Upper bounds on diagonal Ramsey numbers, after Campos, Griffiths, Morris, and Sahasrabudhe

par Yuval Wigderson

samedi 23 nov. 2024, 16:00 → 17:00 Europe/Paris

Amphithéâtre Hermite (Institut Henri Poincaré)

Ramsey's theorem states that if $N$ is sufficiently large, then no matter
how one colors the edges among $N$ vertices with two colors, there are
always $k$ vertices spanning edges in only one color. Given this theorem,
it is natural to ask "how large is sufficiently large?" Ramsey's original
proof showed that $N=k!$ is sufficient, and five years later Erdős and
Szekeres improved this bound to $N=4^k$. And then progress stalled for
almost 90 years.

In this talk, I will present the history of the problem, and discuss some
of the ideas used in the recent breakthrough of
Campos–Griffiths–Morris–Sahasrabudhe, who proved that $N={3.993}^k$ is
sufficient. In particular, I will try to highlight the central role of
book graphs, which play an important role in all known approaches to
this problem.