張貼日期：Aug 03, 2015 2:38:36 PM

Complete disorder is impossible!

「完全失序是不可能的! 」，如果只能用一句話來描述拉姆西理論，沒有比這句話更到位的了。更精確的說，在一個大的系統裡，即便它非常複雜，還是肯定會有一部分形成一個特定的小系統，想避也避免不了。下面這個古老又經典的不得了的[633定理]，想必很多人都曾聽過吧。

任意六個人之中，必定會有三個人彼此互相認識，或者三個人彼此都不認識。

這裡的633跟馬總統的633不一樣啦，這裡的633隱藏了精采美妙的數學呢。用圖論(Graph Theory)的語言來描述的話，我們可以說:

六個頂點所形成的完全圖，將所有邊分別塗上紅色或藍色，

則必定會有一個紅色或者藍色的三角形。

完全圖 K_n (complete graph)指的是將 n 個頂點兩兩之間都互連一條邊的圖。

有個不知道誰發明的知名物理學家霍金在《時間簡史》一書中提到了一個科普理論 (感謝讀者單維彰教授熱心提供出處)，說科普書中包含一個數學式子，書的銷量就會少一半。換成在 Facebook 上的平行理論，應該就是按讚的人會少一半吧?! 有數學式子就這麼慘了，寫數學證明那還得了! 過去本人的科普文一概不提證明，就是害怕這個詛咒阿!! 但是由於這次的證明不太難，本人決定挑戰一下這個科普理論。

證明

從 6 個頂點中隨便挑一個點出來，稱 v 點，那麼只有兩種情況: v 點有大於或等於 3 條(a)紅色邊，或者(b)藍色邊。考慮(a)的情況，那麼連接紅色邊的這 3 個頂點，如果有兩點間有紅色邊連接，則這兩點和 v 將形成一個紅色三角形，得證；反之，如果任兩點間都是藍色邊，則這 3 個頂點就是一個藍色三角形。同理可證(b)的情況，得證。

拉姆西數

給定一個圖 H，所謂的拉姆西數 Ramsey number R(H)，就是最小的整數 m，使得將一個含 m 個點的完全圖 K_m的所有邊用兩種顏色(紅、藍)去塗，不論如何塗色，都還是保證會找到紅色的 H 或者藍色的 H 在 K_m 裡面。

用上述六人行的例子來看，就是 R(K₃) ≦ 6 ；事實上，6 就是最小的，5 個點會存在某種塗法都沒有同色的三角形，這個簡單的作業就留給讀者當練習囉。

拉姆西理論

