鴿籠原理說,足夠大的集合無法在不重複的情況下分配出去。Ramsey 理論問的是更豐富的不可避免的結構:無論怎樣用兩種顏色給大完全圖的邊著色,總有一組頂點,它們之間的所有邊都同色。本節證明這樣的頂點組一定存在,估計圖至少要多大,並精確確定第一個非平凡的值。本節用到歸納法、二項式係數,以及前面各計數章節的雙重計數技巧。
定義
定義 2.11.1
(單色團與 Ramsey 數)
設 為 個頂點的完全圖。 的紅藍著色為每條邊指定紅色或藍色之一。若頂點集 中任意兩點之間的邊都是紅色,稱 為紅團;藍團同理;含 個頂點的團稱為 -團。對整數 ,Ramsey 數 是最小的 ,使得 的每個紅藍著色都含有紅 -團或藍 -團。這個最小值存在,是下面定理的一部分。若 的某個著色既無紅 -團也無藍 -團,稱它為 的見證。
由定義立即得到兩條性質。紅藍可以互換,所以 。-團沒有邊,所以單獨一個頂點既是紅 -團也是藍 -團:。
概念視角結構
同一個圖中的團與獨立集
只保留紅邊。 的紅藍著色就等同於 個頂點上的一個圖 :紅邊是 的邊,藍邊是 的非邊。紅 -團就是 中大小為 的團,藍 -團就是大小為 的獨立集,即 個彼此之間沒有 的邊的頂點。因此 是最小的 ,使得 個頂點上的每個圖都含大小為 的團或大小為 的獨立集。用這種語言,對稱性 就是取補圖;下面 的見證是 -圈,它不含三角形,而它的補圖仍是 -圈。
存在性與二項式上界
定理 2.11.2
(兩色 Ramsey 定理)
對所有整數 , 存在,並且
此外,對所有 ,
證明
(經由一個頂點對 作歸納)
對 作歸納,並假定 與 存在( 或 的基本情形已知,都等於 )。令 ,取 的任意紅藍著色,並固定一個頂點 。它有 個鄰點,分為以紅邊與 相連的集合 和以藍邊與 相連的集合 。若 且 ,則 ,矛盾。所以 或 。
情形 。 內有紅 -團或藍 -團。若是後者,已達成目標。若是前者,加入 即得紅 -團,因為 與 的每個頂點都以紅邊相連。
情形 。 對稱地, 內有紅 -團,或有藍 -團,加入 即成藍 -團。
無論哪種情形,該著色都含有紅 -團或藍 -團,所以 存在且至多為 。
證明透視
一個頂點的兩項任務
固定的頂點 做了兩件事。第一,它的 條邊按顏色分成 與 ;選取 ,正是為了迫使其中一側夠大:若兩側都低於各自的門檻,便有 。這是容量不同的鴿籠原理,兩個容量分別為 與 。第二, 是被加入到其顏色類內所找到的團的頂點;只有當團的顏色與 引出的邊的顏色一致時,擴充才成立: 內的紅 -團可以擴充,而 內的藍 -團則無需擴充。
歸納假設應用於 或 所誘導的子圖,它仍是帶紅藍著色的完全圖;所以與 Ramsey 數比較的是 與 ,而不是 。每一步令 減少一,最終到達 或 的基本情形,歸納因而收結。矛盾只用到 ,所以論證對 個頂點不作任何斷言;例如對 ,九個頂點其實已經足夠。
證明
(用 Pascal 法則作歸納)
當 或 時,界分別為 或 ,成立。對 ,假定 與 的界成立。由遞推式與 Pascal 法則,
例如 ,。
以見證和計數得到下界
下界 需要 的一個既無紅 -團也無藍 -團的著色。第一個簡單的族是 :一條紅邊就是紅 -團,所以沒有紅 -團的著色,所有邊都是藍色;而全藍的 沒有藍 -團,故 ,與上界合起來得 。
對一般的 ,很難直接找出見證;而概率式的計數論證不需要構造就能給出下界。
定理 2.11.3
(計數下界)
設 。若 ,則 。
證明
(對所有 元集用並集界)
把 的每條邊獨立地染成紅色或藍色,使全部 個著色等可能。固定的 個頂點之間共有 條邊。恰有 個著色使它成為紅團,同樣多個使它成為藍團,所以它單色的概率為 。對 個集合用並集界,某個 元集單色的概率至多為 。因此存在一個著色沒有單色 -團,它就是 的見證。
例題
例題 2.11.4
()
上界:由定理,。直接論證:在 的任意著色中,頂點 有五個鄰點,所以至少有三條邊同色,設為紅色,連到 。若 中有一條是紅色,它與 構成紅三角形;否則 是藍三角形。
下界:把 的頂點記為 ,當 時邊 為紅色,當 時為藍色。紅邊構成 -圈 ,藍邊構成 -圈 。-圈不含三角形,所以沒有單色三角形。於是 ,從而 :任何六個人之中,總有三人兩兩認識,或三人兩兩不認識。
例題 2.11.5
( 的上界)
由遞推式,。二項式界同樣給出 。這些都只是上界。確切值已知為 ,但證明它需要比遞推式更精細的論證,這裏不作介紹。
例題 2.11.6
(用計數法得到 與 的下界)
當 ,因子為 。取 ,,,所以 。取 ,,,論證到此為止。當 ,因子為 。取 ,,,所以 ;取 ,,論證到此為止。這些界對小的 很弱;方法的價值在於對每個 都適用,見下一例。
例題 2.11.7
(計數界中的指數)
取 ,。利用 得 。當 時為 ;當 時更小,因為 比 增長得更快。所以對所有 有 。例如 時為 。
常見錯誤與細節
常見錯誤
(遞推式是不等式)
遞推式是不等式,不是等式:並沒有聲稱 等於 。證明只表明 個頂點已經足夠。
常見錯誤
(一個著色只確定一個方向)
確定 需要兩個方向。上界說明 的每個著色都含團;下界則需要較小完全圖上一個具體的、不含這種團的著色。只說明 的某個著色含三角形,對 沒有任何說明。
常見錯誤
(團的顏色必須與 引出的邊一致)
單色團指其頂點之間的所有邊同色,並不是說這些頂點與某個外部頂點以該色的邊相連。在遞推式的證明中,從 到 的紅邊與 內部的邊扮演不同角色:只有當 內找到的團的顏色與 到 的邊的顏色一致時,才能用 擴充該團。
反例模式
三種顏色時六個頂點不夠
聲稱:既然 , 的邊無論用多少種顏色著色,都有單色三角形。取例題中頂點 上的紅、藍兩個 圈,加上頂點 ,把它的五條邊塗成綠色。紅與藍照舊沒有三角形;綠邊全都經過頂點 ,任何三條都圍不成三角形。定理只涉及兩種顏色。同一個頂點論證可修補三色的情形: 的一個頂點有 條邊,故某種顏色連到 個鄰點;它們之間若有一條該色的邊便閉合成三角形,否則它們只用兩種顏色, 便適用。
計數論證只證明存在性,並不給出具體著色。它說明某個著色沒有單色 -團,卻沒有說明是哪一個。
Ramsey 數由對 取最小值定義。若 的每個著色都有單色團,則對 , 的每個著色也有(限制到 個頂點上),所以這個性質對 單調,「最小的 」有明確定義。
練習
快速檢查
(證明對每個 都有 。)
解答 · 答案
取 的任意紅藍著色。若有一條邊為藍色,它就是藍 -團。否則所有邊都是紅色,全部 個頂點構成紅 -團。所以 。把 的所有邊染紅,既沒有藍邊,頂點數又少於 ,所以既無紅 -團也無藍 -團;故 ,即 。
快速檢查
(把 的頂點集分成 ,,連接 與 的邊染紅,兩端同在 或同在 的邊染藍。找出所有單色三角形,並說明結果如何與 相符。)
解答 · 答案
紅邊連接 與 ,所以紅圖是二分圖,沒有三角形。全藍的三角形必須完全在 內或完全在 內(同時含兩側頂點的三角形含有 – 的邊,那是紅色)。 與 各是一個藍三角形,沒有其他的。所以恰有兩個單色三角形,都是藍色。由 , 的每個著色至少有一個,這裏恰有兩個,與之相符。
快速檢查
(利用遞推式與 證明 ,並計算 的二項式上界。)
解答 · 答案
由遞推式,,其中 見正文。二項式界為 。
快速檢查
(對 應用計數下界:證明 在 時成立而在 時不成立,並把結論與真值 比較。)
解答 · 答案
當 時,,所以 。當 時,,不小於 ,論證到此為止。它只證明 ,而真值為 ;計數法對小的 遠不夠精確。
快速檢查
(把兩人分為認識或不認識。直接證明在任意 人之中,有三人兩兩認識,或有四人兩兩不認識。)
解答 · 答案
在這 人的完全圖中,認識的人之間連紅邊,不認識的人之間連藍邊,並固定一個人 。設 有 個熟人和 個陌生人。若 ,則這 個熟人之中,或有兩人彼此認識(與 構成三人兩兩認識),或所有人兩兩不認識(至少四人兩兩不認識)。若 ,則 ;在 的六個或更多陌生人之中,由 ,有三人兩兩認識或三人兩兩不認識;三個兩兩不認識的人加上 即得四個兩兩不認識的人。每種情形結論都成立。