flâneur

[2605.28793] Nearly tight exponents for off-diagonal Ramsey numbers

arxiv.org · 192 words · saved by 1 readers

Abstract:We construct a new family of $K_s$-free graphs that leads to improved lower bounds for Ramsey numbers across a wide range of parameters. For any fixed $s \ge 4$, we show that the off-diagonal Ramsey numbers satisfy $r(s, k) \ge k^{s-2 + o(1)}.$ For $s \ge 6,$ this improves the best known lower bound of the form $r(s, k) \ge k^{\frac{s+1}{2} + o(1)}$ which was first established by Spencer in 1977 and has since only seen logarithmic improvements. This nearly matches the best known upper bound which is of the form $r(s, k) \le k^{s-1 + o(1)}$ and which is widely believed to give the correct exponent. More generally, we show that if $s, k/s \rightarrow \infty$, then $r(s, k) = \left(\frac{k}{s}\right)^{(1+o(1)) s},$ where the upper follows from the seminal work of Erdős and Szekeres in 1935. We also obtain improved lower bounds for Ramsey numbers extremely close to the diagonal as well as for diagonal multicolor Ramsey numbers.

View PDF HTML (experimental) Abstract:For positive integers $s$ and $k$, the Ramsey number $r(s,k)$ is the minimum integer $n$ such that any graph on $n$ vertices contains a clique of size $s$ or an independent set of size $k$. We prove that for any fixed $s \ge 3$ and $k$ tending to infinity, the off-diagonal Ramsey numbers satisfy \[ r(s, k) \ge \Omega \left(\frac{k^{s-1}}{(\log k)^{2s-4}} \right), \] which matches, up to polylogarithmic factors, the upper bound established over 90 years ago by Erdős and Szekeres. For $s \ge 5,$ this improves the best known lower bound of the form $r(s,…

saved by

related reading