内容来源：https://www.quantamagazine.org/after-80-years-mathematicians-give-famed-erdos-method-an-upgrade-20260626/

内容总结：

80年来首次突破：数学家改进埃尔德什概率方法，推动拉姆齐数研究获重大进展

1947年，匈牙利数学家保罗·埃尔德什提出了一项革命性的数学工具——概率方法。该方法不通过具体构造来证明某种数学对象的存在，而是通过证明随机选取的对象满足条件的概率大于零，从而断言该对象必然存在。这一思路在当时令学界震惊，如今已成为数学和计算机科学领域的基础工具，广泛应用于素数判定、电路设计和数据清洗等方向。

然而，80年来，埃尔德什最初应用该方法时关注的拉姆齐数问题——尤其是“对角拉姆齐数”（红蓝团大小相等的情况）——几乎未取得实质性突破。直到2025年，这一局面终于被打破。

几何方法破局

来自清华大学的研究生沈吴杰（Wujie Shen）与导师马杰（Jie Ma）及另一位研究生谢圣杰（Shengjie Xie）合作，提出了一种结合高维球面几何的随机着色模型。传统方法采用完全随机的硬币抛掷决定边色，而新方法将图的节点随机放置在高维球面上，然后根据节点间距离着色：距离大于某阈值着红色，小于则着蓝色。

高维球面的奇特几何性质——如极小的体积、巨大的表面积以及几乎所有点都位于“赤道”附近——使得红色团（相距较远的节点簇）更难形成。尽管这种方法会增加蓝色团出现的概率，但研究团队通过精密计算证明，在蓝色团大于红色团的情况下，收益大于代价。

50年来首次改进

经过一年、长达40页的密集推导，该团队在2025年7月发表论文，将埃尔德什关于“近对角拉姆齐数”（红色团大小约为蓝色团一半）的下界从 $((\sqrt{5}+1)/2)^k$ 提升至 $((\sqrt{5}+1)/2 + 10^{-21})^k$。尽管数值提升微乎其微，但这标志着该领域50年来首次取得进展。

“这有点令人震惊——一个熟悉的方法竟然能解决一个熟悉的问题，”剑桥大学的朱利安·萨哈斯拉布德（Julian Sahasrabudhe）评价道，“它一直在我们眼前，却无人发现。”

后续影响

该成果迅速引发连锁反应。2025年12月，瑞士联邦理工学院的本尼·苏达科夫（Benny Sudakov）及其两名博士生大幅简化了该着色模型，进一步改进了下界。其他研究者也开始将其应用于三色拉姆齐数的估算。

“概率方法就像一个充满活力的思想游乐场，”苏达科夫说，“每一次新的改进都会在其他领域发挥作用。”

中文翻译：

80年后，数学家为著名的“埃尔德什方法”带来升级
（罗伯特·纽贝克为《量子杂志》供稿）
1947年，居无定所的匈牙利数学家保罗·埃尔德什提出了一种方法，后来成为数学中最强大的工具之一。他想证明某类特定对象的存在——在此例中，是一个由相互连接的节点构成的网络。但奇怪的是，他的证明并未说明如何构建这个网络。相反，他表明：如果你考虑所有可能的网络并随机选取一个，那么找到具备你所需性质的网络的概率大于零。这意味着，即便你对那个网络几乎一无所知，它也确实存在于某处。
埃尔德什的这种方法被称为“概率方法”，它简单却具有革命性。在这套方法问世之前，“如果我告诉你某些对象存在，你会对我说，‘展示给我看，’”苏黎世联邦理工学院的数学家本尼·苏达科夫说，“但有些对象太不寻常了，以至于我们很难相信它们竟然存在。”
埃尔德什的技巧克服了这一困难，展示了随机性能够以数学家们从未想象过的方式被运用。“你会使用随机性，这太令人震惊了，”纽约大学的乔尔·斯宾塞说，“而现在，这已是基础操作。”
今天，概率方法被广泛应用于数学和计算机科学领域——例如判断一个数是否为质数、设计更优的电路，或是在不引入偏差的情况下清理数据。
研究者们已在不同方面强化了这一技巧。但概率方法最初的焦点——埃尔德什试图解决的那个关于网络的问题——却鲜有进展。八十年来，数学家们始终无法在埃尔德什当年提出的解决方案上取得显著改进。
如今，情况终于开始改变了。

