## Tuesday, July 01, 2008

### Embedding Lemma & finding regular partitions of a graph

Theorem (Special form of Embedding Lemma).

Given $d> \epsilon > 0$, 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 $\epsilon\leq (d-\epsilon)^{\Delta}/(2+\Delta)$, then $R\subset G$. In fact, the number of labelled copies of R in G is at least $(\epsilon m)^{r}$.

(*) 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.

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.

BarrosH said...

Joseph, Chuang-Chieh Lin said...

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

Joseph, Chuang-Chieh Lin said...