新智元報道

編輯：KingHZ

陶哲軒的伯樂Erd?s，有則關于外星人為難全人類的數(shù)學寓言，喻示Ramsey數(shù)計算之難。2025年，三位中國數(shù)學家的arxiv論文為某類Ramsey數(shù)注入新希望。

1947年，陶哲軒的伯樂Erd?s提出了組合數(shù)學中Ramsey數(shù)下界。

10歲的陶哲軒和Erd?s

最近，國內的馬杰等三位研究人員聯(lián)手帶來了首次指數(shù)級改進。

他們公布了一篇arxiv新論文展示了這一領域的驚人進展：

論文鏈接：https://arxiv.org/abs/2507.12926

數(shù)學家、計算機科學家Gil Kalai表示改進令人驚嘆！

什么是Ramsey數(shù)？

在近百年前，英國邏輯學家Frank Ramsey就證明了這樣一個有趣的結論：

在一個六人聚會中，無論這六人之間的關系如何，總能找到三人彼此相識，或者三人互不相識。

Frank Ramsey（1903–1930）英年早逝，年僅26歲。除了數(shù)學，在哲學上，他成就斐然，被公認為二十世紀最重要和最具影響力的思想家之一

這個簡單而直觀的例子，正是Ramsey理論的最早雛形。

當圖中的節(jié)點數(shù)量不斷增加時，圖中就會出現(xiàn)越來越復雜的結構。而在整數(shù)序列中，也會自然浮現(xiàn)出類似的有序模式。

荷蘭數(shù)學家兼數(shù)學史學家Bartel Leendert van der Waerden曾經證明：即使是一組看似隨機的整數(shù)，也必然會出現(xiàn)某種等差數(shù)列結構。

這種現(xiàn)象揭示了Ramsey理論的核心思想：

當元素數(shù)量足夠多時，某些有序模式的出現(xiàn)將變得不可避免。也就是說，混亂之中也會自發(fā)地產生秩序。

Ramsey數(shù)就是關于圖論中有序模式：

Ramsey數(shù)用于衡量圖論中圖的規(guī)模——圖在變大到某個程度后，某些特定的模式將不可避免地出現(xiàn)。

比如，將五個頂點兩兩相連，構成一個完全圖（即每個頂點都與其余所有頂點相連）。在五個頂點的完全圖中，我們可以把每條邊涂成紅色或藍色，并且仍然可以避免出現(xiàn)三個頂點之間的所有邊顏色相同的情況。

但如果是六個頂點，無論如何著色，都會不可避免地出現(xiàn)三個頂點之間的邊顏色相同的情形。

對于使用兩種顏色，并要求圖中不出現(xiàn)大小為3的同色完全子圖（clique），對應的Ramsey數(shù)R(3，3)是6。上圖標出了一個由三個頂點組成的單色團。

換句話，在一個聚會中，可以保證其中三個人之前已經見過面，而另外三個人彼此都不認識，最低只需要6個人。但如果將總數(shù)減少到五個，這種確定性就會消失。

宇宙級難題

然而，數(shù)學家們發(fā)現(xiàn)，要確定到底在哪個點這些模式一定會出現(xiàn)，也就是找到這個「臨界閾值」，極其困難。除了最簡單的情形，目前幾乎都無法精確計算出來。

Ramsey數(shù)R(a，b)的一些已知值

例如，R(5,5) 是一個代表性的問題，表示圖中一定會出現(xiàn)紅色或藍色的五邊形結構。其精確值仍未確定，當前僅知其介于43和48之間。

在研究Ramsey數(shù)的圈內，流傳著一個廣為人知的寓言，通常被認為出自Erd?s，用來形象地說明這個問題的難度增長有多么迅猛。

寓言是這樣的：

有一天，外星人入侵地球。他們提出條件：只要人類能算出一個正確的Ramsey數(shù)，他們就放過地球。

如果他們問的是Ramsey數(shù)R（5，5），我們應該立刻動員整個人類文明的計算能力，全力以赴去求解它。

但如果他們問的是R（6，6）——那最好放棄幻想，準備斗爭。

盡管如此，數(shù)學家仍不斷嘗試推進上界和下界的收斂，并在過程中探索新的證明策略。

Erd?s與合作者曾開創(chuàng)性地用概率推斷圖中結構的出現(xiàn)，從而避免上界過大。這些方法不僅極大推動了數(shù)學，也為算法設計帶來了突破。

拉姆齊原理的魅力在于它的普適性：從數(shù)論到計算機科學，從圖論到邏輯學和幾何學，這一理論的深遠影響幾乎遍布整個數(shù)學世界

天才數(shù)學家的方法

Erd?s，匈牙利數(shù)學家，1913年3月26日—1996年9月20日，在數(shù)論和計算機科學等多個領域做出了重要貢獻。

Erd?s，中文名全稱為埃爾德什·帕爾，原名Erd?s Pál，英語名Paul Erd?s。他發(fā)表論文高達1525篇（包括與人合寫的），是目前發(fā)表論文數(shù)最多的數(shù)學家（其次是歐拉）；曾和511人合寫論文。

Erd?s成功的關鍵公式：數(shù)學家+數(shù)學家+數(shù)學家=更多、更好的數(shù)學

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數(shù)的技巧分為5大步：

