An exponential improvement for diagonal Ramsey

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) \le (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

Departmento 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, University of Cambridge, Wilberforce Road, Cambridge CB3 0WA, United Kingdom