78年后，中国数学家刷新世界记录！陶哲轩伯乐的外星人难题新突破

新智元报道

编辑：KingHZ

【新智元导读】陶哲轩的伯乐Erdős，有则关于外星人为难全人类的数学寓言，喻示Ramsey数计算之难。2025年，三位中国数学家的arxiv论文为某类Ramsey数注入新希望。

1947年，陶哲轩的伯乐Erdős提出了组合数学中Ramsey数下界。

10岁的陶哲轩和Erdős

最近，国内的马杰等三位研究人员联手带来了首次指数级改进。

他们公布了一篇arxiv新论文展示了这一领域的惊人进展：

论文链接：https://arxiv.org/abs/2507.12926

数学家、计算机科学家Gil Kalai表示改进令人惊叹！

什么是Ramsey数？

在近百年前，英国逻辑学家Frank Ramsey就证明了这样一个有趣的结论：

在一个六人聚会中，无论这六人之间的关系如何，总能找到三人彼此相识，或者三人互不相识。

Frank Ramsey（1903–1930）英年早逝，年仅26岁。除了数学，在哲学上，他成就斐然，被公认为二十世纪最重要和最具影响力的思想家之一

这个简单而直观的例子，正是Ramsey理论的最早雏形。

当图中的节点数量不断增加时，图中就会出现越来越复杂的结构。而在整数序列中，也会自然浮现出类似的有序模式。

荷兰数学家兼数学史学家Bartel Leendert van der Waerden曾经证明：即使是一组看似随机的整数，也必然会出现某种等差数列结构。

这种现象揭示了Ramsey理论的核心思想：

当元素数量足够多时，某些有序模式的出现将变得不可避免。也就是说，混乱之中也会自发地产生秩序。

Ramsey数就是关于图论中有序模式：

Ramsey数用于衡量图论中图的规模——图在变大到某个程度后，某些特定的模式将不可避免地出现。

比如，将五个顶点两两相连，构成一个完全图（即每个顶点都与其余所有顶点相连）。在五个顶点的完全图中，我们可以把每条边涂成红色或蓝色，并且仍然可以避免出现三个顶点之间的所有边颜色相同的情况。

但如果是六个顶点，无论如何着色，都会不可避免地出现三个顶点之间的边颜色相同的情形。

对于使用两种颜色，并要求图中不出现大小为3的同色完全子图（clique），对应的Ramsey数R(3，3)是6。上图标出了一个由三个顶点组成的单色团。

换句话，在一个聚会中，可以保证其中三个人之前已经见过面，而另外三个人彼此都不认识，最低只需要6个人。但如果将总数减少到五个，这种确定性就会消失。

宇宙级难题

然而，数学家们发现，要确定到底在哪个点这些模式一定会出现，也就是找到这个「临界阈值」，极其困难。除了最简单的情形，目前几乎都无法精确计算出来。

Ramsey数R(a，b)的一些已知值

例如，R(5,5) 是一个代表性的问题，表示图中一定会出现红色或蓝色的五边形结构。其精确值仍未确定，当前仅知其介于43和48之间。

在研究Ramsey数的圈内，流传着一个广为人知的寓言，通常被认为出自Erdős，用来形象地说明这个问题的难度增长有多么迅猛。

寓言是这样的：

有一天，外星人入侵地球。他们提出条件：只要人类能算出一个正确的Ramsey数，他们就放过地球。

如果他们问的是Ramsey数R（5，5），我们应该立刻动员整个人类文明的计算能力，全力以赴去求解它。

但如果他们问的是R（6，6）——那最好放弃幻想，准备斗争。

尽管如此，数学家仍不断尝试推进上界和下界的收敛，并在过程中探索新的证明策略。

Erdős与合作者曾开创性地用概率推断图中结构的出现，从而避免上界过大。这些方法不仅极大推动了数学，也为算法设计带来了突破。

拉姆齐原理的魅力在于它的普适性：从数论到计算机科学，从图论到逻辑学和几何学，这一理论的深远影响几乎遍布整个数学世界

天才数学家的方法

Erdős，匈牙利数学家，1913年3月26日—1996年9月20日，在数论和计算机科学等多个领域做出了重要贡献。

Erdős，中文名全称为埃尔德什·帕尔，原名Erdős Pál，英语名Paul Erdős。他发表论文高达1525篇（包括与人合写的），是目前发表论文数最多的数学家（其次是欧拉）；曾和511人合写论文。

Erdős成功的关键公式：数学家+数学家+数学家=更多、更好的数学

1947年，Erdős提出的最初下界是通过随机染色Kn得到的：每条边以概率p被染成红色，其他情况下染成蓝色。

论文链接：https://www.ams.org/journals/bull/1947-53-04/S0002-9904-1947-08785-1/S0002-9904-1947-08785-1.pdf

Erdős方法估算Ramsey数的技巧分为5大步：

（1）假设从一个包含10个顶点的完全图出发。如果我们用3种颜色（例如红、蓝、黄）随机为每条边染色，那么图中是否总会出现5个顶点，其中的10条边都被染成相同颜色？

（2）每条边被染成红色的概率是1/3。

（3）因此，10条边都恰好为红色的概率是 (1/3)¹⁰。

