查看原文
其他

图论大突破 | 菲尔兹奖得主陶哲轩、高尔斯围观

和乐数学 和乐数学 2023-04-11

图论大突破 | 菲尔兹奖得主陶哲轩、高尔斯围观的讨论班

3月16日,

M. Campos, S. Griffiths, R. Morris, J. Sahasrabudhe

在arXiv上上传了一篇文章

An exponential improvement for diagonal Ramsey

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

3月18日,微博博主“物理芝士数学酱”发布微博,介绍说

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

主讲人就是这篇文章的作者之一:剑桥的Julian Sahasrabudhe。

根据“物理芝士数学酱”:

高尔斯今天在推特上评价说,上一次在剑桥听到这么精彩的讲座,还是安德鲁·怀尔斯(证明费马大定理)那次。

拉姆齐

拉姆齐理论是以英国数学家和哲学家弗兰克·P·拉姆齐(Frank P. Ramsey)的名字命名的。

1930年拉姆齐在论文On a Problem in Formal Logic (《形式逻辑上的一个问题》)证明:

通俗地说,这个结论表明:随意找至少6个人,其中必定存在3个人互相认识或3个人彼此都不认识,两者必居其一。

在一群人中,如果人数足够多,“必定存在3个人互相认识或3个人彼此都不认识,两者必居其一”这样的关系一定存在,这个6是至少要找的人。

上述问题自然可以推广:你需要邀请多少人参加一个聚会,才能保证一定会有个人彼此认识,或者个人彼此不认识?

如果将人数用图的顶点来描述,两人认识用两个顶点之间有红色的边连接表示,不认识用蓝色的边连接来表示,则可以用图论语言描述这里的问题:

顶点数至少要多少,才能使其中存在蓝色阶完全子图或存在红色阶子图,且这两种情况必居其一?

这里要求的数字就是

则  


就如哥德巴赫猜想,孪生素数猜想等著名难题,问题理解起来都很简单,但解答很困难:

即使至今不知道确切值。

数学家保罗·埃尔德什(Paul Erdös)曾经开玩笑说:

“如果外星人入侵,要求人类计算出R(5,5),否则就消灭人类。那我们可以集全球之力,给他们答案。如果外星人要求计算R(6,6),那我们还是直接和外星人拼命好了。”

不能算出精确解,那就估计吧。

1935年,埃尔德什和Szekeres证明了

1947年,埃尔德什又发现了拉姆齐数的下界:

埃尔德什证明上述结论的概率方法引发了概率论在组合数学中的应用。

七八十年来,埃尔德什的结果有些改进,但进展缓慢。

上述突破性文章的作者证明的结论是,存在正常数,使得对充分大的,有

ε

作者给出了两个证明。一个给出

一个给出

作者强调,这里的常数是可以改进的。

有人评论说,报告人Julian Sahasrabudhe可能能获得菲尔兹奖。他是2017年获得博士学位。2017-2018年曾访问另一位作者Morris。


欢迎关注【和乐数学】并加星标。

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存