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

主讲人是剑桥的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

[ 广告 ]

支付宝打赏 [x]
您的大名: 打赏金额:

赞一个 (10)

PREV :
NEXT :