The blow-up lemma, proved by János Komlós, Gábor N. Sárközy, and Endre Szemerédi in 1997,[1][2] is an important result in extremal graph theory, particularly within the context of the regularity method.
It states that the regular pairs in the statement of Szemerédi's regularity lemma behave like complete bipartite graphs in the context of embedding spanning graphs of bounded degree.
To formally state the blow-up lemma, we first need to define the notion of a super-regular pair.
then it is already embeddable into G.[1] The proof of the blow-up lemma is based on using a randomized greedy algorithm (RGA) to embed the vertices of
The argument then proceeds by bounding the failure rate of the algorithm such that it is less than 1 (and in fact
This means that there is a non-zero chance for the algorithm to succeed, so an embedding must exist.
in this manner does not work because the algorithm may get stuck when only a small number of vertices are left.
Instead, we set aside a small fraction of the vertex set, called buffer vertices, and attempt to embed the rest of the vertices.
Consider the set of vertices left to be embedded, which is precisely
The proof of correctness is technical and quite involved, so we omit the details.
The core argument proceeds as follows: Prove simultaneously by induction on
The only way that the first phase could fail is if it aborts, since by the first step we know that there is always a sufficient choice of good vertices.
The argument then proceeds by union-bounding over all modes of failure, noting that for any particular choice of
satisfy the conditions of the "main lemma", and thus have a low probability of occurring.
Recall that the list was set up so that neighbors of vertices in the buffer get embedded first.
The time until all of these vertices get embedded is called the initial phase.
, we can find a sufficiently large lower bound on the probability that
is a large set of unused vertices, we can use the main lemma and union-bound the failure probability.
[1][2][3] The blow-up lemma has a number of applications in embedding dense graphs.
contains the square of a Hamiltonian cycle,[4] generalizing Dirac's theorem.
The conjecture was further extended by Paul Seymour in 1974 to the following: The blow-up lemma was used by Komlós, Sárközy, and Szemerédi to prove the conjecture for all sufficiently large values of
[5] In 1995, Noga Alon and Raphael Yuster considered the generalization of the well-known Hajnal–Szemerédi theorem to arbitrary
-factors (instead of just complete graphs), and proved the following statement: They also conjectured that the result holds with only a constant (instead of linear) error: This conjecture was proven by Komlós, Sárközy, and Szemerédi in 2001 using the blow-up lemma.
[7] The blow-up lemma, first published in 1997 by Komlós, Sárközy, and Szemerédi,[1] emerged as a refinement of existing proof techniques using the regularity method to embed spanning graphs, as in the proof of the Bollobás conjecture on spanning trees,[8] work on the Pósa-Seymour conjecture about the minimum degree necessary to contain the k-th graph power of a Hamiltonian cycle,[9][4] and the proof of the Alon-Yuster conjecture on the minimum degree needed for a graph to have a perfect H-factor.
[7] The proofs of all of these theorems relied on using a randomized greedy algorithm to embed the majority of vertices, and then using a Kőnig-Hall like argument to find an embedding for the remaining vertices.
[1] The first proof of the blow-up lemma also used a similar argument.
Later in 1997, however, the same authors published another paper that found an improvement to the randomized algorithm to make it deterministic.
[2] Peter Keevash found a generalization of the blow-up lemma to hypergraphs in 2010.
[3] Stefan Glock and Felix Joos discovered a variant of the blow-up lemma for rainbow graphs in 2018.
[10] In 2019, Peter Allen, Julia Böttcher, Hiep Hàn, Yoshiharu Kohayakawa, and Yury Person, found sparse analogues of the blow-up lemma for embedding bounded degree graphs into random and pseudorandom graphs[11]