Finite Playground

To verify is human; to prove, divine.

A lower bound to Ramsey numbers and an application

Leave a comment

Ramsey’s Theorem.  R(p_1,\ldots,p_k;r) is finite.

常看見的證明是先證 r=2 的情形 (r=1 當然是鴿籠原理), 然後再對 r\sum p_i 作兩變數歸納法; 證明底下的不等式就完成了.

R(p_1,\ldots,p_k;r) \le R(p_1',\ldots,p_k';r-1)+1, where p_i' = R(p_1,\ldots,p_{i}-1,\ldots,p_k;r).

當然R(p,p) := R(p,p;2)仍是我們最關注的; 底下的機率方法可以證明一個簡單的下界.

Theorem. R(p,p) = \Omega(p 2^{p/2}).
Proof.  每個特定的p-clique 或p-independent set 出現的機會都是2^{-{p \choose 2}}; 因此若2{n \choose p} 2^{{n \choose 2}-{p\choose 2}} < 2^{n \choose 2}的話就表示某個大小為n的圖同時沒有大小為p的 cliques 或 independent sets, 因此R(p,p) > n.  整理不等式便得出我們的結果.

這個下界告訴我們一個大小為n的圖會有個O(\log n)大小左右的 clique 或 independent set.  但有趣的地方是我們可以用類似的方式證明不會有太大的C_4-免除生成子圖.  證明如下: 大小為p的生成子圖數量為n^p; 每張生成子圖最多有{p \choose 2}條邊.  我們可以將這些潛在邊分解成\Omega(p^2)個邊互斥的K_4(why?), 而每個K_4是個真正C_4的機率是6/2^6, 因此我們可以保證每個大小為p的生成子圖是C_4-免除的機會不會超過c^{p^2} (c < 1).  套用聯集上界 (union bound) 便完成了.

這告訴我們, 如果要在圖中找個大小為O(\log n)左右的C_4-免除生成子圖 (例如想要找個 inteval graph 或 chordal graph), 不如就找完全集或獨立集算了, 反正放寬條件也找不到更大的.

我們同時可以觀察到將大小為 n 的完全圖分解成大小為 k 的小完全集這件事其實就是找一個 t=2 的 partial Steiner system S(n,k,t); 利用所謂的 Erdos-Hanani-Rodl 定理 (原本是 Erdos-Hanani 猜想), 我們知道對於任意的 n,k,t 存在著大小大約為{n\choose t}/{k\choose t}的 partial Steiner system.  因此上述所說的C_4 並沒有什麼特別的; 我們可以證明對於任意大小為 k (常數) 的圖 H, 存在大小為 n 的圖 G, 其中 H-免除生成子圖的大小大約是\Theta(\log n).  同樣的定理可以推廣到 hypergraphs!  這一屆當然都符合 Ramsey 理論 (事實上, 就是隨機性) 的精神: 只要結構夠大, 裡頭什麼事都會發生, 就算是規律; 想要避免某一種規則的產生是不可能的.

Author: hcsoso

Ph.D. student in the Department of Computer Science, University of Illinois at Urbana-Champaign.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s