Exploring the Exponential Improvement of Ramsey's Theorem

I was at a sensational combinatorics seminar in Cambridge yesterday, reminiscent of the time I had been tipped off that Andrew Wiles's seminar at the Newton Institute on Wednesday 23rd June 1993 might be worth going to. 🧵https://t.co/rDj3KA4MPO

— Timothy Gowers @wtgowers@mathstodon.xyz (@wtgowers) March 17, 2023

The speaker was my colleague Julian Sahasrabudhe, who announced that he, Marcelo Campos, Simon Griffiths and Rob Morris had obtained an exponential improvement to the upper bound for Ramsey's theorem. pic.twitter.com/rG27mBmRNP

— Timothy Gowers @wtgowers@mathstodon.xyz (@wtgowers) March 17, 2023

Ramsey's theorem says that for any number k there is a number R(k) with the property that if you have R(k) people in a room and any two of them are either friends or enemies, then you can find k people who are either all friends of each other or all enemies of each other.

— Timothy Gowers @wtgowers@mathstodon.xyz (@wtgowers) March 17, 2023

Or to put it in its more mathematical formulation, if you colour all the edges of the complete graph with R(k) vertices either red or blue, then you get either a red clique of size k or a blue clique of size k.

The big question is how large R(k) needs to be.

— Timothy Gowers @wtgowers@mathstodon.xyz (@wtgowers) March 17, 2023

A famous argument of Erdős and Szekeres shows that the binomial coefficient 2k choose k is enough. This is roughly 4^k. An equally famous argument of Erdős shows that 2^{k/2} is not enough.

— Timothy Gowers @wtgowers@mathstodon.xyz (@wtgowers) March 17, 2023

His proof: a random colouring of the edges works! This can be established with a pretty simple calculation. The proof was extremely influential, as it was one of the first uses of random constructions to answer a significant open problem.

— Timothy Gowers @wtgowers@mathstodon.xyz (@wtgowers) March 17, 2023

There have been subsequent improvements to the upper bound, but the following question has been open since 1935: can the upper bound be improved to C^k for some C that is strictly less than 4?

— Timothy Gowers @wtgowers@mathstodon.xyz (@wtgowers) March 17, 2023

Basically all combinatorialists have tried hard to answer this question -- including me -- and I think it's fair to say that it is one of the top two or three open problems in extremal combinatorics, or perhaps even the actual top one.

— Timothy Gowers @wtgowers@mathstodon.xyz (@wtgowers) March 17, 2023

Except that it isn't open any more, since Campos, Griffiths, Morris and Sahasrabudhe have now obtained an upper bound that is at least as good as (3.9995)^k, and possibly better -- we'll have to wait for the dust to settle a bit.

— Timothy Gowers @wtgowers@mathstodon.xyz (@wtgowers) March 17, 2023

Julian suggested a few days ago that "it might be nice to have an end of term pint", which was somewhat unprecedented for us serious Cambridge combinatorialists. Once his seminar got going, it suddenly all made sense. And we went for the pint. pic.twitter.com/anLetxhUJn

— Timothy Gowers @wtgowers@mathstodon.xyz (@wtgowers) March 17, 2023

Here are a few more of us.

Apparently, all four authors gave seminars at roughly the same time, in different parts of the world. It was the culmination of a project that started five years ago. pic.twitter.com/lI9jHPNeq8

— Timothy Gowers @wtgowers@mathstodon.xyz (@wtgowers) March 17, 2023

I was worried during the seminar that I was going to have the feeling that if only I had thought a bit harder at a certain point in my life I might have solved the problem myself.

— Timothy Gowers @wtgowers@mathstodon.xyz (@wtgowers) March 17, 2023

But I didn't have that feeling at all: the proof was very different from the kind of argument I had tried to find, and I don't think I would ever have found it. So even if a little dream dies, I'm very happy to see this breakthrough.

— Timothy Gowers @wtgowers@mathstodon.xyz (@wtgowers) March 17, 2023

And I'm particularly happy to have been in the audience when it was announced -- this time I had no tip-off (and had even managed to forget that the title of the seminar was "On an old problem of Erdős").

Many congratulations to Marcelo, Simon, Rob and Julian.

— Timothy Gowers @wtgowers@mathstodon.xyz (@wtgowers) March 17, 2023