荒野中的声音
想象一个由节点构成的网络——即一张图——其中每一对节点都由一条边连接。
（马克·贝兰为《量子杂志》供图）
现在，将每条边涂成红色或蓝色，但有一个条件：不要创建任何由同色边连接而成的大型节点簇。这些被禁止的结构被称为“单色团”。这是一个由三个节点构成的单色团，数学家称之为大小为3的团：
如果你的图有足够多的节点，那么无论你如何给边着色，都无法避免产生一个单色团。例如，如果你想避免大小为3的团，你的图最多只能有五个节点。一个六节点的图则总会产生一个这样的团：
因此，数学家们说，大小为3的团对应的“拉姆齐数”，记作R(3)，等于6。拉姆齐数衡量的是：在禁止模式不可避免地出现之前，图可以大到什么程度。
你也可以定义红色和蓝色团大小不同的拉姆齐数。例如，你可以给一个八节点的图着色，使其既没有大小为3的红色团，也没有大小为4的蓝色团。但如果你在图里再加一个节点，就必然会强制产生至少一个红色或蓝色团。因此，拉姆齐数R(3,4)等于9。
随着你想要避免的团越来越大，问题也变得越来越难解决。数学家们只算出了少数几个最小的拉姆齐数。“要创造出完全没有结构的东西是非常困难的，”丹佛大学的保罗·霍恩说，“也许是因为我们是人类，容易受自身偏见影响。”
因此，数学家们花费了几十年时间，试图找到越来越精确的拉姆齐数近似值。这正是埃尔德什在1947年引入概率方法时所尝试的方向。他并未直接构建无团的图，而是考虑了给图着色的所有可能方式，然后证明其中至少存在某个非零比例的着色方式是无团的。
埃尔德什用这一论证证明了：如果你禁止大小为k的红色和蓝色团，那么拉姆齐数R(k)必然大于$latex \sqrt{2}^k$。红色和蓝色团大小相同的拉姆齐数被称为“对角拉姆齐数”。埃尔德什类似地也能为“非对角”拉姆齐数R(k, l)（即禁止大小为k的红色团和大小为l的蓝色团）给出一个下界。
这段证明只有寥寥几行。但它完全出人意料。
起初，数学家们不愿跟随他的思路。他们想要具体的例子。“很多年里，埃尔德什就像荒野中的声音，”斯宾塞说，“他用随机性得到了这些惊人的结果，而人们以前从未这样做过。”
但很快，概率方法就证明了自身的价值。如今，它已是“离散”数学（研究像图这样离散而非连续的对象）中最常用的技巧之一，并且已从数学渗透到物理学和计算机科学领域。“我认为，随机性恰好帮助我们触及了那些原本非常缥缈的东西，”霍恩说。
最近，数学家们已经能够改编埃尔德什的方法，在被禁止的团大小相差很大的情况下获得更好的拉姆齐数估计值。例如，2025年，霍恩和三位同事使用埃尔德什方法的更新版本，证明了R(3, l)（其中l可以任意大）的一个更精确的下界。（这项工作反过来又导致了图论领域的一项重大突破。）
（奥伯沃尔法赫数学研究所档案 ©加布里埃拉·博洛巴什）
然而，当被禁止的团大小相差不大时——特别是埃尔德什最初关注的对角拉姆齐数——概率方法就停滞不前了。假设你禁止大小为1000的团。埃尔德什证明了R(1000)必然大于约2500。八十年的努力将这个界限提高到了约2501。类似地，从20世纪70年代起，在红色和蓝色团都相对较大的非对角拉姆齐数方面，进展也一直原地踏步。
这时，一位对拉姆齐理论几乎毫无经验的研究生出现了。

