TOPICS

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

See also

Szemerédi's Regularity Lemma

Explore with Wolfram|Alpha

More things to try:

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.

Blow-Up Lemma

Cite this as:

Weisstein, Eric W. "Blow-Up Lemma." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Blow-UpLemma.html