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

10歲的陶哲軒和Erd?s

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

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

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

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

什么是Ramsey數(shù)？

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

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

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

這個(gè)簡(jiǎn)單而直觀的例子，正是Ramsey理論的最早雛形。

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

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

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

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

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

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

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

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

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

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

宇宙級(jí)難題

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

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

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

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

寓言是這樣的：

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

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

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

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

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

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

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

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

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

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

1947年，Erd?s提出的最初下界是通過(guò)隨機(jī)染色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è)從一個(gè)包含10個(gè)頂點(diǎn)的完全圖出發(fā)。如果我們用3種顏色（例如紅、藍(lán)、黃）隨機(jī)為每條邊染色，那么圖中是否總會(huì)出現(xiàn)5個(gè)頂點(diǎn)，其中的10條邊都被染成相同顏色？

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

鏈接：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í)的改進(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撰寫(xiě)的論文中引入并研究了一類幾何隨機(jī)圖模型。這類模型本身就具有較高的研究?jī)r(jià)值，甚至超出了Ramsey理論的范疇。

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

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

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

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

在d維球面上隨機(jī)選擇n個(gè)點(diǎn)。

設(shè)置一個(gè)閾值，并根據(jù)兩點(diǎn)之間的距離是否低于該閾值，將它們之間的邊染色為藍(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ù)量（或僅是概率）減少，如何理解這一機(jī)制將是一個(gè)有趣的課題。

論文的關(guān)鍵貢獻(xiàn)在于復(fù)雜的分析過(guò)程，涉及選擇維度d以及計(jì)算最大紅色和藍(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é)系博士后研究員，及中國(guó)科技大學(xué)數(shù)學(xué)科學(xué)學(xué)院教授。馬杰的主要研究興趣是極值組合學(xué)和圖論。他獲得了國(guó)家自然科學(xué)基金杰出青年科學(xué)基金的資助。