新智元報道

編輯：KingHZ

【新智元導(dǎo)讀】陶哲軒的伯樂Erd?s，有則關(guān)于外星人為難全人類的數(shù)學(xué)寓言，喻示Ramsey數(shù)計算之難。2025年，三位中國數(shù)學(xué)家的arxiv論文為某類Ramsey數(shù)注入新希望。

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

10歲的陶哲軒和Erd?s

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

他們公布了一篇arxiv新論文展示了這一領(lǐng)域的驚人進(jìn)展：

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

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

什么是Ramsey數(shù)？

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

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

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

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

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

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

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

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

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

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

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

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

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

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

宇宙級難題

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

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

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

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

寓言是這樣的：

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

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

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

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

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

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

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

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

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

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

1947年，Erd?s提出的最初下界是通過隨機染色Kn得到的：每條邊以概率p被染成紅色，其他情況下染成藍(lán)色。

論文鏈接：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）假設(shè)從一個包含10個頂點的完全圖出發(fā)。如果我們用3種顏色（例如紅、藍(lán)、黃）隨機為每條邊染色，那么圖中是否總會出現(xiàn)5個頂點，其中的10條邊都被染成相同顏色？

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

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

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

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

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

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

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

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

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

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

馬里蘭大學(xué)計算機科學(xué)教授William Gasarch指出，這些概率技術(shù)已經(jīng)被用于網(wǎng)絡(luò)路由算法，以及理論計算機科學(xué)的核心問題中。

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

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

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

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

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

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

2023年，數(shù)學(xué)家Gil Kalai介紹過當(dāng)時取得的最新成果。

鏈接：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ù)級的改進(jìn)。

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

而關(guān)于更一般的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年構(gòu)造更優(yōu)的下界。

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

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

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

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

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

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

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

論文的關(guān)鍵貢獻(xiàn)在于復(fù)雜的分析過程，涉及選擇維度d以及計算最大紅色和藍(lán)色團(tuán)的大小。

作者介紹

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

參考資料：

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/