Blow-Up Lemma

The blow-up lemma essentially says that regular pairs in Szemerédi's regularity lemma behave like complete bipartite graphs from the point of view of embedding bounded degree subgraphs.

In particular, given a graph  of order , minimal vertex degree  and maximal vertex degree , then there exists an  such that the following holds. Let  be an arbitrary positive integer, and replace the vertices of  with pairwise disjoint -sets , , ...,  (blowing up). Now construct two graphs on the same vertex set . The graph  is obtained by replacing all edges of  with copies of the complete bipartite graph , and construct a sparser graph by replacing the edges of  with some -superregular pair. If a graph  with  is embeddable into , then it is already embeddable into  (Komlós et al. 1998).

REFERENCES

Komlós, J.; Sárkőzy, G. N.; and Szemerédi, E. "Blow-Up Lemma." Combinatorica 17, 109-123, 1997.

Komlós, J.; Sárkőzy, G. N.; and Szemerédi, E. "Proof of the Seymour Conjecture for Large Graphs." Ann. Comb. 2, 43-60, 1998.