The asymptotics of r(4,t)

Sam Mattheus wrote on his blog “Points and Lines” a summary with a general overview of the proof for his breakthrough with Jacques Verstraete about .

Jacques Verstraete and I posted a preprint on the arXiv today on the off-diagonal Ramsey number $latex r(4,t)$. In short, we show that $latex r(4,t) = Omega(t^3/log^4t)$, which is just a $latex log^2t$ factor shy from the upper bound $latex r(4,t) = O (t^3/log^2t)$ proved by Ajtai, Komlós and Szemerédi in 1980. Erdős [1] conjectured that up to logarithmic factors, $latex t^3$ is the order of growth:

We thus confirm this conjecture. The previous best lower bound was due to Bohman and Keevash who studied the random $latex K_4$-free process and obtained $latex r(4,t) = widetilde{Omega}(t^{5/2})$, where the tilde hides logarithmic factors. It is not clear whether our methods can be pushed further to obtain asymptotically sharp bounds. In any case, that’s not what I want to speculate about, but rather sketch the proof of our result. It’s in my very biased opinion a nice combination of ideas that existed…