相关着色
吴杰·沈在清华大学的前几个学期主要专注于几何与拓扑学。但在2024年春天，他偶然读到一篇关于拉姆齐数的论文，并被深深吸引。
他知道埃尔德什方法的工作原理：通过抛硬币来决定图中每条边的颜色——正面朝上，边为红色；反面朝上，边为蓝色。然后计算出得到无团着色的概率。但对于较大的图，这种计算变得非常困难。沈想知道是否存在一种随机模型，能比埃尔德什的方法更高效地产生无团着色。
考虑到沈的训练背景，他提出的模型涉及几何或许并不令人意外。通常，图的着色不涉及几何：数学家关心的只是哪些节点由红色边连接，哪些由蓝色边连接。这些节点是彼此靠近还是分散在空间中并不重要。
但沈想利用几何来帮助他决定哪些边涂成红色，哪些边涂成蓝色。具体来说，他想利用高维球面的几何——即所有点到一个中心点的距离都相等的点集。
这些球面“完全颠覆了我们所有的直觉，”加州理工学院的戴维·康伦说。我们关于球面外观的许多假设在高维空间中都不再成立：高维球面体积极小、表面积巨大，而且大部分点都位于赤道上。“处理起来相当复杂，”苏达科夫说。
但沈和两位同事——当时访问清华教授秋季课程的杰·马以及马的研究生谢生杰——想要尝试一下。他们的方法是：首先，将节点逐一放置到高维球面的表面。每个节点的位置随机选择——球面上的任何点都是候选点，且每个节点的位置不影响其他节点的位置。
放置好所有节点后，根据节点之间的距离给每条边着色。如果两个点之间的距离大于某个固定值（这发生的概率小于1/2），则将连接它们的边涂成红色。如果它们靠得更近，则将边涂成蓝色。
通过这种方法，马、沈和谢创建的图形成红色团的可能性更小。这是因为要形成一个大的红色团，需要许多彼此相距很远的节点。球面上的空间有限，这种情况不太可能发生。
但这里有一个问题。出于同样的原因，与埃尔德什的方法相比，这种方法产生的含有蓝色团的着色比例更大。“这看起来像是一种权衡——对一种颜色很有帮助，但对另一种颜色却毫无裨益，”康伦说，“何必费这个功夫呢？”
即便如此，马、沈和谢仍抱有希望。他们在较小的图上测试了该方法，似乎有效：在它产生的数万种糟糕着色中，仍然存在非零概率得到一个良好的无团着色。这让他们确信，即使对于大得多的图，收益也可能超过成本。
随后，他们着手证明这一点。关键最终落在了高维球面极其怪异的几何性质上。
最终，为了证明他们能够避免特定大小的团，马、沈和谢需要限制随机放置的节点形成彼此相距很远或全部靠得很近的簇的概率。他们意识到，如果从每个节点向球心画一条线，这些线几乎全部会相互垂直或接近垂直。如果你在一个熟悉的二维球面上随机放置节点，这种情况不会发生：大多数节点不会位于垂直线上。但该团队能够证明，在他们所处理的更高维度空间中，这是成立的。
这反过来又限制了节点之间可能的最大距离——从而降低了它们形成单色团的机会。
经过一年时间和40页密集的计算，这三位研究者在2025年7月发表了他们的论文。他们改进了埃尔德什关于拉姆齐数的下界——但仅限于被禁止的蓝色团大于红色团的情况。当蓝色团和红色团一样小时，新方法的优势便消失了。
不过，当你想要避免的红色团大小，比方说，只有蓝色团的一半时，马、沈和谢设法将埃尔德什的增长率从$latex ((\sqrt{5} + 1)/2)^k$ 提升到了$latex ((\sqrt{5} + 1)/2 + 10^{-21})^k$。虽然变化微乎其微，但他们的证明标志着50年来近对角拉姆齐数首次得到改进。
“这很幸运，我们觉得所有的努力都得到了回报，”马说，“但这个过程很长时间里都很艰难。”
“一个熟悉的东西竟然能解决一个熟悉的问题，这有点令人震惊，”剑桥大学的朱利安·萨哈斯拉布赫说。他认为他们的技巧“就藏在眼皮底下”。

