An exponential improvement for Ramsey lower bounds

Abstract

We prove a new lower bound on the Ramsey number $r(\ell ,C\ell )$ for any constant $C>1$ and sufficiently large $\ell$, showing that there exists $\epsilon =\epsilon (C)>0$ such that \[ r(\ell, C\ell) \geq \left(p_C^{-1/2} + \varepsilon\right)^\ell, \] where $p_C\in (0,1/2)$ is the unique solution to $C=\frac{\log p_C}{\log (1-p_C)}$. This provides the first exponential improvement over the classical lower bound obtained by Erdős in 1947.

44 pages, 3 figures