hypergraph | Finite Playground

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 理論 (事實上, 就是隨機性) 的精神: 只要結構夠大, 裡頭什麼事都會發生, 就算是規律; 想要避免某一種規則的產生是不可能的.

Finite Playground

To verify is human; to prove, divine.

Tag Archives: hypergraph

A lower bound to Ramsey numbers and an application