Ramsey’s Theorem. is finite.
常看見的證明是先證 的情形 (
當然是鴿籠原理), 然後再對
與
作兩變數歸納法; 證明底下的不等式就完成了.
, where
.
當然仍是我們最關注的; 底下的機率方法可以證明一個簡單的下界.
Theorem. .
Proof. 每個特定的-clique 或
-independent set 出現的機會都是
; 因此若
的話就表示某個大小為
的圖同時沒有大小為
的 cliques 或 independent sets, 因此
. 整理不等式便得出我們的結果.
這個下界告訴我們一個大小為的圖會有個
大小左右的 clique 或 independent set. 但有趣的地方是我們可以用類似的方式證明不會有太大的
-免除生成子圖. 證明如下: 大小為
的生成子圖數量為
; 每張生成子圖最多有
條邊. 我們可以將這些潛在邊分解成
個邊互斥的
(why?), 而每個
是個真正
的機率是
, 因此我們可以保證每個大小為
的生成子圖是
-免除的機會不會超過
(
). 套用聯集上界 (union bound) 便完成了.
這告訴我們, 如果要在圖中找個大小為左右的
-免除生成子圖 (例如想要找個 inteval graph 或 chordal graph), 不如就找完全集或獨立集算了, 反正放寬條件也找不到更大的.
我們同時可以觀察到將大小為 n 的完全圖分解成大小為 k 的小完全集這件事其實就是找一個 t=2 的 partial Steiner system S(n,k,t); 利用所謂的 Erdos-Hanani-Rodl 定理 (原本是 Erdos-Hanani 猜想), 我們知道對於任意的 n,k,t 存在著大小大約為的 partial Steiner system. 因此上述所說的
並沒有什麼特別的; 我們可以證明對於任意大小為 k (常數) 的圖 H, 存在大小為 n 的圖 G, 其中 H-免除生成子圖的大小大約是
. 同樣的定理可以推廣到 hypergraphs! 這一屆當然都符合 Ramsey 理論 (事實上, 就是隨機性) 的精神: 只要結構夠大, 裡頭什麼事都會發生, 就算是規律; 想要避免某一種規則的產生是不可能的.