The asymptotics of r(4,t)

Abstract

For integers $s,t \ge 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}{\mathrm{log}^4 t}\Bigr)$ \quad\quad\quad \mathrm{as}\ t \rightarrow \infty, \] which determines $r(4,t)$ up to a factor of order $\mathrm{log}^2 t$, and solves a conjecture of Erdős.

Topics & Concepts