機器之心編譯

數十年前，匈牙利數學家保羅?埃爾德什（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/