Estimating the Ramsey Number R(4,k)
Learn about the breakthrough in estimating the Ramsey number R(4,k). Find out why it's an amazing time to be alive for a combinatorialist at the moment, with a number of longstanding problems being resolved.
Timothy Gowers @wtgowers@mathstodon.xyz
Mathematician. Professeur titulaire de la chaire Combinatoire au Collège de France. Also fellow of Trinity College Cambridge.

It's an amazing time to be alive for a combinatorialist at the moment, with a number of longstanding problems, several of them personal favourites of mine, being resolved. Today I woke up to the news of yet another breakthrough, due to Sam Mattheus and Jacques Verstraete. 🧵
— Timothy Gowers @wtgowers@mathstodon.xyz (@wtgowers) June 8, 2023 
A month or two ago I tweeted about a stunning new result that obtained an exponential improvement for the upper bound for the Ramsey number R(k,k), a problem I had thought about a lot. When I felt stuck on that, I would sometimes turn my attention to a related problem
— Timothy Gowers @wtgowers@mathstodon.xyz (@wtgowers) June 8, 2023 
that felt as though it ought to be easier: estimating the Ramsey number R(4,k). This is the smallest n such that every graph contains either a K_4 (that is, four vertices all joined to each other) or an independent set of size k (that is, k vertices not joined at all).
— Timothy Gowers @wtgowers@mathstodon.xyz (@wtgowers) June 8, 2023 
Following a wellknown and simple proof of Ramsey's theorem leads to an upper bound of around k^3: that is, if you have k^3 vertices, then you'll get either a clique of size 4 or an independent set with k vertices.
— Timothy Gowers @wtgowers@mathstodon.xyz (@wtgowers) June 8, 2023 
In the other direction, a fairly standard use of the probabilistic method  choose a random graph and delete a few troublesome vertices IIRC  gives a lower bound that's more like k^{5/2}.
— Timothy Gowers @wtgowers@mathstodon.xyz (@wtgowers) June 8, 2023 
This is a pretty huge gap, which in the past I have spent quite a bit of time trying to close. I am an optimist, so I concentrated my efforts on trying to reduce the upper bound.
— Timothy Gowers @wtgowers@mathstodon.xyz (@wtgowers) June 8, 2023 
Another reason for that decision was that to improve the lower bound would require improving on the probabilistic method, which is difficult to do and usually requires algebraic methods well outside my area of expertise.
— Timothy Gowers @wtgowers@mathstodon.xyz (@wtgowers) June 8, 2023 
Well, it now turns out that my efforts were doomed to failure, as the exponent 3 is correct, and all that remains is to sort out a few remaining log factors. Mattheus and Verstraete did indeed use algebraic methods, mixing them in a clever way with probabilistic techniques.
— Timothy Gowers @wtgowers@mathstodon.xyz (@wtgowers) June 8, 2023 
It will be interesting to see whether this leads to the correct exponent for R(s,k) for all fixed s. (It automatically leads to some improvements to those exponents, since you can use the standard inductive argument to reduce to R(4,k) and then apply the new improved bound.)
— Timothy Gowers @wtgowers@mathstodon.xyz (@wtgowers) June 8, 2023 
Here is the preprint if you want to take a closer look. (I should make clear that I have merely skimmed it very rapidly, but I would be very surprised if it turned out not to be correct.)https://t.co/MEy5znvqfD
— Timothy Gowers @wtgowers@mathstodon.xyz (@wtgowers) June 8, 2023