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

兩位數學家表示，他們找到了一個困擾數學界90多年的拉姆齊問題——r(4, t)的近似答案。

撰文 | 佐佑

上世紀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)問題有關，其中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^³人”，這只是一個非常接近真實情況的估計值，而非一個確切的答案。

參考來源：

[1] https://today.ucsd.edu/story/ramsey-problems

[2] https://arxiv.org/pdf/2306.04007.pdf

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

本文經授權轉載自微信公眾號“原理”。

特 別 提 示

1. 進入『返樸』微信公眾號底部菜單“精品專欄“，可查閲不同主題系列科普文章。

2. 『返樸』提供按月檢索文章功能。關注公眾號，回覆四位數組成的年份+月份，如“1903”，可獲取2019年3月的文章索引，以此類推。