The asymptotics of $r(4,t)$


For integers $s,t \geq 2$, the Ramsey number $r(s,t)$ denotes the minimum $n$ such that every $n$-vertex graph contains a clique of order $s$ or an independent set of order $t$. In this paper we prove \[ r(4,t) = \Omega\Bigl(\frac{t^3}{\log^4 \! t}\Bigr) \quad \quad \mbox{ as }t \rightarrow \infty,\] which determines $r(4,t)$ up to a factor of order $\log^2 \! t$, and solves a  conjecture of Erdős.


Sam Mattheus

Vrije Universiteit Brussel, Brussels, Belgium

Jacques Verstraete

University of California, San Diego, La Jolla, CA, USA