Blow-up lemmas for sparse graphs

Blow-up lemmas for sparse graphs, Discrete Analysis 2025:8, 141 pp.

Szemerédi’s regularity lemma is, roughly speaking, the statement that for every graph $G$ and every $\epsilon>0$, we can partition the vertex set of $G$ into sets $V_1,\dots,V_k$ of almost equal size, with $k$ depending on $\epsilon$ only, in such a way that for all but at most $\epsilon k^2$ of the pairs $(i,j)$ the bipartite graph spanned by $V_i$ and $V_j$ enjoys a quasirandomness property known as $\epsilon$-regularity, which is all the bipartite graphs $G(A_i,A_j)$ induced by subsets $A_i$ and $A_j$ of $V_i$ and $V_j$ that are not too small have roughly the same density (which is therefore the density $d_{ij}$ of the bipartite graph $G(V_i,V_j)$ induced by $V_i$ and $V_j$).

We can then form a weighted “block graph” with vertex set $\{1,2,\dots,k\}$, where the edge joining $i$ to $j$ has weight equal to $d_{ij}$. This allows us to obtain approximations for the number of copies of some fixed small subgraph $H$ in $G$. For example, if $H$ is a triangle, we can choose vertices $x,y$ and $z$ at random and condition on which sets $V_i$ they lie in. If $x\in V_i, y\in V_j$ and $z\in V_h$, then the probability that $xy$ is an edge is $d_{ij}$, the probability that $xz$ is an edge given that $xy$ is an edge is approximately $d_{ih}$ (because one can check that almost all vertices in $V_i$ have roughly the same number of neighbours in $V_j$, so knowing that $xy$ is an edge gives almost no information about $x$) and the probability that $yz$ is an edge given that $xy$ and $xz$ are edges is roughly $d_{jh}$, at least assuming that $d_{ij}$ and $d_{ih}$ are not too small. So the number of triples $(x,y,z)\in V_i\times V_j\times V_h$ that form a triangle is roughly $d_{ij}d_{ih}d_{jh}|V_i||V_j||V_h|$. All that was assuming that the three pairs $(V_i,V_j), (V_i,V_h)$ and $(V_j,V_j)$ are $\epsilon$-regular, which is true almost all the time, so summing up, we obtain a good approximation for the number of triangles.

Often in graph theory, however, one wishes to prove results about embedding large graphs. The argument sketched above is sufficiently flexible to suggest that such embeddings ought to be possible under suitable conditions. For example, suppose for simplicity that $G$ is a quasirandom bipartite graph of density 1/2 with vertex sets $V_1$ and $V_2$ of equal size. We could ask whether $G$ must contain a Hamilton cycle. If we wanted to prove that it does, we could start by choosing a vertex $x_0$, then proceed in a random greedy way, picking a random neighbour $x_1$, then a random neighbour $x_2$ of $x_1$ not equal to $x_0$, and so on. Suppose we have picked $x_0,x_1,\dots,x_m$. If many vertices are still not yet chosen, and $x_m$ has many neighbours among those vertices (which will typically be the case, by the regularity property), then there will be many possibilities for $x_{m+1}$. Let us say in this case that $x_m$ is good. In that case, there will be many good choices for $x_{m+1}$, so the inductive procedure can continue until only a few vertices remain to be chosen. Thus, we can at least embed most of a Hamilton cycle.

It is clear that we cannot always embed a Hamilton cycle in its entirety, since a quasirandom graph can have isolated vertices. So one has to strengthen the condition on the graph to ensure that the minimum degree is large. A regular pair with this minimal-degree condition is called super-regular. More precisely, a pair $(V,W)$ is $(\epsilon,\delta)$-super-regular if for any two subset $A\subset V$ and $B\subset W$ with $|A|\geq\delta|V|$ and $|B|\geq\delta|W|$ there are at least $\epsilon|A||B|$ edges from $A$ to $B$, and also every vertex in $A$ has at least $\delta|B|$ neighbours in $B$ and vice versa. Note that the first condition is weaker than regularity, since it just asks for a lower bound on the densities.

The blow-up lemma states the following. Suppose we have a block graph with sufficiently large blocks and we replace all the $(\epsilon,\delta)$-super-regular pairs by complete bipartite graphs with the same vertex sets. Then any bounded-degree graph that can be embedded into the resulting larger graph can be embedded into the original one. It has been used in conjunction with Szemerédi’s regularity lemma to prove a large number of embedding results.

The argument sketched above for Hamilton cycles showed only that most of the Hamilton cycle could be embedded. To get the rest, one starts by setting aside a set of “buffer vertices” that are used at the end of the proof to modify the attempted embedding once it has got stuck.

This paper concerns analogues of the blow-up lemma for sparse graphs, which places it in a long tradition of “sparse random versions” of results initially proved for dense graphs (or more precisely formulated in a way that makes them non-trivial only for dense graphs). For example, Mantel’s theorem states that a graph with $n$ vertices and more than $\lfloor n/2\rfloor\lceil n/2\rceil$ edges must contain a triangle. A slightly more approximate version of this statement is that a subgraph of the complete graph of density greater than 1/2 must contain a triangle. The sparse random version of Mantel’s theorem replaces the complete graph by the random graph $G(n,p)$ for any $p$ greater by a constant factor than a trivial bound that turns out to be $cn^{-1/2}$. (Below that bound the number of triangles is smaller than, say, half the number of edges so the conclusion clearly does not hold.)

There are already sparse random versions of Szemerédi’s regularity lemma, so it is very natural to ask for a sparse random version of the blow-up lemma. In fact this paper proves three such results. In particular, it proves a blow-up lemma for graphs of maximum degree $\Delta$ in subgraphs of $G(n,p)$ provided that $p\geq C(\log n/n)^{1/\Delta}$. Note that $n^{-1/\Delta}$ is a natural barrier because below that, the probability of a given $\Delta$ vertices having a common neighbour dips below 1, which is a serious problem for any greedy procedure for choosing the vertices of the embedded subgraph. However, for many graphs that observation does not translate into a proof of optimality (up to the log factor): the paper contains a discussion of the degree to which the results are optimal.

Sparse random versions of combinatorial results are typically substantially harder to prove than their dense counterparts. The proof in this paper is no exception: again it proceeds algorithmically, but the algorithm is much more complicated, with several subprocedures that rely on ideas from earlier papers. However, the reward for this effort is a fundamental result with a diverse set of applications, some of them given in the paper and others proved subsequently.