The Ramsey Numbers - New Results and New Perspectives
Speaker: Julian SahasrabudheDate of Talk: December 12, 2024
Upstream link: UCLA Colloquium
The speaker’s last name is pronounced “Sa-Has-Ra-Bu-Day”.
1. Upper and Lower Bounds for Ramsey Numbers
The Ramsey number \(R(k)\) is the smallest integer \(n\) such that every \(2\)-colouring of the complete graph on \(n\) vertices \(K_n\) contains a monochromatic copy of \(K_k\). For instance, \(R(3) = 6\): every \(2\)-colouring of the complete graph on \(6\) vertices contains a monochromatic triangle, but there is a colouring of \(K_5\) containing no monochromatic triangles.
In 1930, Ramsey showed that these numbers do exist. The main focus of this talk is understanding the asymptotics of \(R(k)\).
It can be easily shown that \(R(k) \geq (k-1)^2\): take \(k-1\) disjoint copies of \(K _{k-1}\), all coloured the same, and connect every disconnected pair of vertices with the opposite colour. For a while, this was believed to be “close to truth”, but in 1947, Erdős produced a better lower bound of \[R(k) \geq \left( 1+ o(1) \right) \frac{k}{e\sqrt 2} 2 ^{\frac{k}{2}}.\] He did this in the most troll way imaginable. Grab a random colouring of the complete graph with this many vertices, then just compute the probability it has a monochromatic \(K_k\) in it. It ends up being less than \(1\), so there have got to be colourings with no monochromatic \(K_k\)’s in them! (Surprisingly, it’s actually quite difficult to construct these colourings explicitly…it’s like “finding hay in a haystack”.) Since 1947, there has been little progress on this lower bound: the \(\sqrt 2\) was moved to the numerator, but that’s it.
On the other side is the upper bound of \(4^k\), by Erdős and Szekeres in 1935. This was done by extending the pigeonhole argument for \(R(3)=6\).
2. Is God on our side?
The speaker presented the following beautiful analysis of the gap between the upper bound and lower bound above, only far more convincingly than I can convey in writing. I think I sound like a babbling lunatic when I try to describe what I heard.
On one hand, the Erdős-Szekeres method is very wasteful: the pigeonhole principle discards a lot of the structure in the graphs. But if in fact \(R(k)\sim 4^k\), this suggests that an adversarial deity can force these inefficiencies with the right colouring, and that somehow these recursive structures cannot communicate vertically.
On the other extreme, \(R(k) \approx 2 ^{\frac{k}{2}}\) suggests that the deity is benevolent rather than adversarial, and that every colouring looks more or less like a random one.
Perhaps truth is somewhere in between the two. Order in a colouring can perhaps be cleverly exploited directly, and the inefficiencies in the Erdős-Szekeres method must come with some kind of order. “On average”, one would expect the pigeonholing argument to work much better.
3. Progress on Upper Bounds
Erdős-Szekeres actually got an upper bound of \(\lesssim \frac{4^k}{\sqrt k}\) in 1935. Half a century later, Rödl saved some logs and got \(\lesssim \frac{4^k}{\sqrt k \left( \log k \right)^2}\) in 1988. Thommaon improved this the same year to \(\lesssim \frac{4^k}{k}\) by studying “quasirandomness”. In 2006, Conlon obtained \(\lesssim 4 ^{k - \left( \log k \right) ^{2-o(1)}}\), i.e. better than \(4^k\) divided by any polynomial. In 2023, Sah removed the \(o(1)\) in the exponent.
Sahasrabudhe, Campos, Griffiths, and Morris in 2023 made an exponential improvement, showing an upper bound of \(\left( 4- \epsilon \right)^k\). Together with Balister, Bollobás, Hurley, and Tiba, they were similarly able to produce an exponential improvement in the \(r\)-coloured generalisation of this problem.
Ultimately, this work fundamentally uses the same argument that Erdős and Szekeres used nearly 100 years ago, but with much more sophisticated book-keeping and optimisation on how the pigeonholing was done. This was enough to make a whole exponential improvement!
Curiously, \(R(k)\) is only known for \(k\leq 4\). Even \(R(5)\) isn’t known, and that’s strangely tantalising, especially since the gaps between our best-known bounds are so wide…