動機
極值圖論定理問的是:多少條邊會迫使圖中出現某個特定子圖。Ramsey 問題則是給每條邊染上一種顏色,問某一種顏色中是否必然含有完全圖。兩種顏色都可以有很多條邊,所以僅僅知道邊的總數並不能解決問題。真正有用的資訊是:兩個顏色類在一個頂點周圍如何相互作用。
這裏有兩類不同的任務。上界必須對每一種著色都成立;下界則只需要一種著色,使其同時避開兩個被禁止的團。我們先透過不斷限制到鄰點集合來建立普遍性保證,再構造一個精確的小規模障礙,並用一個有限隨機試驗證明更大的障礙存在。這些存在性陳述都沒有給出尋找最優著色的快速算法,也沒有確定所有 Ramsey 數。
以下論證只使用初等計數和有限概率,不假設任何漸近 Ramsey 估計。
定義
定義 10.5.1
(二色閾值及其量詞)
對正整數 與 ,令 為最小的正整數 ,使得完全簡單圖 的每一種紅/藍邊著色都含有 個頂點的紅色團,或 個頂點的藍色團。單個頂點的團沒有邊,對任一顏色的要求都自動滿足。這個最小整數的存在性將在下文證明。
若一種著色中兩個指定的團都不出現,則稱它避開數對 。因此, 個頂點上的一種避開著色證明 ;而 個頂點上的一個普遍性論證證明 。
交換顏色的名稱即得對稱性 。把著色限制到頂點子集上可知:一旦普遍性在 處成立,它在任何更大的階數處也成立。邊界值 由單點約定得出。對於兩個或更多頂點,給一條邊著色就是在它的兩種顏色中選擇一種,並不要求兩種顏色都出現。
定義 10.5.2
(多色邊著色與單色團)
對整數 , 的一個 -著色給每條邊指定 種顏色之一。若 個互不相同的頂點之間的全部 條邊都同色,則稱它們生成一個單色 -團。
正常頂點著色(相鄰頂點必須不同色)是另一個概念;這裏的顏色屬於邊,共用頂點的邊可以同色。
定理
定理 10.5.3
(鄰域遞推證明有限性與二項式上界)
對 ,
所有這些有限閾值都存在,並且
特別地,對每個 都有 。
定理 10.5.4
(有限隨機試驗給出避開著色)
設 與 為整數。若
則 存在一種邊著色,其中沒有單色 -團,故 。當 時該二項式係數為零。
對每個 ,這蘊含
該判據只是充分條件;該數值不等式不成立,並不能證明每一種著色都含有被禁止的團。
定理 10.5.5
(重複限制同樣證明多色保證)
對整數 與 ,令 。在
個頂點的完全圖上,每一種 -著色都含有單色 -團。這是一個有限上界,並不聲稱它是最優的。當 時,上式之和為 。
概念視角組合
普遍性限制與有限平均回答的是相反的量詞
鄰域歸納處理任意著色,並迫使見證出現:它證明的是「對每一種著色都存在團」這類陳述。有限平均則遍歷所有著色,證明其中至少有一種沒有見證:「存在一種沒有團的著色」。即使涉及同一個有限圖,上界、下界與精確閾值所需要的證據也各不相同。
下面的證明正按這一分工進行:第一和第三個定理用限制證明,第二個定理用平均證明。
證明思路或證明
一個頂點把較小的閾值變成較大的閾值
歸納對 進行,並用一個中心頂點把兩個較小的閾值推到較大的閾值。
證明
(鄰域遞推與二項式界的證明)
對 作歸納來證明有限性,起點是其中一個參數為 的情形。假設較小的閾值 與 已經存在。考慮 的任意著色,並選定一個頂點 。
若 至少有 個紅鄰點,則限制到其中 個。歸納性質給出:要麼有大小為 的紅色團,加入 之後成為紅色 -團;要麼有藍色 -團,這已經回答了原問題。
否則 至多有 個紅鄰點。由於它的 條關聯邊按顏色分成兩類,所以它至少有 個藍鄰點。這些藍鄰點誘導的完全圖含有紅色 -團,或大小為 的藍色團;在後一種情形下加入 即可。因此 的每一種著色都含有所需的團。可行的正整數階數構成的集合非空,故其最小元 存在且不超過 ,遞推式得證。
對於顯式界,使用同樣的歸納,邊界值為 。由 Pascal 恆等式
與 的歸納上界相加正好得到所示的係數。在對角線上, 是 中的一項,由此得到較粗的指數上界。
證明透視
中心頂點用在哪裏
證明只用到歸納假設: 個頂點上的每一種著色都含紅色 -團或藍色 -團, 個頂點上的每一種著色都含紅色 -團或藍色 -團。唯一不顯然的一步,是對 的 條邊作抽屜計數:紅鄰點不足 個,藍鄰點就至少有 個。論證之所以能收尾,是因為 以相應顏色連到所保留集合的每個頂點,加入 使該顏色的較小團增大一個頂點,而另一種顏色的團本來就已達到所需大小。
這個計數是剛好夠用的。在 個頂點上,中心只有 個鄰點,可以恰好分成 個紅鄰點與 個藍鄰點,此時兩個保留集合都不夠大,無法使用歸納假設。這就是遞推式要把兩個較小閾值本身相加的原因。計算出的上界不一定能取到:遞推完全捨棄了兩個鄰域之間如何連接的資訊。
計數壞團,而不是假設它們的事件相互獨立
下界來自對所有著色取平均:平均值小於一,就迫使某種著色的取值為零。
證明
(第一矩下界的證明)
把 的每條邊獨立地以各 的概率染成紅色或藍色。這是一個有限的均勻概率空間:全部 種著色權重相同。固定的 -子集恰好生成 條邊。這些邊全為紅色的概率是 ;全為藍色的概率相同。對 ,這兩個事件互不相交,所以該 -子集單色的概率是 。
令 為單色 -子集的個數。把 寫成 個示性隨機變量之和,由有限期望的線性性得
這一計算不要求不同 -子集的事件相互獨立;相互重疊的團通常共享邊。若每種著色都至少含有一個壞團,則 恆不小於一,其平均值也不小於一。因此平均值嚴格小於一就蘊含存在 的著色。嚴格性很重要:平均值等於一本身並不能迫使出現零結果。
為得到指數下界,取 ,於是 。由於 -子集的個數至多等於有序 -元組的個數除以 ,
對 ,最後一個量是 ,因為 。 增加一時,其分子乘以 ,分母乘以 ,所以它始終嚴格小於一。這就證明了對每個 所斷言的界,包括 的情形(此時 )。該證明是在明確有限的著色之中確立存在性,不需要任何無限隨機構造。
每次顏色限制之後都多保留一個頂點
多色證明重複中心頂點這一步,但不再對兩個參數遞推,而是記錄顏色。
證明
(多色保證的證明)
對非負整數 ,記 。從 個頂點出發。選取中心 ,並按其餘頂點與 相連的邊的顏色把它們分類。由於 , 個顏色類中必有一個至少含 個頂點。保留這樣一個類,並把它的顏色記在該中心旁邊。
重複此過程,直到選出 個中心 並剩下最後一個頂點 ;這是可以做到的,因為所保留的集合依次至少有 個頂點。因為所保留的集合是嵌套的,每個被選中的中心與所有後來被選中的頂點之間的邊,都具有它所記錄的顏色。由抽屜原理,在所記錄的 個顏色中,至少有 個相同。取這 個中心和最後的頂點 。兩個所選中心之間的任何邊都具有較早那個中心所記錄的顏色;中心到 的邊也是這一顏色。因此這 個頂點之間的所有邊同色。
這個嵌套集合不變量比單純選出許多標記相同的頂點更強。標記控制的是通向所有後來保留頂點的實際的邊。這也解釋了為甚麼我們保留最後一個頂點而不給它標記:它與 個同色的中心共同構成一個團。
例題詳解
例題 10.5.6
(三角形閾值恰為六)
在 的任意紅/藍著色中,選定的頂點有五個鄰點,所以在某一種顏色中至少有三個鄰點,不妨設為紅色。若這三個鄰點之間有任一條邊為紅色,它與中心構成紅色三角形。否則這三個鄰點之間的三條邊都是藍色,構成藍色三角形。藍鄰點的情形對稱,故 。
對於反向不等式,把五圈的邊染成紅色,其餘的邊全染成藍色。紅色圖是一個圈,不含三角形。用模 的剩餘類標記頂點,藍色邊連接差為 的頂點,構成圈 ,同樣不含三角形。這一種避開著色證明 。兩個論證合起來給出 。
例題 10.5.7
(把精確的小值代入遞推式)
若一種著色沒有紅邊,則其所有邊都是藍色。因此 : 個頂點就足夠,而 個頂點上的全藍著色同時避開兩個所要求的團。在遞推式中使用精確的三角形閾值,得
再次應用得 。這些是已證明的普遍性上界。這裏沒有給出與之匹配的避開構造,所以這兩個不等式都不能被提升為精確值。所得結果與二項式公式 、 相同,因為代入的 與 恰好等於各自的二項式界;只有代入小於二項式係數的精確值時,遞推式才會勝過公式。由對稱性,參數互換後得到相應的界。
例題 10.5.8
(期望檢驗證明存在性,並有明顯的局限)
對 與 ,單色五團的期望個數為
因此存在某種十個頂點的著色,同時避開兩種顏色的五團,從而證明 。該證明不需要指出這是哪一種著色。
邊界情形 、 時,同一期望等於 ,所以這一檢驗沒有給出避開著色。然而上面的五圈構造確實同時避開了兩種三角形。因此,充分的第一矩檢驗失敗,與所期望的構造不存在,是兩回事。
常見錯誤
反例模式
稠密的顏色不一定含有指定的團
待檢驗的說法:若某一種顏色得到 至少一半的邊,則該顏色含有三角形。取 ,把一個五圈染成紅色。紅色有 條邊中的 條,恰為一半,每個頂點的紅度數為 ;紅色三角形需要三個在圈上兩兩相鄰的頂點,而五圈中沒有這樣的三個頂點。藍色補圖是圈 ,有同樣的密度和同樣的障礙。該說法不成立。邊密度只有超過某個需要另行證明的極值閾值後才迫使三角形出現;它不能代替 Ramsey 論證,後者用的是顏色類在一個頂點處如何相遇。
常見錯誤
(把重疊團的概率直接相乘)
人們容易把「沒有單色 -團」的概率估計為 ,彷彿不同 -子集的事件相互獨立。一般而言它們並不獨立。對 ,兩個共用三個頂點的 -子集共用三條邊;各自單色的概率是 ,但兩者同時單色的概率是 ,而非 。第一矩論證只需要邊的顏色相互獨立以及期望的線性性。
常見錯誤
(把邊著色與正常頂點著色混為一談)
Ramsey 著色給邊上色,對共用頂點的邊沒有任何限制。正常頂點著色給頂點上色,並禁止一條邊的兩端同色。關於色數的結論不能直接說明邊著色中的單色團。
常見錯誤
(把界當作值,或把方向寫反)
個頂點上的避開著色證明 ,永遠不證明 。反過來,遞推式與多色求和給出的上界不一定能取到: 並不是說 。精確值需要一個普遍性論證與一個避開著色恰好相接,就像 那樣。
總結
鄰域限制證明了有限的二色閾值和顯式的二項式界;嵌套限制給出多色保證。精確的五圈障礙確定了三角形閾值。有限期望證明其他障礙的存在,同時明確保留嚴格不等式以及充分檢驗的局限。這些論證在本章內仍未解決大多數精確閾值和高效搜尋的問題。
練習
快速檢查
(證明對每個正整數 都有 ,並明確處理 的情形。)
把單點約定與沒有紅邊這兩種情形區分開來。
解答
對 ,邊界約定給出 。對 , 個頂點上的任意著色要麼有一條紅邊(這已經是紅色二團),要麼所有邊都是藍色,從而有藍色 -團。這證明了上界 。
把 個頂點上的每條邊都染成藍色。沒有紅邊,且頂點數不足以構成藍色 -團。因此閾值大於 ,等式得證。該論證在 時同樣成立:單個頂點同時避開兩個二團。
快速檢查
(計算多色定理對三種顏色與三角形給出的界。準確說明哪些被選中的頂點構成團。)
取 ,並保留最後一個未標記的頂點。
解答
取 、,則 ,保證的階數為 。限制過程選出六個中心,隨後是最後一個頂點。六個記錄的顏色只來自三種,所以至少有兩個中心所記錄的顏色相同。它們之間的邊由較早那個的標記決定,具有該顏色,並且它們到最後頂點的兩條邊也具有該顏色。這兩個中心與最後的頂點構成所需的三角形。
這一數值保證有意取得較粗。該證明沒有給出接近 的下界構造,也不聲稱這就是三色三角形的實際閾值。
快速檢查
(對 證明更強的下界估計 。說明為甚麼它仍然只是存在性的界。)
在應用第一矩檢驗之前,先把對數之和與從 到 的積分作比較。
解答
因為對數函數遞增,對 有 ,所以
特別地,。取 ;當 時它為正,並且 。第一矩估計給出
因此存在避開著色,其階數證明了所需的嚴格下界。我們是在所有有限邊著色上取平均;僅憑這一計算,並不能得到尋找成功著色的高效方法、最優閾值,或對無界 的高效避開證書。