Back to Search
Start Over
Upper bounds on diagonal Ramsey numbers [after Campos, Griffiths, Morris, and Sahasrabudhe]
- Publication Year :
- 2024
-
Abstract
- 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\H{o}s and Szekeres improved this bound to $N=4^k$. And then progress stalled for almost 90 years. In this survey, I 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 addition, I discuss the subsequent work of Balister, Bollob\'as, Campos, Griffiths, Hurley, Morris, Sahasrabudhe, and Tiba, who gave an alternative, and more conceptual, proof.<br />Comment: Expository paper accompanying a Bourbaki seminar talk (November 2024, expos\'e number 1230). 48 pages. Second version includes the follow-up of Balister et al
- Subjects :
- Mathematics - Combinatorics
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2411.09321
- Document Type :
- Working Paper