組合學/拉姆齊定理

拉姆齊定理是組合學中的一個基礎結果。該結果的第一個版本由 F. P. 拉姆齊證明。這開創了被稱為拉姆齊理論的組合理論，該理論試圖在混亂中尋找規律：尋找具有規律性質的子結構存在的普遍條件。該定理指出

在對足夠大的完全圖（即每個頂點對之間都有一條邊連線的簡單圖）的邊進行任何著色時，都會找到單色完全子圖。對於 2 種顏色，拉姆齊定理指出，對於任何一對正整數 (r,s)，存在一個最小的正整數 R(r,s)，使得對於任何具有 R(r,s) 個頂點的完全圖，其邊被塗成紅色或藍色，要麼存在一個具有 r 個頂點的完全子圖，其完全為紅色，要麼存在一個具有 s 個頂點的完全子圖，其完全為藍色。這裡 R(r,s) 表示一個取決於 r 和 s 的整數。它被理解為代表該定理成立的最小整數。

該定理的擴充套件適用於任何有限的顏色數量，而不僅僅是兩種顏色。更準確地說，該定理指出，對於任何給定的顏色數量 c，以及任何給定的整數 n₁,...,n_c，存在一個數字 R(n₁,...,n_c)，使得如果階為 R(n₁,...,n_c) 的完全圖的邊用 c 種不同的顏色著色，則在 1 到 c 之間的某個 i 處，它必須包含一個階為 n_i 的完全子圖，其邊都是顏色 i。上面的特例有 c = 2（以及 n₁ = r 和 n₂ = s）。

示例：R(3,3)=6

假設一個具有 6 個頂點的完全圖的邊被塗成紅色和藍色。選擇一個頂點 v。有 5 條邊與 v 相連，因此（根據抽屜原理）至少 3 條邊必須是相同的顏色。不失一般性，我們可以假設至少 3 條這些邊連線到頂點 r、s 和 t，是藍色的。（如果不是，在下面交換紅色和藍色。）如果邊 (r, s)、(r, t)、(s, t) 中的任何一個也是藍色的，那麼我們就得到了一個完全是藍色的三角形。如果不是，那麼這三條邊都是紅色的，我們就得到了一個完全是紅色的三角形。由於這個論證適用於任何著色，因此任何 K₆ 都包含一個單色 K₃，因此 R(3,3) ≤ 6。這個定理的流行版本被稱為朋友和陌生人定理。

一個交替證明方法是透過雙重計數。它如下所示：計算頂點 x、y、z 的有序三元組的數量，使得邊 (xy) 為紅色，邊 (yz) 為藍色。首先，任何給定的頂點將是 0×5=0、1×4=4 或 2×3 = 6 個此類三元組的中間頂點。因此最多有 6×6=36 個此類三元組。其次，對於任何非單色三角形 (xyz)，恰好存在兩個此類三元組。因此最多有 18 個非單色三角形。因此，在 K₆ 中的 20 個三角形中，至少有 2 個是單色的。

相反，可以對 K₅ 進行 2 色著色，而不會建立任何單色 K₃，這表明 R(3,3) > 5。右側顯示了唯一的著色。因此 R(3,3) = 6。

定理證明

首先，我們透過對 r + s 進行歸納來證明 2 色情況下的定理。從定義中可以明顯看出，對於所有 n，R(n, 1) = R(1, n) = 1。這開始了歸納。我們透過找到它的顯式界限來證明 R(r, s) 存在。根據歸納假設，R(r − 1, s) 和 R(r, s − 1) 存在。

斷言：R(r, s) ≤ R(r − 1, s) + R(r, s − 1): 考慮一個具有 R(r − 1, s) + R(r, s − 1) 個頂點的完全圖。從圖中選擇一個頂點 v，並將剩餘的頂點劃分為兩個集合 M 和 N，使得對於每個頂點 w，如果 (v, w) 為藍色，則 w 在 M 中，如果 (v, w) 為紅色，則 w 在 N 中。

因為該圖具有 R(r - 1, s) + R(r, s - 1) = |M| + |N| + 1 個頂點，所以 |M| ≥ R(r − 1, s) 或 |N| ≥ R(r, s − 1)。在前一種情況下，如果 M 具有一個紅色 K_s，那麼原始圖也具有一個紅色 K_s，我們就完成了。否則 M 具有一個藍色 K_r−1，因此 $M\cup \{v\}$ 根據 M 的定義具有藍色 K_r。後一種情況類似。

因此斷言是正確的，我們完成了對 2 種顏色的證明。我們現在證明了 c 種顏色的一般情況下的結果。證明仍然是歸納法，這次是對顏色數量 c 進行歸納。我們對 c = 1（平凡的）和 c = 2（上面）得到了結果。現在讓 c > 2。

斷言：R(n₁, ..., n_c) ≤ R(n₁, ..., n_c−2, R(n_c−1, n_c))

注意，右手邊只包含 c − 1 種顏色和 2 種顏色的拉姆齊數，因此根據歸納假設，它存在並且是有限數 t。因此，證明斷言將證明定理。

斷言證明：考慮一個具有 t 個頂點的圖，並用 c 種顏色對它的邊進行著色。現在“色盲”，假裝 c − 1 和 c 是同一種顏色。因此該圖現在是 (c − 1) 色的。根據歸納假設，它包含一個 K_n_{_i}，用顏色 i 單色著色，對於某個 1 ≤ i ≤ (c − 2)，或者一個 K_R(n_{_c−1,n_c)}，用“模糊色”著色。在前一種情況下，我們完成了。在後一種情況下，我們恢復了視力，並從 R(n_c−1, n_c) 的定義中可以看到，我們必須要麼有一個 (c − 1) 單色 K_n_{_c−1}，要麼有一個 c 單色 K_n_{_c}。在任何一種情況下，證明都完成了。

定理的擴充套件

該定理也可以擴充套件到超圖。一個 m 超圖是一個圖，其“邊”是 m 個頂點的集合——在一個普通圖中，邊是 2 個頂點的集合。拉姆齊定理關於超圖的完整陳述是，對於任何整數 m 和 c，以及任何整數 n₁,...,n_c，存在一個整數 R(n₁,...,n_c;c,m)，使得如果階為 R(n₁,...,n_c;c,m) 的完整 m 超圖的超邊用 c 種不同的顏色著色，則對於某個 1 到 c 之間的 i，超圖必須包含一個階為 n_i 的完整子 m 超圖，其超邊都是顏色 i。這個定理通常透過對 m（圖的“超”程度）進行歸納來證明。證明的基本情況是 m=2，這正是上面的定理。