Estimating the Ramsey Number R(4,k)

It's an amazing time to be alive for a combinatorialist at the moment, with a number of long-standing 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 well-known 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