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

机器之心编译

数十年前，匈牙利数学家保罗・埃尔德什（Paul Erdős）用随机性照亮了网络这个庞大而奇异的世界。如今，数学家们正在让他的这套方法变得更加强大。

1947 年，四处漂泊的保罗・埃尔德什提出了一种后来成为数学领域最有力工具之一的方法。当时，他想证明某类对象一定存在 —— 一种由相互连接的节点组成的网络。

奇特之处在于，他的证明并没有告诉人们该如何具体构造这个网络。相反，他证明：如果把所有可能的网络都考虑进来，并从中随机选取一个，那么选到具备目标性质的网络的概率大于零。换句话，满足条件的网络一定存在于某个地方，哪怕我们几乎不知道它长什么样。

埃尔德什的这一思路后来被称为「概率方法」，它简单却极具革命性。

苏黎世联邦理工学院数学家 Benny Sudakov 表示，在这套方法出现之前，「如果我说某些对象存在，你会让我拿出来看看。」但有些对象太反常了，以至于人们很难直观理解它们竟然真的存在。

埃尔德什的方法绕开了这个难题，证明了随机性能够以数学家此前从未想象过的方式发挥作用。纽约大学的 Joel Spencer 表示：「用随机性来证明问题，这在当时简直令人震惊。今天，这已经成了基本操作。」

如今，概率方法已经被广泛用于数学和计算机科学：判断一个数是否为素数，设计更好的电路，或者在不引入偏差的情况下清洗数据。

研究者也从多个方向强化了这套方法。但是对于概率方法最初关注的问题，也就是埃尔德什当年想解决的网络问题，进展却一直有限。八十年来，数学家几乎没能显著改进埃尔德什当初给出的解法。

现在，变化终于开始出现。

荒野中的声音

想象一个由节点组成的网络，也就是数学家所说的「图」。在这个图里，每一对节点之间都由一条边相连。

现在，把每条边染成红色或蓝色，但有一个限制：不能出现一大簇节点，使得这些节点之间的所有连边都是同一种颜色。这样的禁忌结构被称为「单色团」。下面这个由三个节点组成的单色团，数学家称之为大小为 3 的团。

只要图里的节点足够多，无论你怎样给边上色，都不可能完全避开单色团。举个例子，如果你想避开大小为 3 的单色团，那么这个图最多只能有 5 个节点。一旦节点数达到 6 个，就必然会出现这样的结构。

因此，数学家把大小为 3 的团对应的「拉姆齐数」记作 R (3)，其值为 6。拉姆齐数衡量的是：一个图可以大到什么程度，才会不可避免地出现某种被禁止的结构。

红色团和蓝色团也可以设定为不同大小。比如，我们可以给一个 8 个节点的图上色，使其中既没有大小为 3 的红色团，也没有大小为 4 的蓝色团。但只要再增加一个节点，就必然会出现至少一个红色团或蓝色团。因此，拉姆齐数 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 仍抱有希望。他们先在较小的图上测试了这一方法，结果显示它似乎有效：在生成的数万种糟糕上色中，仍然存在非零概率得到一种好的、无团的上色。这让他们相信，即便面对大得多的图，这种收益也可能超过代价。

接下来，他们开始尝试证明这一点。关键恰恰来自高维球面那种非常反直觉的几何性质。

归根结底，为了证明可以避开某个特定大小的团，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/