（1）假設從一個包含10個頂點的完全圖出發(fā)。如果我們用3種顏色（例如紅、藍、黃）隨機為每條邊染色，那么圖中是否總會出現(xiàn)5個頂點，其中的10條邊都被染成相同顏色？

（2）每條邊被染成紅色的概率是1/3。

（3）因此，10條邊都恰好為紅色的概率是 (1/3)1?。

（4）由于我們有3種顏色，任何一種都可能形成一個單色團(clique)。

（5）而10個頂點中可能組成的5-點子集（也就是5-點團）共有252種組合方式。

所以，出現(xiàn)任意顏色的5點單色團的總體概率不超過：(1/3)1?×3×252小于1。

上圖中高亮顯示了一個滿足該條件的紅色子圖：由5個頂點和10條紅色邊組成的紅色團（完全子圖）。

這就是所謂的并集界（union bound）：它估算的是在隨機染色下生成單色團的可能性。由于這個值小于1，意味著在某些情況下，10個頂點的圖可以**不包含**任意顏色的 5 點單色團。

所以我們可以得出結論：這個Ramsey數(shù)（表示5點單色團必然出現(xiàn)的最小頂點數(shù)）一定大于10。

持續(xù)的挑戰(zhàn)

Erd?s等人幾十年前提出的概率方法，基于隨機圖中出現(xiàn)目標結構的可能性，并結合一些數(shù)學公理，得出較為合理的上界。這一思路不僅成功運行了近百年，還推動了算法中隨機性使用的發(fā)展。

馬里蘭大學計算機科學教授William Gasarch指出，這些概率技術已經被用于網絡路由算法，以及理論計算機科學的核心問題中。

路由算法可以在多個節(jié)點間隨機選擇路徑，從而避免窮舉整個網絡來尋找最優(yōu)結構。

1980年代早期，清華「姚班之父」、圖靈獎得主姚期智證明了，在數(shù)據(jù)表達到一定大小后，其行必須進行排序，才能避免訪問效率的下降，這也是Ramsey理論在計算機應用中的一個典型實例。

然而，數(shù)學家們逐漸意識到，純粹的概率方法存在局限。這促使他們轉向新的方法：構造遵循明確規(guī)則的圖結構，以人為避免某些clique的出現(xiàn)，直到其變得不可避免。與完全依賴隨機過程相比，這種構造方法在某些情境下可能更有效。

三十多年前，普林斯頓大學數(shù)學教授Noga Alon提出了一種確定性構造無三角形圖（triangle-free graph）的方法，取得了成功。但更大規(guī)模圖的構造仍缺乏穩(wěn)定可靠的手段，因此隨機生成仍是當前最有效的工具。

Mattheus與Verstraete借助有限幾何中的工具，對 R(4,t) 的上界進行了深入研究。他們設法從初始偽隨機圖中剔除所有四節(jié)點clique，并在此基礎上構造了一個證明，展示了隨著t的增加，其上界如何增長。

論文鏈接：https://arxiv.org/abs/2306.04007

2023年，數(shù)學家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)指數(shù)級的改進。

論文鏈接：https://arxiv.org/abs/2505.13371

而關于更一般的Ramsey數(shù)的下界，最佳記錄是1974年Joel Spencer提出的。

論文鏈接：https://www.sciencedirect.com/science/article/pii/0097316575900710

超越Ramsey理論

由 Jie Ma、Wujie Shen和Shengjie Xie撰寫的論文中引入并研究了一類幾何隨機圖模型。這類模型本身就具有較高的研究價值，甚至超出了Ramsey理論的范疇。

正如作者所指出的，目前仍無法確定在C=1的情況下是否能獲得比 Erd?s 1947年構造更優(yōu)的下界。

研究當C→1時的情況以及?如何依賴于C，也是一個有趣的問題。

我們是否能超越Erd?s早期構造，仍然是一個懸而未決的問題。

數(shù)學家、計算機科學家Gil Kalai表示：論文中所考慮的隨機模型令人印象深刻。

在d維球面上隨機選擇n個點。

設置一個閾值，并根據(jù)兩點之間的距離是否低于該閾值，將它們之間的邊染色為藍色或紅色。

閾值的選擇使得邊是紅色的概率為p（因此邊是藍色的概率為1-p）。

這一模型與Erd?s–Rényi模型 G(n,p) 有些相似，但增加了微妙的相互依賴性。與G(n,p)模型相比，這些細微的依賴關系導致紅色和藍色大團的預期數(shù)量（或僅是概率）減少，如何理解這一機制將是一個有趣的課題。

論文的關鍵貢獻在于復雜的分析過程，涉及選擇維度d以及計算最大紅色和藍色團的大小。

作者介紹

馬杰現(xiàn)任清華大學丘成桐數(shù)學科學中心教授和北京雁棲湖應用數(shù)學研究院教授。2011年從佐治亞理工學院數(shù)學學院獲得博士學位，之后在Benny Sudakov教授指導下在加州大學洛杉磯分校數(shù)學系擔任Hedrick助理教授兩年，后任卡內基梅隆大學數(shù)學科學系博士后研究員，及中國科技大學數(shù)學科學學院教授。馬杰的主要研究興趣是極值組合學和圖論。他獲得了國家自然科學基金杰出青年科學基金的資助。

參考資料：

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/