# Blow-up lemma

The **blow-up lemma** is a result in extremal graph theory, proved by [János Komlós](https://www.edgepedia.org/janos-komlos-mathematician), Gábor N. Sárközy, and [Endre Szemerédi](https://www.edgepedia.org/endre-szemeredi) and published in *Combinatorica* in 1997, stating that regular pairs of vertices behave like complete bipartite graphs from the point of view of embedding bounded-degree subgraphs<sup>[1](https://doi.org/10.1007/BF01196135)</sup>. Together with Szemerédi's regularity lemma, it forms the main general tool of the regularity method for finding spanning subgraphs in dense graphs<sup>[3](https://arxiv.org/abs/math/9612213)</sup>.

| Key fact | Detail |
|---|---|
| Statement | Regular pairs behave like complete bipartite graphs for embedding bounded-degree subgraphs<sup>[1](https://doi.org/10.1007/BF01196135)</sup> |
| Publication | Komlós, Sárközy, Szemerédi, *Combinatorica* 17, 109–123 (1997); received 16 August 1995<sup>[1](https://doi.org/10.1007/BF01196135)</sup> |
| Proof method | Randomized greedy embedding of most vertices, finished by a König-Hall argument<sup>[3](https://arxiv.org/abs/math/9612213)</sup> |
| Algorithmic version | Subgraph found in time \( O(n \cdot M(n)) \) with \( M(n) = O(n^{2.376}) \); parallelizable in \( NC^5 \)<sup>[3](https://arxiv.org/abs/math/9612213)</sup> |
| Landmark applications | Seymour's conjecture on powers of Hamilton cycles; the Alon-Yuster conjecture on \( H \)-factors<sup>[5](https://arxiv.org/abs/1011.1355)</sup> |
| Extensions | Hypergraph version (Keevash, 2011); sparse versions for random and pseudorandom graphs (Allen, Böttcher, Hàn, Kohayakawa, Person, 2016)<sup>[5](https://arxiv.org/abs/1011.1355)</sup><sup> • </sup><sup>[6](https://arxiv.org/abs/1612.00622)</sup> |

## Statement

The lemma is set up through a graph blow-up. Start with a graph \( R \) of order \( r \) and replace each vertex \( v_i \) with a pairwise disjoint set \( V_i \) of \( N \) vertices. Two graphs are built on the same vertex set \( V = \bigcup_i V_i \): the graph \( R(N) \), obtained by replacing every edge of \( R \) with a complete bipartite graph \( K_{N,N} \) between the corresponding sets, and a sparser graph \( G \), obtained by replacing each edge of \( R \) with an \( (\varepsilon, \delta) \)-super-regular pair<sup>[2](https://mathworld.wolfram.com/Blow-UpLemma.html)</sup>. A pair \( (A, B) \) is \( (\varepsilon, \delta) \)-super-regular if it is \( \varepsilon \)-regular and, in addition, every vertex of \( A \) has degree at least \( \delta|B| \) into \( B \) and every vertex of \( B \) has degree at least \( \delta|A| \) into \( A \)<sup>[9](https://doktori.bibl.u-szeged.hu/id/eprint/9833/34/Disszertacio.pdf)</sup>.

The lemma then says: for every \( \delta > 0 \) and \( \Delta, r \in \mathbb{N} \) there is an \( \varepsilon > 0 \) such that if \( H \) is a graph with maximum degree \( \Delta(H) \le \Delta \) that embeds into \( R(N) \), then \( H \) already embeds into \( G \)<sup>[2](https://mathworld.wolfram.com/Blow-UpLemma.html)</sup>. In other words, once the regularity lemma has reduced a dense host graph to a reduced graph \( R \) of clusters, and the target graph \( H \) of bounded maximum degree can be placed on the clusters of \( R \), the many edges missing inside the regular pairs do not obstruct the embedding. The bounded-degree restriction is essential: the lemma concerns spanning subgraphs of bounded maximum degree<sup>[3](https://arxiv.org/abs/math/9612213)</sup>.

## Role in the regularity method

Szemerédi's regularity lemma, published in 1976 in the form of regular partitions of graphs, approximates any graph by a bounded number of vertex classes, with the number of classes depending only on the desired accuracy and not on the number of vertices<sup>[1](https://doi.org/10.1007/BF01196135)</sup><sup> • </sup><sup>[5](https://arxiv.org/abs/1011.1355)</sup>. The regularity lemma alone is good at finding small graphs, but embedding a spanning graph \( H \) requires more, because every vertex of the host must be used and the error terms of the regularity approximation cannot be absorbed anywhere<sup>[4](https://www.researchgate.net/publication/259371303_The_Blow-up_Lemma)</sup>. The blow-up lemma supplies the missing step: after the regularity lemma produces a reduced graph \( R \) and the target \( H \) is mapped onto its clusters, the lemma guarantees that the embedding can be realized inside the super-regular pairs<sup>[3](https://arxiv.org/abs/math/9612213)</sup>.

**How the proof works.** The original proof is probabilistic and non-algorithmic. At a high level, the proof embeds most vertices of the graph with bounded degrees via a greedy randomized procedure, and then uses a König-Hall argument to complete the embedding<sup>[3](https://arxiv.org/abs/math/9612213)</sup>. Keevash's hypergraph proof follows the same template, a randomised greedy embedding algorithm, with additional complications from hypergraph regularity theory<sup>[5](https://arxiv.org/abs/1011.1355)</sup>.

## Applications

The lemma was developed as part of a method, based on the regularity lemma, for finding spanning subgraphs in dense graphs, and it can be applied to obtain approximate versions of many embedding conjectures of extremal graph theory<sup>[3](https://arxiv.org/abs/math/9612213)</sup><sup> • </sup><sup>[4](https://www.researchgate.net/publication/259371303_The_Blow-up_Lemma)</sup>. Komlós, Sárközy, and Szemerédi applied the lemma to establish Seymour's conjecture, which concerns how large a minimum degree suffices for embedding the \( k \)-th power of a Hamilton cycle, as well as the Alon-Yuster conjecture, which asks how large a minimum degree guarantees that a graph contains an \( H \)-factor for a fixed graph \( H \)<sup>[5](https://arxiv.org/abs/1011.1355)</sup>. A 2009 survey by Daniela Kühn and Deryk Osthus, both combinatorialists then working on large-scale embedding problems, records that the regularity lemma and the blow-up lemma had by then been used to solve several long-standing problems and conjectures, with main emphasis on \( F \)-packings, Hamiltonicity problems, and tree embeddings<sup>[8](https://www.cambridge.org/core/services/aop-cambridge-core/content/view/D76B0849140DA656B3CB4BB7CE90B7FF/9781107325975c6_p137-168_CBO.pdf/embedding_large_subgraphs_into_dense_graphs.pdf)</sup>.

The lemma also underlies the Bandwidth Theorem of Böttcher, Schacht, and Taraz, which confirms a conjecture of Bollobás and Komlós by giving a minimum-degree condition ensuring that every bounded-degree \( r \)-chromatic graph \( H \) on \( n \) vertices of bandwidth \( o(n) \) embeds into \( G \)<sup>[6](https://arxiv.org/abs/1612.00622)</sup>. In recent work the lemma remains a standard final step: in proofs for spanning structures in dense graphs, buffer vertices are reserved precisely for the application of the blow-up lemma<sup>[13](https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/plms.12552)</sup>, and in a 2025 result on cycles in sparse random graphs, the blow-up lemma is applied at the end to cover the remaining vertices with \( t \)-cycles<sup>[11](https://link.springer.com/article/10.1007/s00493-025-00171-1)</sup>.

## Algorithmic version

The original proof gives no procedure for constructing the embedding. In December 1996 the same three authors posted an algorithmic version, published in *Random Structures & Algorithms* in 1998, in which the desired subgraph of an \( n \)-vertex graph is found in time \( O(n \cdot M(n)) \), where \( M(n) = O(n^{2.376}) \) is the time to multiply two \( n \times n \) matrices with 0,1 entries over the integers; the algorithm can be parallelized and implemented in \( NC^5 \)<sup>[3](https://arxiv.org/abs/math/9612213)</sup><sup> • </sup><sup>[7](https://onlinelibrary.wiley.com/doi/abs/10.1002/%28SICI%291098-2418%28199805%2912%3A3%3C297%3A%3AAID-RSA5%3E3.0.CO%3B2-Q)</sup>. This answered the question raised by the earlier algorithmic version of the regularity lemma itself, which finds a regular partition in time \( O(M(n)) \) and runs in \( NC^1 \)<sup>[12](https://www.sciencedirect.com/science/article/pii/S0196677484710054)</sup>.

## Variants and extensions

**Hypergraphs.** In 2011, Peter Keevash, a combinatorialist then working at Queen Mary, University of London, extended the result to hypergraphs, demonstrating that sufficiently regular hypergraphs lacking atypical vertices can, when it comes to embedding bounded-degree hypergraphs, be treated as though they were complete<sup>[5](https://arxiv.org/abs/1011.1355)</sup>. The proof uses a randomised greedy embedding algorithm similar to the graph case, with the analysis complicated by hypergraph regularity theory and by the need to work with an approximating hypergraph<sup>[5](https://arxiv.org/abs/1011.1355)</sup>.

**Sparse host graphs.** Allen, Böttcher, Hàn, Kohayakawa, and Person proved sparse analogs for subgraphs of random and of pseudorandom graphs, in three regimes: embedding spanning graphs of maximum degree \( \Delta \) in subgraphs of \( G(n,p) \) with \( p = C(\log n/n)^{1/\Delta} \); embedding spanning graphs of maximum degree \( \Delta \) and degeneracy \( D \) in subgraphs of \( G(n,p) \) with \( p = C_{\Delta}(\log n/n)^{1/(2D+1)} \); and embedding spanning graphs of maximum degree \( \Delta \) in \( (p, cp^{\max(4,(3\Delta+1)/2)}n) \)-bijumbled graphs<sup>[6](https://arxiv.org/abs/1612.00622)</sup>. Such sparse blow-up lemmas are particularly useful for resilience results for spanning structures<sup>[6](https://arxiv.org/abs/1612.00622)</sup>.

**Beyond bounded degree.** Böttcher, Kohayakawa, Taraz, and Würfl generalized the lemma to \( a \)-arrangeable graphs, meaning graphs whose vertices admit an ordering such that, for each vertex \( v \), the vertices adjacent to \( v \) lying to its right collectively have no more than \( a \) neighbors on its left; this class includes planar graphs, and more broadly all graphs free of a \( K_s \)-subdivision for constant \( s \). Their main result embeds \( a \)-arrangeable graphs of maximum degree at most \( \sqrt{n}/\log n \) into corresponding systems of super-regular pairs, which is optimal up to the logarithmic factor<sup>[10](https://epubs.siam.org/doi/abs/10.1137/13093827X?journalCode=sjdmec)</sup>.

**Spread versions.** A 2024 spread blow-up lemma combines ideas on spread perfect matchings in super-regular bipartite graphs with an algorithmic blow-up lemma: there exists a probability measure over copies of the desired spanning graph \( H \) in a system of super-regular pairs that does not heavily pin down any subset of vertices, with output distribution \( O(1/N) \)-vertex-spread. This allows the blow-up lemma to be combined with the recently resolved Kahn-Kalai conjecture, and as an application the authors proved an approximate version of a conjecture of Böttcher, Parczyk, Sgueglia, and Skokan on the threshold for powers of Hamilton cycles in perturbed random graphs<sup>[14](https://arxiv.org/abs/2410.06132)</sup>.

## References

1. [Komlós, J., Sárközy, G.N. & Szemerédi, E. Blow-up Lemma. Combinatorica 17, 109–123 (1997).](https://doi.org/10.1007/BF01196135)
2. [Blow-Up Lemma, Wolfram MathWorld](https://mathworld.wolfram.com/Blow-UpLemma.html)
3. [Komlós, J., Sárközy, G.N., Szemerédi, E. An Algorithmic Version of the Blow-up Lemma. arXiv:math/9612213 (1996).](https://arxiv.org/abs/math/9612213)
4. [Komlós, J. The Blow-up Lemma. Combinatorics, Probability and Computing 8, 161–176 (1999).](https://www.researchgate.net/publication/259371303_The_Blow-up_Lemma)
5. [Keevash, P. A hypergraph blow-up lemma. arXiv:1011.1355; Random Structures & Algorithms 39, 275–376 (2011).](https://arxiv.org/abs/1011.1355)
6. [Allen, P., Böttcher, J., Hàn, H., Kohayakawa, Y., Person, Y. Blow-up lemmas for sparse graphs. arXiv:1612.00622 (2016).](https://arxiv.org/abs/1612.00622)
7. [Komlós, J., Sárközy, G.N., Szemerédi, E. An algorithmic version of the blow-up lemma. Random Structures & Algorithms 12, 297–312 (1998).](https://onlinelibrary.wiley.com/doi/abs/10.1002/%28SICI%291098-2418%28199805%2912%3A3%3C297%3A%3AAID-RSA5%3E3.0.CO%3B2-Q)
8. [Kühn, D., Osthus, D. Embedding large subgraphs into dense graphs. Surveys in Combinatorics 2009, Cambridge University Press.](https://www.cambridge.org/core/services/aop-cambridge-core/content/view/D76B0849140DA656B3CB4BB7CE90B7FF/9781107325975c6_p137-168_CBO.pdf/embedding_large_subgraphs_into_dense_graphs.pdf)
9. [Doctoral dissertation, University of Szeged, containing a statement of the Blow-up Lemma and super-regularity.](https://doktori.bibl.u-szeged.hu/id/eprint/9833/34/Disszertacio.pdf)
10. [Böttcher, J., Kohayakawa, Y., Taraz, A., Würfl, A. An Extension of the Blow-up Lemma to Arrangeable Graphs. SIAM Journal on Discrete Mathematics.](https://epubs.siam.org/doi/abs/10.1137/13093827X?journalCode=sjdmec)
11. [Trujić, M. Blow-up Lemma for Cycles in Sparse Random Graphs. Combinatorica 45, 52 (2025).](https://link.springer.com/article/10.1007/s00493-025-00171-1)
12. [Alon, N. et al. The Algorithmic Aspects of the Regularity Lemma. Journal of Algorithms 16, 80–109 (1994).](https://www.sciencedirect.com/science/article/pii/S0196677484710054)
13. [Lang, R. On sufficient conditions for spanning structures in dense graphs. Proceedings of the London Mathematical Society (2023).](https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/plms.12552)
14. [Spread blow-up lemma with an application to perturbed random graphs. arXiv:2410.06132 (2024).](https://arxiv.org/abs/2410.06132)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › General discrete mathematics and discrete structures › Combinatorics › Extremal and additive combinatorics › Regularity lemmas and removal lemmas*

*Initially written Sep 17, 2026 · Reviewed: Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license