Abstract
The Ramsey number $R(k)$ is the minimum $n \in \mathbb {N}$ such that every red-blue colouring of the edges of the complete graph $K_n$ on $n$ vertices contains a monochromatic copy of $K_k$. We prove that $$R(k) \leqslant (4 – \varepsilon )^k$$ for some constant $\varepsilon > 0$. This is the first exponential improvement over the upper bound of Erdös and Szekeres, proved in 1935.
Authors
Marcelo Campos
IMPA, Estrada Dona Castorina 110, Jardim Botânico, Rio de Janeiro, 22460-320, Brasil
Simon Griffiths
Departamento de Matemática, PUC-Rio, Rua Marquês de São Vicente 225, Gávea, 22451-900 Rio de Janeiro, Brasil
Robert Morris
IMPA, Estrada Dona Castorina 110, Jardim Botânico, Rio de Janeiro, 22460-320, Brasil
Julian Sahasrabudhe
Department of Pure Mathematics and Mathematical Statistics, Wilberforce Road, Cambridge, CB3 0WA, UK
Full Article