Tuesday, July 01, 2008

Embedding Lemma & finding regular partitions of a graph

Theorem (Special form of Embedding Lemma).

Given , a graph R, and a positive integer m. Assume that |V(R)| = r and the maximum degree of R is Δ > 0.

Let us construct a graph G by
  1. replacing every vertex of R by m (independent) vertices, and
  2. replacing the edges of R with ε-regular pairs of density at least d.

If , then . In fact, the number of labelled copies of R in G is at least .

其實可以把 regularity 想像成一種「隨機性」。當 ε 的值愈小,regular pair 就愈「隨機」。更精確地來說,當兩個 vertex sets U, V 的 subsets A, B 儘管很小,但是它們的邊密度 (e(A,B)/|A||B|) 仍然可以與原來的邊密度 (e(U,V)/|U||V|) 十分相近。

這個定理給人的感覺,很有 Ramsey theorem 的味道。差別在於這邊是給予 regularity 一個上限,而 Ramsey-like theorem 則是給與圖形的頂點數一個下限。此外,embedding lemma 還能夠數算 labelled copies 的個數,感覺上又更強大了一點。

此外,如果把造 G 的第二點改成 complete bipartite graphs 而非先前的 "regular pairs",然後把這個另外造出的圖形叫做 G*, 那麼如果 HG* 的 subgraph,則 H 亦為 G 的 subgraph。這個變形的定理 (大致上) 就是有名的 "The Blow-up Lemma" (*)。

(*) Quotes of the Blow-up Lemma:
"... Regular pairs behave like complete bipartite graphs from the point of view of bounded-degree subgraphs. ..."


====================================================

Algorithmic version of the regularity lemma (Alon, Duke, Lefmann, Rödl and Yuster [FOCS'92]):
  • Finding ε-regular partitions of a graph can be done in polynomial time.
  • However, describe this partition to someone else, he or she cannot verify in polynomial time that this partition is really ε-regular.
也就是說,有多項式時間找出一個圖的 regular partition。如此一來,先前所說的 regular partition 的「存在性」都變成了「可建構性」 (constructive)。但是給定一個圖以及一個 partition,要檢驗這個 partition 是不是 regular 卻是一個 co-NP complete problem.



參考資料:
J. Komlós, A. Shokoufandeh, M. Simonovits, and E. Szemerédi: The regularity lemma and its applications in graph theory. Theoretical Aspects of Computer Science, Lecture Notes Comput. Sci., Vol. 2292, pp. 84--112, 2002.


3 comments:

BarrosH said...

推!很久以前就想看這篇了,不過一直延宕......

Joseph, Chuang-Chieh Lin said...

看了這些papers一開始真的是讓人頭昏眼花,不過忍耐幾個禮拜之後,才慢慢會有感覺出來。

可能是相關的 papers 實在太多了,他們寫這些文章已經不那麼仔細了。

(OS: 可能是我的數學底子不好 orz)

Joseph, Chuang-Chieh Lin said...

事實上,G 的 construction 可以藉由 regularity lemma 來做,很容易可以想到 regular partition 的 某些 blocks 對應到 R 的頂點集。

而至於需要的 regulary 程度 (\gamma 值,還是\epsilon 值,忘了),就先使用 embedding lemma 確定需要的 regularity。