拉姆齐理论重大理论进展：拉姆齐定理上界的指数改进

AN EXPONENTIAL IMPROVEMENT FOR DIAGONAL RAMSEY

MARCELO CAMPOS, SIMON GRIFFITHS, ROBERT MORRIS, AND JULIAN SAHASRABUDHE

拉姆齐数\( R（k） \)是最小n∈N，使得n个顶点上的完备图\( K_n \)的边的每个红蓝色都包含\( K_k \)的单色副本。我们证明了对于一些常数ε>0，\( R(k)\le{ (4-\varepsilon )} ^k \)。这是在1935年证明的ErdŸos和Szekeres上界的第一次指数改进。

https://arxiv.org/pdf/2303.09521.pdf

来自Timothy Gowers推特翻译：

昨天，我在剑桥参加了一个轰动的组合学研讨会，这让我想起了1993年6月23日星期三在牛顿研究所举行的Andrew Wiles研讨会可能值得一去的时候。

演讲者是我的同事Julian Sahasrabudhe，他宣布他、Marcelo Campos、Simon Griffiths和Rob Morris已经获得了拉姆齐定理上界的指数改进。

拉姆齐定理说，对于任何一个数k，都有一个数R（k），其性质是，如果一个房间里有R（k）个人，其中任何两个人要么是朋友，要么是敌人，那么你可以找到k个人，他们要么都是彼此的朋友，要么都是对方的敌人。

或者把它放在数学的公式中，如果你用R（k）个顶点给整个图的所有边涂上红色或蓝色，那么你会得到一个大小为k的红色团或一个尺寸为k的蓝色团。

最大的问题是R（k）需要有多大。

埃尔德斯和塞克雷斯的一个著名论点表明，二项式系数2k选择k就足够了。这大约是4^k。埃尔德斯的一个同样著名的论点表明，2^{k/2}是不够的。

他的证明：边缘的随机着色有效！这可以通过一个非常简单的计算来建立。这个证明非常有影响力，因为它是第一次使用随机结构来回答一个重大的开放问题。

随后对上界进行了改进，但自1935年以来，以下问题一直悬而未决：对于一些严格小于4的C，上界能否改进为C^k？

基本上所有的组合学家都很努力地回答这个问题，包括我，我认为可以公平地说，这是极端组合学中最热门的两三个开放问题之一，甚至可能是最热门的问题。

除了它不再开放之外，因为坎波斯、格里菲斯、莫里斯和撒哈拉布德现在已经获得了一个上限，这个上限至少和（3.9995）^k一样好，甚至可能更好——我们必须等待尘埃落定。

朱利安几天前建议“期末喝一杯可能会很好”，这对我们这些认真的剑桥组合学家来说是前所未有的。他的研讨会一开始，突然一切都变得有意义了。我们去喝了一品脱。

这里还有我们几个人。

显然，这四位作者几乎同时在世界不同地区举办了研讨会。这是五年前开始的一个项目的高潮。

在研讨会上，我很担心我会有这样的感觉，如果我在人生的某个时刻更加努力地思考，我可能会自己解决这个问题。

但我一点也没有这种感觉：证据与我试图找到的论点大不相同，我想我永远不会找到。所以，即使一个小梦想破灭，我也很高兴看到这一突破。

当它宣布时，我特别高兴能和观众在一起——这一次我没有得到任何消息（甚至忘记了研讨会的标题是“关于埃尔德斯的一个老问题”）。

向马塞洛、西蒙、罗布和朱利安表示热烈祝贺。

附言预印本有57页，但风格温和，有很多聊天内容。

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.   

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.

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.

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.

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.

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.

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?

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.

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.

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.

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.

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.

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.

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.

PS The preprint is 57 pages, but in a gentle style with lots of chat.

推特地址：https://twitter.com/wtgowers/status/1636632071069106181