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

10歲的陶哲軒和Erd?s

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

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

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

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

什么是Ramsey數？

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

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

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

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

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

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

這種現象揭示了Ramsey理論的核心思想：

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

Ramsey數就是關于圖論中有序模式：

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

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

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

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

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

宇宙級難題

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

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

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

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

寓言是這樣的：

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

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

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

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

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

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

天才數學家的方法

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

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

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

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

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

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

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

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

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

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

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

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

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

持續的挑戰

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

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

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

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

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

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

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

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

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

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

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

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

超越Ramsey理論

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

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

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

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

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

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

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

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

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

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

作者介紹

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