我們如何研究結構與隨機性之間的邊界？數學中充滿了這種現象，比如在非線性動力學和湧現過程的領域中。還有一些科學領域涉及混沌理論（Chaos Theory），比如氣候系統。在我看來，這就是數學和科學變得最有趣的地方！這個迷人的邊界可能出現在最意想不到的地方，比如被稱為圖論（graph theory）的高度結構化的數學領域。
如果你對圖論有所瞭解，這可能會讓你感到驚訝。這個數學的子領域充滿了嚴格的佈局和高度有序的網路。透過稍微改變規則，我們可以得到一個豐富而美麗的數學領域，它處理秩序與混沌的邊界。這就是所謂的拉姆齊理論（Ramsey Theory），以英國傑出的數學家弗蘭克·拉姆齊的名字命名。拉姆齊不幸在26歲時就去世了，但他的工作永遠改變了數學。
- 弗蘭克·拉姆齊，拉姆齊理論的創始人
維基百科對拉姆齊理論有一個有趣的定義。它被定義為一個數學領域
專注於秩序的出現
全文有更長的描述，但我喜歡這個摘錄。它幾乎是詩意的。這個定義簡潔地總結了它，但它並沒有告訴我們拉姆齊理論真正的含義。這就是這篇文章要做的。我首先要講解圖論的基礎知識。然後我會講述拉姆齊的變化（它涉及到著色！）。
圖論
要理解拉姆齊理論，我們首先需要了解圖論。這是一個處理網路的數學領域，在計算機科學中常用。實際上，它始於尤拉著名的“哥尼斯堡七橋問題”。
哥尼斯堡城（現在位於俄羅斯，當時屬於普魯士）被普雷格爾河分為四個部分，這四部分透過七座橋連線。問題是：是否有可能從城市的一個區域出發，穿越每一座橋恰好一次，然後回到起點或者結束於另一個地點。換句話說，就是尋找一條路徑，它恰好經過每一座橋一次。
- K_3示例圖
上圖有三個節點和三條邊。節點標記為A、B和C，邊將它們相互連線。事實上，這是一種特殊型別的圖，所有節點都相互連線，稱為K_3。你可以想象一個修改過的版本的K₃圖，其中至少有一對節點之間沒有邊相連。這樣的圖在圖論中仍然是一個有效的圖形，但它就不再是一個完全圖（即不是K_3圖）了。
- K_4示例圖
實際上，可能有無限多的圖。圖中的每個節點不需要透過邊與另一個節點相連。圖論有許多有趣的應用！我們說這個圖不是完全圖，因為不是每個節點都相互連線，
圖論的價值在於它作為分析和理解各種網路和連線的強大工具。這個數學分支透過節點（代表點或頂點）和邊（連線線）來模擬和簡化現實世界中的複雜系統。這種簡化手段使得我們能夠清晰地識別和理解系統的核心結構及其組成部分之間的相互作用。
圖論允許我們將複雜的系統看作是由多個相互連線的物件組成的網路。在這個框架下，物件可以是網路中的任何實體（如個人、計算機或城市），而它們之間的關係則透過邊來表示。這種方法有效地將現實生活中的複雜關係轉化為更容易分析和理解的數學模型。
此外，圖論中的“有向邊”概念為表示方向性提供了可能，使其成為描述具有明確方向流動（如單向道路或資料流）的理想工具。有向圖（其邊具有確定方向的圖）可以更精確地描繪出資訊或物件在系統內的流動方向。
下面，我們將深入研究拉姆齊理論。
拉姆齊理論
為了闡述拉姆齊理論的結構，我們需要在上述圖形中新增一些新元素。我們將建立多種不同型別的邊，每種邊用不同的顏色表示。現在，我僅使用紅色和藍色的邊。拉姆齊理論有多種顏色的版本，但為了本文的目的，我將保持簡單。
- 帶有彩色邊的K_4
現在，圖形有了更多元素。我們可以根據邊的顏色來構造子圖。具體來說，如果我們有一個由不同顏色的邊組成的圖，我們可以選擇這些邊中的一種顏色，並利用這些特定顏色的邊及其連線的節點來建立一個新的、更小的圖，即子圖。
子圖是從原始圖中選取一部分節點和邊構成的。例如，假設原圖中有紅色和藍色的邊，我們可以選擇所有紅色的邊及其連線的節點來形成一個子圖；同理，選擇所有藍色的邊及其連線的節點也可以形成另一個子圖。這樣，我們就根據邊的顏色，從原圖中分離出了兩個不同的子圖。
在建立這些子圖的過程中，我們保留並重用了原圖中的節點。這意味著，儘管子圖只包含原圖的一部分元素（即特定顏色的邊和相連的節點），但這些節點在原圖中仍然存在，維持了子圖與原圖之間的關聯性。
- 將上面的圖形分割成兩個子圖
這兩個子圖被稱為“包含在”上面的原始彩色圖中。它們保持相同的結構，只是其中的一部分。這兩個圖都不是完全圖，因為一些節點沒有連線。這與它們所包含的主圖形成對比。
我們現在準備好了用一個具體的例子來展示拉姆齊理論的應用。想象一下，有六個朋友被邀請參加同一個派對。在這群朋友中，有的相互認識，有的則不認識。為了描繪這種社交關係，我們可以使用圖論的方法。在這個圖中，每個人都由一個節點表示，而他們之間的相識或不相識的關係則透過連線這些節點的邊來表示。
為了區分朋友之間的不同關係，我們可以使用兩種顏色的邊：藍色邊表示兩個人相互認識，紅色邊則表示他們彼此不認識。透過這種方式，這個圖就變成了一個展示朋友間關係網路的視覺模型。在這個模型中，每個節點（代表一個朋友）都透過藍色或紅色的邊與其他節點（其他朋友）相連，形成了一個揭示了他們之間已知和未知聯絡的複雜網路。這個網路為我們提供了一個實際的場景來應用拉姆齊理論，從而發現其中的一些數學性質和模式。
這就是拉姆齊理論的用武之地。弗蘭克·拉姆齊證明了一個定理，無論如何，總會有三個人彼此認識或彼此不認識。這有點奇怪，邊的排列方式有這麼多種可能！這怎麼可能被證明呢？所有邊都相連的子圖被稱為“團（clique）”。
由於每個人要麼相互認識，要麼不認識，所以每對節點之間都有一條邊。你能在那裡找到一個由相同顏色邊連線的三人小組嗎？
這個圖中實際上有多個三人小組。其中一個是在節點A、B和E之間。它們都透過紅色邊連線，所以這是一個由三個陌生人組成的小組。在這個圖中，實際上還有另一個三人小組：D、E和F。這個小組由藍色邊連線，所以他們都互相認識。無論我們如何設定顏色，總會有這樣的子圖存在。
這些子圖總是存在似乎非常奇怪。用不同顏色設定這個圖形有2^15種不同的方式，這是一個超過3萬的數字！然而，拉姆齊理論證明，在每一個構型中，總有一個由三個全紅或全藍的組成的小組。
當我第一次聽說這個時，我真的不相信。我花了一段時間試圖找到一個反例。最終，我放棄了並接受了這個事實。
- 拉姆齊理論在更大的圖中變得更加複雜
提高複雜度
我剛才展示的是一個相對較小的圖。該圖包含6個節點和兩種顏色的邊。在這種情況下，我們關注的是所謂的拉姆齊數（Ramsey Number），使用符號表示為R(3, 3)。這個表示式中的兩個數字3表示我們在圖中尋找的是一個包含三個節點的子圖，這些節點全部透過同色（紅色或藍色）的邊相連。因此，這個拉姆齊數R(3, 3)=6的含義是，在一個有6個節點的圖中（完全圖），無論如何著色邊，總能找到一個全由同色邊連線的三個節點的子圖。實際應用到社交場景中，這意味著如果有六個人參加派對，總會存在一個三人小組，他們之間要麼全部相識（紅色連線），要麼完全不相識（藍色連線）。
數學家已經計算出R(4, 4)=18。所以如果我們邀請18人參加派對，那裡會有一個大小為4的小組，他們要麼都是朋友，要麼都是陌生人。讓人驚訝的是，R(4, 4)是目前已知的最高值。R(5, 5)是未知的。我們只知道R(5, 5)在43到48位客人之間。
這為什麼這麼難以計算？假設有一個包含43個節點的圖。這意味著有2^903種不同可能的紅色和藍色邊的排列！這個數字是巨大的！即使使用最強大的超級計算機計算所有可能的排列也需要超過宇宙的年齡。
當然，數學家已經想出了各種巧妙的技巧來試圖找到這個數字。這就是為什麼我們有一系列的猜測。這些論證背後的證明超出了本文的範圍，但我在最後提供的一些連結可以幫助你開始。
- 即使在純粹的混沌中，總會出現某種形式的秩序
拉姆齊理論表明，無論系統多麼混亂，總會在其中存在有序的部分。這是一個非常強大的宣告，可以擴充套件到各種應用中。
