Improving $R(3,k)$ in just two bites

Abstract

We present a flexible random construction which, for certain graphs $H$, is able to produce $H$-free graphs with edge density strictly larger than that of the $H$-free process, while simultaneously preserving pseudorandom properties and allowing a much easier analysis. As our main application, we use this construction to show that the off-diagonal Ramsey numbers satisfy $R(3,k)\ge \left(\frac{1}{2}+o(1)\right)\frac{k^2}{\log k}$, improving the previously best bound $R(3,k)\ge \left(\frac{1}{3}+o(1)\right)\frac{k^2}{\log k}$. While the best known upper bound is $R(3,k)\le \left(1+o(1)\right)\frac{k^2}{\log k}$, the constant of $\frac{1}{2}$ has been conjectured to be asymptotically tight by multiple groups.

18 pages