Frank Plumpton Ramsey (22 February 1903 – 19 January 1930) 出生在英國劍橋，他的老爸也是位數學家，從小耳濡目染之下培養出對數學獨特的興趣。Ramsey 的興趣據說非常的廣泛，熱愛英國文學和古典事物，不只這樣，還是一個左派關懷弱勢型的政治魔人。年紀輕輕就展現各方面的才華，在 27 歲時卻因慢性肝病，驟然離世。Ramsey 留給世人最印象深刻的，其實是他在 1930 年論文裡的一個次要的引理，論文主要的研究對象是關於邏輯學，然而，沒想到這個引理後來被稱作拉姆西定理(Ramsey's Theorem)卻是一個非常豐富且深刻的數學理論 － 拉姆西理論(Ramsey Theory)的起源。

[拉姆西定理] 如果 H 是一個有限點的完全圖，那麼 R(H) 就是有限的。

直觀的來說，這個定理某種程度上解釋了，為何仰望星空能夠發現各式各樣的星座。意思就是，你隨便灑一些星星在天空中，可以透過將某些星星連起來，讓它看起來像是一頭獅子的形狀，只要星星多到超過 R(獅子)。

什麼?!! 星座居然跟數學理論扯上關係，這也太太太浪漫了吧~~

Ps. 上一集<數學羅曼史系列 - 幸福結局的幸福結局> 中 R(n, 5; 4) 的存在性，可以從拉姆西定理推廣得到。

以我接觸拉姆西理論的經驗來說，拉姆西理論留下的問題大部份都非常困難，這麼說好了，如果有研究生拿著題目來找我，說他決定碩士論文作這個，那我會叫他先回去洗洗睡，明天想清楚再來找我。拉姆西理論是一個非常具有挑戰性的領域，光是大數學家 Erdős 就留下了將近三四十個未解的難題，也許正是因為 Ramsey Theory 的難度太高，許多年來鮮少聽到有比較重大的研究進展。一直到今年，一個關於退化圖(degenerate graph)的猜想，被徹底解決了!

d-退化圖

一個圖如果稱為d-退化圖 (d-degenerate graph)，表示這個圖中所有的子圖(拿掉某些點或某些邊所成的圖)都會找到某一點剩下的鄰居數不超過 d 個；換句話說，一個d-退化圖可以藉由重覆[刪去鄰居數不超過 d 個的頂點]直到消失。著名的例子像是樹 (tree) 就是1-退化圖，因為 tree = [沒有迴圈且連通的圖]，既然沒有迴圈，就必定保證會有某一個頂點最多只有 1 個鄰居，將這個頂點拿走之後剩下的圖也必定還是[沒有迴圈且連通]，還是 tree，就又可以找到某一個頂點最多只有 1 個鄰居，將這個頂點拿走之後剩下的圖也必定還是[沒有迴圈且連通]，還是 tree..... 如此一直下去，很明顯 tree 滿足了 1-退化圖 的條件。

而1-退化圖必定是森林 (forest)，即把許多 tree 放在一起；平面圖 (planar graph) 則是 5-退化圖。

上面是從定義以及演算法上的意涵來解釋什麼是退化圖，提高到更一般的層次來看，所謂退化圖，即是

對於所有子圖的邊數跟點數之間保持著均勻的線性關係。

大多數的圖都沒有這樣好的性質，圖的邊數最多甚至可達到點數的平方規模。因此，退化系數 d 也可以看成為圖的稀疏性質(sparseness)的一個自然指標。

Burr-Erdős 猜想

在1973年，Burr 和 Erdős 提出了一個猜測:

對任意自然數 d，存在一個常數 c = c(d) 使得每一 n 個點的 d-退化圖 H 都滿足 R(H) ≦ cn

這個猜測之所以特別的地方，在於 H 若是一般圖，則 R(H) 的規模相較於點數是以指數型成長；若 H 限制為退化圖，則是線性的。而且，對於任意一個固定的 d，所有的 d-退化圖都滿足於同一個常數 c(d) 的上界。也就是只跟 d 有關，跟圖本身長甚麼樣子無關，這根本比即將上映的驚奇四超人還要驚奇阿阿阿!

在接下來的 40 年時間裡，有一些相關的進展，提供弱一點的估計，或者是針對特定的退化圖類，其中一個較為知名的結果是在 1983 年，Chvátal、Rödl、Szemerédi 和 Trotter 證明了這個漂亮的定理:

假設 H 的最大度(degree)是 Δ，存在一個常數 c = c(Δ) 使得每一 n 個點的 d-退化圖 H 都滿足 R(H) ≦ cn

之後，Chen 和 Schelp(1993)將[最大度是 Δ]的條件，弱化成[d-可排(d-arrangeable)]，改進了上述的結果，並且連帶證明了

所有平面圖都有線性的拉姆西數

像這樣子精彩的結論，實在是太美妙了。

from Choongbum Lee's page

今年五月十八日，來自韓國目前在 MIT 擔任 instructor 的 Choongbum Lee 博士，在 arXiv 掛了一篇論文 Ramsey numbers of degenerate graphs，解決了懸宕 40 多年的 Burr-Erdős 猜想，他的貢獻在 Ramsey Theory 取得了重大突破，在國際間吸引了非常多的討論，堪稱是今年組合數學界最重要的大新聞之一。