Upper bounds on diagonal Ramsey numbers [after Campos, Griffiths, Morris, and Sahasrabudhe]
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910755237920768 |
|---|---|
| author | Wigderson, Yuval |
| author_facet | Wigderson, Yuval |
| contents | 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 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ás, Campos, Griffiths, Hurley, Morris, Sahasrabudhe, and Tiba, who gave an alternative, and more conceptual, proof. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_09321 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Upper bounds on diagonal Ramsey numbers [after Campos, Griffiths, Morris, and Sahasrabudhe] Wigderson, Yuval Combinatorics 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 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ás, Campos, Griffiths, Hurley, Morris, Sahasrabudhe, and Tiba, who gave an alternative, and more conceptual, proof. |
| title | Upper bounds on diagonal Ramsey numbers [after Campos, Griffiths, Morris, and Sahasrabudhe] |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2411.09321 |