昨天，在剑桥大学有一场关于拉姆齐理论的讲座。很多人事先就听说，有很大的进展。所以菲尔兹奖得主陶哲轩和高尔斯同时到场旁听。

主讲人是剑桥的Julian Sahasrabudhe，研究合著者包括Marcelo Campos，Simon Griffiths和Rob Morris。

高尔斯今天在推特上评价说，上一次在剑桥听到这么精彩的讲座，还是安德鲁·怀尔斯(证明费马大定理)那次。陶哲轩则称，自己一直在考虑这个问题，但是没想到有如此精妙的解决方案。

拉姆齐理论(Ramsey's theorem)有一个特别有名的具体例子：随意找6个人，其中存在3个人互相认识或存在3个人彼此都不认识，这两种情况必居其一。

一般情况借助图论的语言则是说，对于顶点数目足够多的完全图(就是任意两个顶点之间存在一条边)，用红蓝两种颜色随意给边染色，则其中存在蓝色n阶完全子图或存在红色m阶子图，这两种情况必居其一时，原图的顶点数最少是多少？

一般这个数字用R(n，m)表示。

著名数学家保罗·爱多士曾经开玩笑说：“如果外星人入侵，要求人类计算出R(5，5)，否则就消灭人类。那我们可以集全球之力，给他们答案。如果外星人要求计算R(6，6)，那我们还是直接和外星人拼命好了。”

其实R(6，6)本身并不大，正是爱多士与合作者塞克尔斯计算出R(k，k)有个上界4^k。大家不妨思考一下，为何上限不超过4^6，我们却不能通过暴力穷举来确定，而要选择血拼外星人呢？

系统地求解拉姆齐数R(n，m)，所有组合领域内的相关学者都试图解决这一问题，我认为它可以说是极值组合学中的前二或前三的开放问题之一，或者就是排名第一的问题之一。

但90年过去，我们对此未能再改进分毫。这里有特殊的说法，给R(k，k)开k次方，我们想知道随着k增长，它的上确界是否可以小于4，甚至是否存在极限。否则，其实还是有人给出更小的上界的。

直到昨天，我们知道存在正数ε(=1/2^7)，R(k，k) ＜ (4 − ε)^k。

论文：https://arxiv.org/pdf/2303.09521v1.pdf

PREV : 这种激素在体内含量越高，我们就越不容易酒精中毒
NEXT : 今日好价 0318