Off-diagonal Ramsey numbers

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 Ω\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,k)\ge k^{\frac{s+1}{2}+o(1)}$ which was first established by Spencer in 1977 and has since only seen polylogarithmic improvements.

The new version achieves the tight exponent $r(s,k)\ge k^{s-1+o(1)}$ compared to the previous $r(s,k)\ge k^{s-2+o(1)}$