概率方法的游乐场
马、沈和谢的证明已经引发了一系列后续进展。2025年12月，苏达科夫和他的两名研究生大幅简化了该团队的着色模型，进一步改进了他们的新界限。此后，其他人已使用该模型来估计涉及三种颜色（而非两种）的拉姆齐数。
这与概率方法的悠久历史一脉相承。在过去的80年里，数学家们一直在调整埃尔德什基于随机性的技巧，找到越来越多融入额外结构的方法以增强其威力。而这些新技术随后又不可避免地被他处证明有用。“这是一个硕果累累的思想游乐场，”苏达科夫说。
因此，马、沈和谢的工作是这段跨越数十年故事的最新篇章。但这也是很长时间以来，首次有人重新审视近对角拉姆齐数。
该团队的新贡献——一种几何方法——可能会在这个棘手问题上带来更多进展。尽管概率方法尚未臻至完美，“但它现在确实非常强大，”斯宾塞说，“它真的改变了太多。”

英文来源：

After 80 Years, Mathematicians Give Famed ‘Erdős Method’ an Upgrade
Robert Neubecker for Quanta Magazine
In 1947, Paul Erdős, the itinerant Hungarian mathematician, introduced what would become one of math’s most powerful tools. He wanted to prove that a certain kind of object existed — in this case, a network made of interconnected nodes. But strangely, his proof didn’t specify how to build it. Instead, he showed that if you consider all networks and select one at random, the chances that you’ll find a network with the property you want is greater than zero. That means that the desired network is out there somewhere, even if you know almost nothing about it.
Erdős’ approach, known as the probabilistic method, was simple but revolutionary. Before its development, “if I’m telling you that certain objects exist, you would tell me, ‘Show me,’” said Benny Sudakov, a mathematician at the Swiss Federal Institute of Technology Zurich. “But certain objects are so unusual that it’s hard for us to grasp that they exist at all.”
Erdős’ technique overcame this difficulty, demonstrating that randomness could be used in ways mathematicians had never imagined. “It was just astounding that you would use randomness,” said Joel Spencer of New York University. “Now, that’s the baseline.”
Today, the probabilistic method is used across mathematics and computer science — to figure out if a number is prime, to design better circuits, or to clean up data without introducing biases.
Researchers have strengthened the technique in various ways. But the original focus of the probabilistic method — the question about networks that Erdős sought to answer — has seen very little progress. For eight decades, mathematicians were unable to significantly improve on the solution that Erdős came up with.
That’s now finally starting to change.
A Voice in the Wilderness
Imagine a network of nodes — a graph — in which every pair of nodes is connected by an edge.
Mark Belan/Quanta Magazine
Now color each edge either red or blue, but with one caveat: Don’t create any large clusters of nodes that are all connected by edges of the same color. These forbidden structures are called monochromatic cliques. Here’s a monochromatic clique consisting of three nodes, which mathematicians call a clique of size 3:
If your graph has enough nodes, it will be impossible to avoid creating a monochromatic clique, no matter how you color the edges. For instance, if you want to avoid a clique of size 3, your graph can have at most five nodes. A six-node graph will always have one:
Mathematicians therefore say that the “Ramsey number” for a clique of size 3, denoted R(3), is 6. Ramsey numbers measure how big graphs can get before the forbidden pattern inevitably emerges.
You can also have Ramsey numbers for red and blue cliques of different sizes. For example, you can color an eight-node graph so that it has no red cliques of size 3 or blue cliques of size 4. But if you add one more node to your graph, you will be forced to create at least one red or blue clique. Therefore, the Ramsey number R(3, 4) is 9.
As the cliques you want to avoid get bigger, the problem gets more and more difficult to solve. Mathematicians have been able to calculate only a handful of the smallest Ramsey numbers. “It’s very hard to create something that has no structure,” said Paul Horn of the University of Denver. “Maybe it’s because we’re human and we’re subject to our biases.”
And so mathematicians have spent decades trying to find better and better approximations of Ramsey numbers. That’s what Erdős was trying to do when he introduced his probabilistic method in 1947. Instead of building clique-free graphs directly, he considered every possible way to color a graph, then showed that at least some nonzero fraction of them must be clique-free.
Erdős used this argument to prove that, if you forbid red and blue cliques of size k, the Ramsey number R(k) must be bigger than $latex \sqrt{2}^k$. Ramsey numbers for same-size red and blue cliques are called diagonal Ramsey numbers. Erdős could similarly get a lower bound on “off-diagonal” Ramsey numbers R(k, l), in which you forbid red cliques of size k and blue cliques of size l.
The proof was just a few lines long. But it was completely unexpected.
At first, mathematicians were loath to follow his lead. They wanted concrete examples. “For many years, Erdős was like a voice in the wilderness,” Spencer said. “He was getting these amazing results using randomness, and people had never done that before.”
But soon the probabilistic method proved its worth. It’s now one of the most ubiquitous techniques in “discrete” math, the study of objects (like graphs) that are separate rather than continuous. And it has seeped out of math into physics and computer science. “The randomness, I think, just helps us get at something that is otherwise very ethereal,” Horn said.
More recently, mathematicians have been able to adapt Erdős’ method to get better estimates of Ramsey numbers where the forbidden cliques differ vastly in size. For instance, in 2025 Horn and three colleagues used an updated version of Erdős’ method to prove a more precise lower bound for R(3, l), where l grows arbitrarily large. (That work, in turn, led to a major breakthrough in graph theory.)
Archives of the Mathematisches Forschungsinstitut Oberwolfach ©Gabriella Bollobas
But when it came to Ramsey numbers where the forbidden cliques weren’t so different in size — particularly diagonal Ramsey numbers, the object of Erdős’ original interest — the probabilistic method stalled. Say you forbid cliques of size 1,000. Erdős showed that R(1,000) must be bigger than about 2500. Eight decades of effort changed that bound to about 2501. Similarly, from the 1970s onward, progress remained stock-still for off-diagonal Ramsey numbers where the forbidden red and blue cliques are both relatively large.
Then along came a graduate student with barely any expertise in Ramsey theory.
Correlated Coloring
Wujie Shen had spent his first few semesters at Tsinghua University focused mainly on geometry and topology. But in the spring of 2024, he came across a paper on Ramsey numbers that captivated him.
He knew how Erdős’ method worked: You flip a coin to determine the color of each edge of your graph: Heads, the edge is red; tails, it’s blue. You then calculate the probability that you’ll get a clique-free coloring. But this calculation gets very difficult for larger graphs. Shen wondered whether there was a random model that could produce clique-free colorings more efficiently than Erdős’ approach.
Given Shen’s training, it’s perhaps no surprise that the model he came up with involved geometry. Typically, graph colorings don’t invoke geometry: All that matters to mathematicians is which nodes are connected by a red edge, and which are connected by a blue one. Whether those nodes sit close together or are scattered throughout space has no significance.
But Shen wanted to use geometry to help him decide which edges to color red and which to color blue. In particular, he wanted to use the geometry of high-dimensional spheres — that is, sets of points that are equidistant from a single central point.
These spheres “mess with all our intuitions completely,” said David Conlon of the California Institute of Technology. Many of our assumptions about what a sphere looks like are no longer true in high dimensions: A high-dimensional sphere has a tiny volume and massive surface area, and most of its points lie on the equator. It’s “pretty complicated to work with,” Sudakov said.
But Shen and two colleagues — Jie Ma, who was visiting Tsinghua to teach for the fall term, and Ma’s graduate student Shengjie Xie — wanted to try. Their method: First, place nodes one by one onto the surface of a high-dimensional sphere. Choose each node’s position at random — any point on the sphere is fair game, and the placement of each node has no influence over the placement of any other node.
Once you’ve placed all the nodes, color each edge based on the distance between the nodes. If two points are more than some fixed distance apart (which will happen with a probability of less than 1/2), color the edge connecting them red. If they’re closer together, color the edge blue.
With this approach, the graphs that Ma, Shen, and Xie created were less likely to form a red clique. That’s because to form a large red clique, you need many nodes that are all far away from one another. With only so much space on the sphere, this is unlikely to happen.
But there’s a catch. By the same token, this method also produces a greater fraction of colorings that have blue cliques than Erdős’ does. “There’s a trade-off that looks like it really helps in one color, but it doesn’t help at all in the other color,” Conlon said. “Why bother?”
Even so, Ma, Shen, and Xie were hopeful. They tested their method on smaller graphs, and it seemed to work: Among the tens of thousands of bad colorings it generated, there was still a nonzero chance of getting a good clique-free coloring as well. That reassured them that the benefits could outweigh the costs, even for much bigger graphs.
They then set out to prove it. The key turned out to be the very weird geometry of high-dimensional spheres.
Ultimately, to show that they could avoid cliques of a particular size, Ma, Shen, and Xie needed to limit the probability that their randomly placed nodes formed clusters that were all far apart, or all close together. They realized that if they drew lines from each node to the sphere’s center, those lines would almost all be perpendicular or close to perpendicular. That doesn’t happen if you randomly place nodes on a familiar two-dimensional sphere: Most nodes will not lie on perpendicular lines. But the team was able to prove that it was true in the much higher dimensions that they were working in.
That, in turn, restricted how far nodes could be from one another — thereby limiting their chances of forming a monochromatic clique.
After a year and 40 pages of dense computations, the trio posted their paper in July 2025. They’d improved Erdős’ lower bound on Ramsey numbers — but only when the forbidden blue cliques are larger than the red ones. When the blue cliques are just as small as the red ones, the benefits of the new approach disappear.
Still, when you want to avoid red cliques that are, say, half as large as blue ones, Ma, Shen, and Xie managed to nudge Erdős’ growth rate of $latex ((\sqrt{5} + 1)/2)^k$ up to $latex ((\sqrt{5} + 1)/2 + 10^{-21})^k$. While the change is tiny, their proof marks the first improvement for near-diagonal Ramsey numbers in 50 years.
“It’s lucky, and we feel like all our efforts are rewarded,” Ma said. “But it was tough for a long time.”
“It’s a bit shocking that a familiar thing works for a familiar problem,” said Julian Sahasrabudhe of the University of Cambridge. Their technique, he said, “was hidden in plain view.”
The Probabilistic Playground
Ma, Shen, and Xie’s proof has already generated a spate of further progress. In December 2025, Sudakov and two of his graduate students drastically simplified the team’s coloring model, improving their new bounds even further. Others have since used the model to estimate Ramsey numbers that involve three colors, not two.
That’s in keeping with the probabilistic method’s long history. For the past 80 years, mathematicians have been tinkering with Erdős’ randomness-based technique, finding more and more ways to mix in additional structure to boost its power. Inevitably, these new techniques have then proved useful elsewhere. “It’s a very fruitful playground for ideas,” Sudakov said.
Ma, Shen, and Xie’s work, then, is the latest chapter in this decades-old story. But it’s also the first one in a long time to revisit the near-diagonal Ramsey numbers.
The team’s new contribution — a geometric approach — might lead to more progress on that stubborn problem. Although the probabilistic method hasn’t been perfected yet, “it’s really very powerful now,” Spencer said. “It’s really changed so much.”