（4）由于我们有3种颜色，任何一种都可能形成一个单色团(clique)。

（5）而10个顶点中可能组成的5-点子集（也就是5-点团）共有252种组合方式。

所以，出现任意颜色的5点单色团的总体概率不超过：(1/3)¹⁰×3×252小于1。

上图中高亮显示了一个满足该条件的红色子图：由5个顶点和10条红色边组成的红色团（完全子图）。

这就是所谓的并集界（union bound）：它估算的是在随机染色下生成单色团的可能性。由于这个值小于1，意味着在某些情况下，10个顶点的图可以**不包含**任意颜色的 5 点单色团。

所以我们可以得出结论：这个Ramsey数（表示5点单色团必然出现的最小顶点数）一定大于10。

持续的挑战

Erdős等人几十年前提出的概率方法，基于随机图中出现目标结构的可能性，并结合一些数学公理，得出较为合理的上界。这一思路不仅成功运行了近百年，还推动了算法中随机性使用的发展。

马里兰大学计算机科学教授William Gasarch指出，这些概率技术已经被用于网络路由算法，以及理论计算机科学的核心问题中。

路由算法可以在多个节点间随机选择路径，从而避免穷举整个网络来寻找最优结构。

1980年代早期，清华「姚班之父」、图灵奖得主姚期智证明了，在数据表达到一定大小后，其行必须进行排序，才能避免访问效率的下降，这也是Ramsey理论在计算机应用中的一个典型实例。

然而，数学家们逐渐意识到，纯粹的概率方法存在局限。这促使他们转向新的方法：构造遵循明确规则的图结构，以人为避免某些clique的出现，直到其变得不可避免。与完全依赖随机过程相比，这种构造方法在某些情境下可能更有效。

三十多年前，普林斯顿大学数学教授Noga Alon提出了一种确定性构造无三角形图（triangle-free graph）的方法，取得了成功。但更大规模图的构造仍缺乏稳定可靠的手段，因此随机生成仍是当前最有效的工具。

Mattheus与Verstraete借助有限几何中的工具，对 R(4,t) 的上界进行了深入研究。他们设法从初始伪随机图中剔除所有四节点clique，并在此基础上构造了一个证明，展示了随着t的增加，其上界如何增长。

论文链接：https://arxiv.org/abs/2306.04007

2023年，数学家Gil Kalai介绍过当时取得的最新成果。

链接：https://gilkalai.wordpress.com/2023/03/16/some-news-from-a-seminar-in-cambridge/

今年5月，Marcelo Campos、Simon Griffiths、Robert Morris和Julian Sahasrabudhe证明了R(3，k)指数级的改进。

论文链接：https://arxiv.org/abs/2505.13371

而关于更一般的Ramsey数的下界，最佳记录是1974年Joel Spencer提出的。

论文链接：https://www.sciencedirect.com/science/article/pii/0097316575900710

超越Ramsey理论

由 Jie Ma、Wujie Shen和Shengjie Xie撰写的论文中引入并研究了一类几何随机图模型。这类模型本身就具有较高的研究价值，甚至超出了Ramsey理论的范畴。

正如作者所指出的，目前仍无法确定在C=1的情况下是否能获得比 Erdős 1947年构造更优的下界。

研究当C→1时的情况以及ϵ如何依赖于C，也是一个有趣的问题。

我们是否能超越Erdős早期构造，仍然是一个悬而未决的问题。

数学家、计算机科学家Gil Kalai表示：论文中所考虑的随机模型令人印象深刻。

在d维球面上随机选择n个点。

设置一个阈值，并根据两点之间的距离是否低于该阈值，将它们之间的边染色为蓝色或红色。

阈值的选择使得边是红色的概率为p（因此边是蓝色的概率为1-p）。

这一模型与Erdős–Rényi模型 G(n,p) 有些相似，但增加了微妙的相互依赖性。与G(n,p)模型相比，这些细微的依赖关系导致红色和蓝色大团的预期数量（或仅是概率）减少，如何理解这一机制将是一个有趣的课题。

论文的关键贡献在于复杂的分析过程，涉及选择维度d以及计算最大红色和蓝色团的大小。

作者介绍

马杰现任清华大学丘成桐数学科学中心教授和北京雁栖湖应用数学研究院教授。2011年从佐治亚理工学院数学学院获得博士学位，之后在Benny Sudakov教授指导下在加州大学洛杉矶分校数学系担任Hedrick助理教授两年，后任卡内基梅隆大学数学科学系博士后研究员，及中国科技大学数学科学学院教授。马杰的主要研究兴趣是极值组合学和图论。他获得了国家自然科学基金杰出青年科学基金的资助。

参考资料：

https://gilkalai.wordpress.com/2025/07/23/amazing-jie-ma-wujie-shen-and-shengjie-xie-gave-an-exponential-improvement-for-ramsey-lower-bounds/

https://arxiv.org/pdf/2507.12926

https://www.quantamagazine.org/after-nearly-a-century-a-new-limit-for-patterns-in-graphs-20230502/

https://www.quantamagazine.org/new-math-proof-raises-lower-bounds-of-graph-randomness-20201104/

https://cacm.acm.org/news/the-secret-of-ramsey-numbers/