Blow-up lemma
The blow-up lemma, proved by János Komlós, Gábor N. Sárközy, and Endre Szemerédi in 1997, 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. Definitions and Statement 
To formally state the blow-up lemma, we first need to define the notion of a super-regular pair. Super-regular pairs 
A pair  of subsets of the vertex set is called -super-regular if for every  and  satisfying

  and 

we have

 

and furthermore,

  for all  and  for all . Here  denotes the number of pairs  with  and  such that  is an edge. Statement of the Blow-up Lemma 
Given a graph  of order  and positive parameters , there exists a positive  such that the following holds. Let  be arbitrary positive integers and let us replace the vertices  of  with pairwise disjoint sets  of sizes  (blowing up). We construct two graphs on the same vertex set . The first graph  is obtained by replacing each edge  of  with the complete bipartite graph between the corresponding vertex sets  and . A sparser graph G is constructed by replacing each edge  with an -super-regular pair between  and . If a graph  with  is embeddable into  then it is already embeddable into G.

Proof Sketch 
The proof of the blow-up lemma is based on using a randomized greedy algorithm (RGA) to embed the vertices of  into  sequentially. The argument then proceeds by bounding the failure rate of the algorithm such that it is less than 1 (and in fact ) for an appropriate choice of parameters. This means that there is a non-zero chance for the algorithm to succeed, so an embedding must exist. Attempting to directly embed all the vertices of  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. The buffer vertices are subsequently embedded by using Hall's marriage theorem to find a perfect matching between the buffer vertices and the remaining vertices of . Notation 
We borrow all notation introduced in previous sections. Let . Since  can be embedded into , we can write  with  for all . For a vertex , let  denote . For ,

 

denotes the density of edges between the corresponding vertex sets of . is the embedding that we wish to construct. is the final time after which the algorithm concludes. Outline of the algorithm

Phase 0: Initialization 
 Greedily choose the set of buffer vertices  from the vertices of  as a maximal set of vertices distance at least  from each other 
 Order the remaining vertices (those in ) in a list , placing the neighbors of  first. Declare a queue  of presently prioritized vertices, which is initially empty. Declare an array of sets  indexed by the vertices of , representing the set of all "free spots" of , that is, the set of unoccupied vertices in  the vertex  could be mapped to without violating any of the adjacency conditions from the already-embedded neighbors of  in . is initialized to . Phase 1: Randomized Greedy Embedding 
 Choose a vertex  from the set of remaining vertices as follows:
 If the queue  of prioritized vertices is non-empty, then choose the vertex from 
 Otherwise, choose a vertex from the list  of remaining vertices
 Choose the image  in  for the vertex  randomly from the set of "good" choices, where a choice is good iff none of the new free-sets  differ too much in size from the expected value. Update the free sets , and put vertices whose free sets have become too small with respect to their size in the last update in the set of prioritized vertices 
 Abort if the queue  contains a sufficiently large fraction of any of the sets 
 If there are non-buffer vertices left to be embedded in either  or , update time  and go back to step 1; otherwise move on to phase 2. Phase 2: Kőnig-Hall matching for remaining vertices 
Consider the set of vertices left to be embedded, which is precisely , and the set of free spots . Form a bipartite graph between these two sets, joining each  to , and find a perfect matching in this bipartite graph. Embed according to this matching. Proof of correctness 
The proof of correctness is technical and quite involved, so we omit the details. The core argument proceeds as follows:

Step 1: most vertices are good, and enough vertices are free 
Prove simultaneously by induction on  that if  is the vertex embedded at time , then

 only a small fraction of the choices in  are bad
 all of the free sets  are fairly large for unembedded vertices

Step 2: the "main lemma" 
Consider , and  such that  is not too small. Consider the event  where

 no vertices are embedded in  during the first phase
 for every  there is a time  such that the fraction of free vertices of  in  at time  was small. Then, we prove that the probability of  happening is low. Step 3: phase 1 succeeds with high probability 
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 program aborts only when the queue is too long. The argument then proceeds by union-bounding over all modes of failure, noting that for any particular choice of ,  and  with  representing a subset of the queue that failed, the triple  satisfy the conditions of the "main lemma", and thus have a low probability of occurring. Step 4: no queue in initial phase 
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. Prove by induction on  that no vertices get added to the queue during the initial phase. It follows that all of the neighbors of the buffer vertices get added before the rest of the vertices. Step 5: buffer vertices have enough free spots 
For any  and , we can find a sufficiently large lower bound on the probability that , conditional on the assumption that  was free before any of the vertices in  were embedded. Step 6: phase 2 succeeds with high probability 
By Hall's marriage theorem, phase 2 fails if and only if Hall's condition is violated. For this to happen, there must be some  and  such that . cannot be too small by largeness of free sets (step 1). If  is too large, then with high probability , so the probability of failure in such a case would be low. If  is neither too small nor too large, then noting that  is a large set of unused vertices, we can use the main lemma and union-bound the failure probability. Applications 
The blow-up lemma has a number of applications in embedding dense graphs. Pósa-Seymour Conjecture 
In 1962, Lajos Pósa conjectured that every -vertex graph with minimum degree at least  contains the square of a Hamiltonian cycle, generalizing Dirac's theorem. The conjecture was further extended by Paul Seymour in 1974 to the following: 
 Every graph on  vertices with minimum degree at least  contains the -th power of a Hamiltonian cycle. 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  (for a fixed ) in 1998. Alon-Yuster Conjecture 
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:
 For every fixed graph  with  vertices, any graph G with n vertices and with minimum degree   contains  vertex disjoint copies of H.
They also conjectured that the result holds with only a constant (instead of linear) error:
 For every integer  there exists a constant  such that for every graph  with  vertices, any graph  with  vertices and with minimum degree  contains at least  vertex disjoint copies of . This conjecture was proven by Komlós, Sárközy, and Szemerédi in 2001 using the blow-up lemma. History and Variants 
The blow-up lemma, first published in 1997 by Komlós, Sárközy, and Szemerédi, 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, work on the Pósa-Seymour conjecture about the minimum degree necessary to contain the k-th graph power of a Hamiltonian cycle, and the proof of the Alon-Yuster conjecture on the minimum degree needed for a graph to have a perfect H-factor. 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. 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. Peter Keevash found a generalization of the blow-up lemma to hypergraphs in 2010. Stefan Glock and Felix Joos discovered a variant of the blow-up lemma for rainbow graphs in 2018. 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

References 

Graph theory
Lemmas in graph theory