新智元报导  

作者：马杰

修改：KingHZ 

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以及核算最大赤色和蓝色团的巨细。

参考资料： 

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/ 

本文来自微信大众号“新智元”，作者：新智元，36氪经授权发布。