The asymptotics of r(4,t)

By Sam Mattheus, Jacques Verstraëte. Annals of Mathematics, 2023

73 citations recorded by the source corpus.

For integers $s,t \geq 2$, the Ramsey numbers $r(s,t)$ denote the minimum $N$ such that every $N$-vertex graph contains either 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\H{o}s.

Subfields: Algebra and Number Theory, Artificial Intelligence, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/61a6fd22058ed00382aa450766487a0f4bfe02b1