Computer Science/Discrete Mathematics Seminar II

The $r$-colour Ramsey number $R_r(k)$ is the minimum $n \in \mathbb{N}$ such that every $r$-colouring of the edges of the complete graph $K_n$ on $n$ vertices contains a monochromatic copy of $K_k$. We prove, for each fixed $r \ge 2$, that 

$$R_r(k) \le e^{-\delta k} r^{rk}$$ 

for some constant $\delta = \delta(r) > 0$ and all sufficiently large $k \in \mathbb{N}$. For each $r \ge 3$, this is the first exponential improvement over the upper bound of Erdős and Szekeres from 1935. In the case $r = 2$, it gives a different (and significantly shorter) proof of a recent result of Campos, Griffiths, Morris and Sahasrabudhe.  This is based on joint work with Paul Balister, Bela Bollobas, Marcelo Campos, Simon Griffiths, Eoin Hurley, Robert Morris and Julian Sahasrabudhe.