The Regularity Lemma and Its Applications in Graph Theory (2002)

Turán graph T(13, 4), an example of extremal graph.

The Regularity Lemma and Its Applications in Graph Theory Kolmós et al, 2002.

這篇 survey 文章比較長,有 8 章。這裡只打算讀第 3、4、7 章。第 3 與第 4 章講 Regularity Lemma 怎麼與 reduced graph 一起使用,以及建 subgraph 的問題。第 7 章講一些演算法上的問題。

Reduced graph 是這樣。G=(V, E) 是個 graph,P=(V_1,…,V_k)V 的 partition,而 εd 是兩個參數。那 reduced graph R 是這樣的 graph:R 的 vertices 是 V_1,…,V_kk 個),而 (V_i, V_j)R 裡有 edge 如果 (V_i, V_j)ε-regular 而且 density 大於 d

記得上次講過如果 e(A,B)AB 之間的 edge 的數目,d(A,B) 也就是密度就是 density=e(A,B)/|A||B|(A,B) 是 ε-regular 如果對每組子集合 X in AY in B 並且 |X|≥ε|A||Y|≥ε|B|,都會有 |d(X,Y)-d(A,B)|≤ε

用 Regularity Lemma 的證明大多會用到 reduced graph,因為 G 的很多性質會保留到 R 身上。過程會是這樣。要解決 G 上面的問題,就先對 G 使用 Regularity Lemma,證明或算出一個 partition P,就可以得到 reduced graph R。接下來可以對 R 用一些 classical extremal graph theory 的定理例如 Konig-Hall theorem、Dirac’s theorem、Turán’s theorem、Hajnal-Szemerédi theorem。再來可以用 Embedding Lemma 或更強一點的 Blow-up Lemma 把在 R 得到的結論推回 G 身上。

上面講的推回 G 身上用的推論基本上是:如果 ε 夠小,那麼 R 的每一個 subgraph H 也會是 G 的 subgraph。這就是 Embedding Lemma 的意思,但定理本身我看不太懂。無論如何,這裡有簡短的證明。第 3 章最後一節快速介紹了幾個常跟 Regularity Lemma 一起使用的 classical extremal graph theory 結果,這些的證明都獨立於 Regularity Lemma。

第 4 章延續前面的討論,在講 Regularity Lemma 加 Embedding Lemma 可以如何證明 graph 裡存在某種 subgraph,方法是逐一把那個 subgraph 建立起來。有個已知的結果是考慮固定的 graph H,以及有 n 個 vertices 的隨機 graph G_n,固定 edge-density p>0,當 n 趨近無限大時 H almost surely 包含在 G 之中。Regularity Lemma 對 dense graph 可以做類似的事情。這章列了很多 conjectures,這部份沒看懂。最後有 Blow-up Lemma 的敘述。

演算法相關的問題有兩大類。第一個是證明 graph 裡存在某種 subconfiguration,所以對 Regularity Lemma 的演算法(如何找到 partition P)就可以變成找到 subconfiguration 的演算法。第二個是 Regularity Lemma 為密度夠高的 graph 提供了 randomlike graph 的結構,而因為我們知道很多演算法在 randomlike graph 上會失效,所以這可以為 complexity theory 的問題提供下限值(Hajnal et al(1988)、Pulak et al(1995))。Alon et al(1994)證明對任何 G 可以在 polynomial time 裡找到 ε-regular partition,但要驗證一個 partition 是 ε-regular 則無法在 polynomial time 完成,是 co-NP complete 問題。Duke et al(1995)用 Regularity Lemma 設計了一個估算固定的 graph HG 裡出現為 subgraph 次數的演算法。

A single golf clap? Or a long standing ovation?

By clapping more or less, you can signal to us which stories really stand out.