Ramsey numbers and the Zarankiewicz problem
| Autor: | Conlon, David, Mattheus, Sam, Mubayi, Dhruv, Verstraëte, Jacques |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | Building on recent work of Mattheus and Verstra\"ete, we establish a general connection between Ramsey numbers of the form $r(F,t)$ for $F$ a fixed graph and a variant of the Zarankiewicz problem asking for the maximum number of 1s in an $m$ by $n$ $0/1$-matrix that does not have any matrix from a fixed finite family $\mathcal{L}(F)$ derived from $F$ as a submatrix. As an application, we give new lower bounds for the Ramsey numbers $r(C_5,t)$ and $r(C_7,t)$, namely, $r(C_5,t) = \tilde\Omega(t^{\frac{10}{7}})$ and $r(C_7,t) = \tilde\Omega(t^{\frac{5}{4}})$. We also show how the truth of a plausible conjecture about Zarankiewicz numbers would allow an approximate determination of $r(C_{2\ell+1}, t)$ for any fixed integer $\ell \geq 2$. Comment: 9 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|