埃尔德什经典「拉姆齐数下界」，被三位中国学者首次指数级改进

机器之心编译

半个多世纪前，经典级改进匈牙利数学家保罗・埃尔德什（Paul Erdős）利用随机性这一利器，拉姆照亮了网络理论中庞大而奇异的齐数领域。如今，下界学数学家们正通过引入新的被位几何视角，让这套经典方法焕发出前所未有的中国指数强大生命力。

1947 年，首次在四处漂泊的经典级改进旅途中，保罗・埃尔德什提出了一种后来被公认为数学界最有力工具之一的拉姆证明方法。当时，齐数他的下界学目标是证明某类特定对象的存在性 —— 即由相互连接节点构成的网络（图）。

该证明的被位独特之处在于，它并未提供构造该网络的中国指数具体算法。相反，首次埃尔德什论证道：若考察所有可能的经典级改进网络结构并从中随机抽取一个，那么抽中具备目标性质网络的概率大于零。换言之，满足条件的网络必然存在于某个角落，即便我们对其具体形态知之甚少。

这一思路后来被命名为「概率方法」（Probabilistic Method），其简洁性背后蕴含着革命性的意义。

苏黎世联邦理工学院（ETH Zurich）数学家 Benny Sudakov 指出，在概率方法问世前，「如果你声称某类对象存在，我会要求你将其展示出来。」然而，某些对象因其极度反常的特性，使得人们难以直观接受其真实存在。

埃尔德什的方法巧妙规避了这一认知障碍，证明了随机性能以数学家此前无法想象的方式发挥作用。纽约大学 Joel Spencer 评价道：「用随机性来证明问题，这在当时令人震惊。如今，这已成为数学研究的基本操作。」

目前，概率方法已广泛应用于数学与计算机科学领域，例如素数判定、电路优化设计以及无偏数据清洗等。

尽管研究者从多个维度强化了这一方法，但在其最初关注的核心问题上 —— 即埃尔德什当年试图解决的网络存在性问题，进展却长期停滞。在长达八十年的时间里，数学家未能对埃尔德什给出的解法做出显著改进。

直到最近，这一僵局才被打破。

荒野中的孤独声音

想象一个由节点和边构成的网络，即数学中的「图」。

现在，将每条边染成红色或蓝色，但需遵循一个约束：禁止出现由同色边构成的密集子图，这种结构被称为「单色团」（Monochromatic Clique）。例如，由三个节点两两相连且颜色相同的子图，被称为大小为 3 的团。

当图中的节点数量足够多时，无论采用何种上色方案，都无法完全避免单色团的出现。以大小为 3 的团为例，若节点数达到 6，则必然会出现同色三角形；而节点数不超过 5 时，则存在避免单色团的上色方案。

因此，数学家将大小为 3 的团对应的「拉姆齐数」（Ramsey Number）记作 $R(3)$，其值为 6。拉姆齐数衡量的是：图规模达到何种程度时，某种被禁止的结构将不可避免地出现。

拉姆齐数也可针对不同大小的团进行定义。例如，在一个 8 个节点的图上，可以构造出既无大小为 3 的红色团，也无大小为 4 的蓝色团的上色方案。但若增加至 9 个节点，则必然出现至少一个红色团或蓝色团。因此，$R(3, 4) = 9$。

随着目标团尺寸的增大，问题难度呈指数级上升。迄今为止，仅少数最小拉姆齐数被精确计算。丹佛大学 Paul Horn 表示：「构建无结构对象极其困难。这或许源于人类固有的认知偏见。」

因此，数十年来，数学家的主要任务是寻找拉姆齐数的更优近似估计。1947 年，埃尔德什提出概率方法，旨在解决这一难题。他并未直接构造无团图，而是考察所有可能的上色方式，证明其中至少有一部分比例的上色方案能避开被禁止的团。

整个证明仅寥寥数行，却颠覆了传统直觉。

起初，数学界对这一思路持怀疑态度，学者们更倾向于寻找具体的构造实例。Spencer 回忆道：「多年来，埃尔德什如同荒野中的孤独声音。他用随机性得出了惊人结果，而此前无人尝试过此路。」

然而，概率方法很快证明了其巨大价值。如今，它已成为「离散数学」（研究离散对象如图的数学分支，与连续对象相对）中最核心的方法之一，并延伸至物理学和计算机科学。Horn 认为，随机性帮助我们触及了那些原本抽象且难以把握的数学本质。

近年来，数学家成功改造埃尔德什的方法，用于估计团大小差异显著的拉姆齐数。例如，2025 年，Horn 与合作者利用改进的概率方法，证明了 $R(3, l)$ 更精确的下界，其中 $l$ 可任意增大。这一成果随后推动了图论领域的重大突破。

保罗・埃尔德什发现，即便无法构造特定数学对象，也可通过随机性证明其存在。这一技术被称为「概率方法」，深刻改变了数学和计算机科学的多个分支。

然而，对于团大小相近的拉姆齐数，尤其是埃尔德什最早关注的「对角拉姆齐数」（即红色团与蓝色团大小相同），概率方法长期停滞不前。假设禁止大小为 1000 的团，埃尔德什证明 $R(1000) > 2^{500}$。此后八十年，下界仅推进至约 $2^{501}$。类似地，自 20 世纪 70 年代起，对于非对角拉姆齐数（红蓝团均较大），进展也几乎冻结。

