一個著名數學問題的新進展

上世紀20年代，數學家弗蘭克·拉姆齊（Frank Ramsey）提出拉姆齊數的概念，這個看似簡單的概念，所涉及的卻是組合學中異常困難的問題。

拉姆齊數催生了一個被稱爲拉姆齊理論的領域，這個領域關注於探討諸如“某個集合需要多大，才能保證出現某個結構”的問題。自20世紀30年代以來，數學家在探索拉姆齊問題方面，幾乎沒有取得任何可觀的進展。

現在，數學家Jacques Verstraete和Sam matthews向預印網站arXiv上提交了一篇新的論文，表示他們找到了一個困擾了數學界90多年的拉姆齊問題——r(4, t)的近似答案。

拉姆齊數與拉姆齊問題

什麼是r(4, t)問題？或許我們要先從拉姆齊數說起。

拉姆齊數與單色團概念有關，我們可以通過一個實例來直觀地理解拉姆齊數和單色團：將一個有着5個頂點的圖的每個點都用線段兩兩相連，那麼我們會發現，用10條線段就可以完成這一步，得到一個5個頂點的完全圖（所有頂點都兩兩相連的圖）。接着，將每條邊塗成綠色或橙色兩種不同的顏色。

用兩種不同顏色爲由5個頂點連接而成的完全圖的邊着色，是有可能避免出現3個頂點由相同顏色的邊連接而成的情況的。（圖/原理）

現在，問題來了，我們是否可以避免出現3個頂點是用相同顏色的邊連接而成的？對於有着5個頂點的完全圖來說，問題的答案是肯定的。

接着，讓我們將點數從5增加到6。同樣，形成一個6個頂點的完全圖需要15條邊將這些點兩兩相連，並同樣也給這15條邊分別塗上綠色或橙色。這時，當我們再去探討相同的問題時，會發現無論採用什麼方法，都不可避免地會得到3個由相同顏色的邊相互連接的點。

6個頂點的完全圖，如果用兩種不同顏色爲其邊着色，必然會出現3個頂點由相同顏色的邊連接而成的情況。（圖/原理）

這些被相同顏色相連的點，就是單色團。它表示，對於顏色數量爲2、大小爲3的單色團來說，拉姆齊數爲6。它意味着你需要一個至少包含6個頂點的完全圖，才能保證這樣一個單色團存在。

其實，這個問題還有一個更簡單易懂的表達方式，那就是所謂的r(3, 3)派對問題：在一個r人蔘加的派對中，如果至少要有3個人彼此認識，或者3個人彼此都不認識，那麼滿足該條件的最小r(3, 3)是多少？從上面的圖中，我們知道，r(3, 3)的答案是6。

在數學家知曉了r(3, 3) = 6之後，他們試圖求解r(4, 4)、r(5, 5)……等於多少。r(4, 4)的解是18，它是用Paul Erdös和George Szekeres在20世紀30年代創造的一個定理證明的；而r(5, 5)目前仍然未知。事實上，隨着單色團的數字增大，拉姆齊數的計算變得越來越複雜。

上界和下界的估計值

爲什麼看似如此簡單的問題這麼難以解決？

事實證明，它比看起來要複雜得多。比如，假設數學家知道r(5,5)的解在40~50之間，如果從45開始，那麼需要考慮的圖就有超過10234種！這是個令人難以想象的數字，所以數學家很難找到精確的結果，只能進行估計，給出一個可能的取值範圍，確保一個任意大小的團的拉姆齊數在某個上界和下界之間。

這也是Verstraete和matthews在新工作中所取得的進展。他們的工作與r(4,t)問題有關，其中4表示必存在用第一種顏色相連的四個點，t表示必存在用另一種顏色相連的頂點數(對應在派對問題中，即爲必存在4個相互認識的人，或t個相互不認識的人)。這個問題已經困擾數學家90多年。

大約四年前，Verstraete與數學家Dhruv Mubayi在研究另一個拉姆齊問題時，發現所謂的僞隨機圖可以推進對這些問題的現有認知。

1937年，Erdös發現使用隨機圖可以爲拉姆齊問題提供很好的下界。Verstraete和Mubayi發現，頻繁地從僞隨機圖中取樣，通常能比隨機圖給出更好的拉姆齊數邊界，可以進一步收緊他們的取值範圍。

2019年，Verstraete和Mubayi使用僞隨機圖求解了r(3,t)。但是，Verstraete難以構建一個有助於求解r(4, t)的僞隨機圖。於是他開始涉足組合學之外的數學領域，比如有限幾何、代數和概率論。最終，他遇到了有限幾何領域的專家，Mattheus。

近似值：t的三次函數

他們發現，Verstraete所需要的僞隨機圖，可以在有限幾何中找到。在得到了有助於求解r(4, t)的僞隨機圖後，仍存在一些其他的數學問題有待解決。最終，他們用了將近一年的時間來處理這些問題，得出了一個近似解：r(4, t)近似於一個t的三次函數。

用派對問題的語言可以被表述爲，如果想要在一個聚會總是有4個人彼此都認識，或者t個人彼此完全不認識，那麼大約需要t³人在場。需要特別強調的是，是“大約t³人”，這只是一個非常接近真實情況的估計值，而非一切的答案。

#創作團隊：

撰文：佐佑

排版：雯雯

#參考來源：

https://today.ucsd.edu/story/ramsey-problems

https://arxiv.org/pdf/2306.04007.pdf

https://www.quantamagazine.org/after-nearly-a-century-a-new-limit-for-patterns-in-graphs-20230502/

#圖片來源：

封面圖&首圖：Jacques Verstraete via ucsd.edu

來源：原理

編輯：悅悅

轉載內容僅代表作者觀點

不代表中科院物理所立場

如需轉載請聯繫原公衆號

1.2.

3.

4.

5.

6.

7.

8.

9.

10.