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 R of order r, minimal vertex degree delta and maximal vertex degree Delta, then there exists an epsilon>0 such that the following holds. Let N be an arbitrary positive integer, and replace the vertices of R with pairwise disjoint N-sets V_1, V_2, ..., V_r (blowing up). Now construct two graphs on the same vertex set V= union V_i. The graph R(N) is obtained by replacing all edges of R with copies of the complete bipartite graph K_(N,N), and construct a sparser graph by replacing the edges of R with some (epsilon,delta)-superregular pair. If a graph H with Delta(H)<=Delta is embeddable into R(N), then it is already embeddable into G (Komlós et al. 1998).

See also

Szemerédi's Regularity Lemma

Explore with Wolfram|Alpha


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.

Referenced on Wolfram|Alpha

Blow-Up Lemma

Cite this as:

Weisstein, Eric W. "Blow-Up Lemma." From MathWorld--A Wolfram Web Resource.

Subject classifications