直到一位缺乏拉姆齐理论背景的研究生出现，局面才得以扭转。

带相关性的上色策略

Wujie Shen（申武杰）在清华大学攻读硕士的前几个学期，主要研究几何与拓扑。2024 年春，他在阅读一篇关于拉姆齐数的论文时深受启发。

他深知埃尔德什方法的原理：对图中每条边抛硬币，正面染红，反面染蓝，计算产生无团图的概率。但随着图规模扩大，该计算变得极其复杂。Shen 开始思考：是否存在一种新的随机模型，能比埃尔德什的方法更高效地生成无团上色？

鉴于 Shen 的几何背景，他提出的模型带有鲜明的几何色彩并不意外。传统图上色通常不涉及几何空间概念，数学家仅关注节点间的连接关系，而非节点在空间中的位置。

Shen 试图利用高维球面的几何性质来决定边的颜色。具体而言，他借助高维球面（所有到中心点距离相等的点构成的集合）的特性。

加州理工学院 David Conlon 指出，高维球面「会彻底颠覆我们的直觉」。在高维空间中，球的体积极小，表面积巨大，且大多数点集中在「赤道」附近。Sudakov 表示，处理这类对象「相当复杂」。

从左至右依次为：Jie Ma（马杰）、Wujie Shen（申武杰）和 Shengjie Xie（谢晟捷）。Jie Ma 为中国科学技术大学数学科学学院教授，Wujie Shen 为清华大学丘成桐数学科学中心博士研究生，Shengjie Xie 为中国科学技术大学数学科学学院博士研究生。

Shen 与两位合作者决定尝试这一路径。另一位合作者 Jie Ma 当时正在清华大学访问并任教；第三位是 Ma 的研究生 Shengjie Xie。

他们的核心策略是：将节点逐个随机放置在高维球面上，每个节点位置独立且均匀分布。放置完成后，根据节点间的距离进行上色：若两点距离大于某固定阈值，则染红（概率小于 1/2）；若距离较近，则染蓝。

这种方法生成的图中，红色团出现的概率显著降低。原因在于，形成大型红色团需要大量节点两两相距甚远，而在有限的高维球面上，这种情况极难发生。

然而，代价也随之而来。由于空间限制，这种方法会产生更多含有蓝色团的上色方案。Conlon 质疑：「这看似一种权衡：它显著抑制了一种颜色，却对另一种颜色毫无帮助。为何要这样做？」

尽管如此，团队仍抱有希望。他们在小规模图上测试该方法，发现尽管存在大量劣质上色，但仍存在非零概率得到优质无团上色。这让他们相信，在大图情形下，收益将超过代价。

接下来的挑战是证明这一猜想。关键突破源于高维球面反直觉的几何性质。

为了证明可以避开特定大小的团，Ma、Shen 和 Xie 需要限制节点形成「全远」或「全近」簇的概率。他们发现，若从每个节点向球心连线，这些线在高维空间中几乎彼此垂直。而在二维球面上，这种现象并不显著。他们证明了在高维空间中，这种正交性成立。

这一性质限制了节点间距离的可能分布，从而有效压低了单色团形成的概率。

经过一年的研究与 40 页密集计算，三人在 2025 年 7 月发布论文。随后，成果发表于国际顶级数学期刊《数学新进展》（Inventiones Mathematicae）。

他们改进了埃尔德什关于拉姆齐数下界的结果，但该改进主要适用于蓝色团大于红色团的情形。当红蓝团大小相近时，新方法的增益有限。

论文标题：An exponential improvement for Ramsey lower bounds
论文地址：https://arxiv.org/pdf/2507.12926

Ma 表示：「我们很幸运，感觉所有努力都得到了回报。但这一路确实艰难且漫长。」

剑桥大学 Julian Sahasrabudhe 评价道：「用熟悉的技术解决熟悉的问题，这令人震惊。这项技术其实一直『藏在眼皮底下』。」

概率方法的试验场

Ma、Shen 和 Xie 的证明引发了连锁反应。2025 年 12 月，Sudakov 及其两名研究生大幅简化了该团队的染色模型，并进一步提升了新下界。此后，其他研究者也开始利用该模型估计涉及三种颜色的拉姆齐数。

论文标题：Gaussian random graphs and Ramsey numbers
论文地址：https://arxiv.org/pdf/2512.17718

这与概率方法的悠久历史一脉相承。过去 80 年里，数学家不断调整埃尔德什的随机性技术，试图融入额外结构以增强其威力。这些新技术随后往往在其他领域发挥关键作用。

Sudakov 称：「这是一个极具生命力的思想试验场。」

Ma、Shen 和 Xie 的工作是这一持续数十年故事的最新篇章，也是多年来首个重新触及近对角拉姆齐数问题的重要突破。

他们引入的几何方法，有望继续推动这一顽固数学难题取得进展。Spencer 认为，虽然概率方法尚未触及极限，「但它已变得极其强大，发生了翻天覆地的变化。」

原文链接：https://www.quantamagazine.org/after-80-years-mathematicians-give-famed-erdos-method-an-upgrade-20260626/

(责任编辑：综合)