$(X,Y)$ is an $(\eps_{a,b},d,p)$-lower-regular pair in a subgraph $G$ of $\Gamma$ with
$|X|\ge \eps'p^{\Delta-2}n/T^2$ and $|Y|\ge \eps' p^{\Delta-2}n/T^2$.
Let $Z$ be the set of vertices outside $X\cup Y$ such that $(N_\Gamma(z;X),N_\Gamma(z; Y))$ is not $(\eps_{a+1,b+1},d,p)$-lower-regular in $G$. By
choice of $p$, we have $\eps' p^{\Delta-2}n/T^2>C_1 p^{-2}\log n$.
Therefore  we can apply Lemma <ref> to conclude that

\[
|Z|\le C_1\max(p^{-2},p^{-1}\log n)\le\tfrac{\eps}{2T^2}C\max(p^{-2},p^{-1}\log n)<\eps p^{\Delta-2}n/T^2\,,
\]

again as desired.

Proof of <ref>:
Given $1\le i\le\Delta$, a set $U\subset V(\Gamma)$, and a family
$\mathcal{F}$ of pairwise
disjoint $\ell$-sets in $V(\Gamma)\setminus U$ with
$|U|\le|\mathcal{F}|\le\rho|V(\Gamma)|$, the graph $\AG(\Gamma,U,\mathcal{F})$
is a random bipartite graph with edge probability $p^\ell$ and
with parts $U$ and $\mathcal{F}$. So the expected number
of edges of $\AG(\Gamma,U,\mathcal{F})$ is $p^\ell|U||\cF|$. By the
Chernoff bound in
Theorem <ref> the probability that

\[\big|e\big(\AG(\Gamma,U,\mathcal{F})\big)\big|> 7p^\ell|U||\mathcal{F}|+\rho p^\ell
is at most

\[\exp\big(-\rho p^\ell n |\mathcal{F}|/T\big)\,.\]

If $|\mathcal{F}|=m\le\rho n$, then since $|U|\le|\mathcal{F}|$ we have $|U|\le
m$. Taking a union bound over $\ell$, over $m$, over the
at most $n^{m+1}$ choices for $U$ and its size, and over the at most $n^{\Delta m}$
choices for $\mathcal{F}$, we see that the probability of failure of
$\CON(\rho,T,\Delta)$ is at most

\begin{align*}
&\sum_{\ell=1}^\Delta\sum_{m=1}^{\rho n}n^{m+1} n^{\Delta
m}\exp\big(-\rho p^\ell n m/T\big) \le \Delta\sum_{m=1}^{\rho n}\exp\big(2\Delta
m\log n-\rho p^\Delta n m/T\big)\\
\le&\Delta\sum_{m=1}^{\rho n}\exp\big(-(\Delta+3)m
\log n \big)<\Delta n\exp\big(-(\Delta+2)\log n\big)<1/n\,,
\end{align*}

where the second inequality uses $p^\Delta n\ge C\log n$ and the choice of
We conclude that $G(n,p)$ a.a.s. has $\CON(\rho,T,\Delta)$ as desired.

Proof of <ref>:
Given integers $i,\ell\ge 1$ such that $i+\ell\le\Delta$, a set $U\subset V(\Gamma)$ of size at least $\eps p^i n/T^2$, and a family of pairwise
disjoint $\ell$-sets $\mathcal{F}$ in $V(\Gamma)\setminus U$, the graph $\AG(\Gamma,U,\mathcal{F})$
is a random bipartite graph with edge probability $p^\ell$ and
parts $U$ and $\mathcal{F}$. The expected number of edges it contains is therefore $p^\ell|U||\mathcal{F}|$.

We separate two cases. If $|\mathcal{F}|\le\eps|U|$, then we have $\Exp e\big(\AG(\Gamma,U,\mathcal{F})\big)\le \eps p^\ell|U|^2$, so by Theorem <ref> the probability of $e\big(\AG(\Gamma,U,\mathcal{F})\big)\ge 7\eps p^\ell|U|^2$ is at most

\[\exp\big(-6\eps p^\ell|U|^2\big)\le \exp\big(-6\eps^2 p^{i+\ell}n|U|/T^2\big)\le \exp(-3\Delta|U|\log n)\,.\]

Taking the union bound over the at most $\Delta^2$ choices of $i$ and $\ell$, at most $n^2$ choices of $|U|$ and $|\mathcal{F}|\le|U|$, the at most $n^{|U|}$ choices of $U$ and the at most $n^{\Delta|U|}$ choices of $\mathcal{F}$, we see that the probability that there exists such a choice with $e\big(\AG(\Gamma,U,\mathcal{F})\big)\ge 7\eps p^\ell|U|^2$ is at most

\[\Delta^2n^2n^{(\Delta+1)|U|}\exp(-3\Delta|U|\log n)\]

which tends to zero as $n$ tends to infinity.

Next we consider the case $|\mathcal{F}|\ge\eps |U|$. Again by Theorem <ref> the probability of $e\big(\AG(\Gamma,U,\mathcal{F})\big)\ge 7p^\ell|U||\mathcal{F}|$ is at most

\[\exp\big(-6p^\ell|U||\mathcal{F}|\big)\le \exp\big(-6\eps p^{i+\ell}n|\mathcal{F}|/T^2\big)\le \exp(-3\eps^{-1}\Delta|\mathcal{F}|\log n)\,.\]

Taking the union bound over the at most $\Delta^2$ choices of $i$ and $\ell$, at most $n^2$ choices of $|U|$ and $|\mathcal{F}|$, the at most $n^{|\mathcal{F}|/\eps}$ choices of $U$ and the at most $n^{\Delta|\mathcal{F}|}$ choices of $\mathcal{F}$, we see that the probability that there exists such a choice with $e\big(\AG(\Gamma,U,\mathcal{F})\big)\ge 7p^\ell|U||\mathcal{F}|$ is at most

\[\Delta^2n^2n^{(\Delta+1/\eps)|\mathcal{F}|}\exp(-3\eps^{-1}\Delta|\mathcal{F}|\log n)\]

which tends to zero as $n$ tends to infinity.
We conclude that $G(n,p)$ a.a.s. has $\LCON(\eps,T,\Delta)$ as desired.

§.§ Bijumbled graphs

In this subsection we will verify the neighbourhood size property, the
regularity inheritance property, and the lopsided neighbourhood size
property for bijumbled graphs, as stated in the following lemma.

For each $\Delta\in\NATS$ and $d,\eps'>0$
there exist $\eps_{a,b}>0$ for $0\le a,b\le\Delta$ and $\eps>0$
such that for each $T\in\NATS$ there is $c>0$ such that if
$p>0$ then any $(p,\beta)$-bijumbled graph on $n$ vertices has

$\NS(\eps,T,\Delta+1)$ if $\beta\le c p^{\Delta+1} n$,

$\RI(\eps,(\eps_{a,b}),\eps',d,T,\Delta+1)$ if $\beta\le cp^{\Delta+2}n$,

$\LNS(\eps,T,\Delta)$ if $\beta\le c p^{(3\Delta+1)/2}n$.

Let us briefly justify why we cannot use the congestion property in
bijumbled graphs. Indeed, blowing up a bijumbled graph by a factor
$\Delta$—that is, replacing vertices with independent $\Delta$-sets and
edges with complete bipartite graphs—degrades the bijumbledness only
slightly, but in this blow up the congestion condition fails badly: If we
choose $\ell=\Delta$ and as $\Delta$-tuples the blow ups of vertices, then
the congestion property fails by a factor $p^{\Delta-1}$.

In the proof of Lemma <ref>, Part <ref> is a
consequence of the regularity inheritance lemmas, Lemmas <ref>
and <ref>.  Parts <ref> and <ref> use
the following easy consequences of the definition of bijumbled graphs.

Let $\Gamma$ be a $(p,\beta)$-bijumbled graph on $n$ vertices and let
$W\subset V(\Gamma)$.

*  If $\eps\ge2\beta\frac1{pn}$, then $e(\Gamma)=(1\pm\eps)p\binom{n}{2}$.

*  $\deg_\Gamma(v;W)\neq(1\pm\eps)p|W|$
for at most $2 \beta^2/(\eps^{2} p^{2}|W|)$ vertices $v\in
V(\Gamma)\setminus W$.

From the definition of jumbledness (<ref>) we obtain

\[2e(\Gamma)=e_{\Gamma}(V,V)=pn^2\pm\beta n=pn^2\pm \eps pn^2/2\]

and <ref> follows.

For <ref> let $U$ be the set of
$v\in V(\Gamma)\setminus W$ with $\deg_\Gamma(v;W)>(1+\eps)p|W|$. We have

\[(1+\eps)p|U||W|<e(U,W)\le p|U||W|+\beta\sqrt{|U||W|}\]

and hence $ |U|<\beta^2/(\eps^{2} p^{2}|W|)$. Similarly, the number of
$v\in V(\Gamma)\setminus W$ with $\deg_\Gamma(v;W)<(1-\eps)p|W|$
is also at most $\beta^2/(\eps^{2} p^{2}|W|)$ and <ref> follows.

We can now prove Lemma <ref>.

Given $\Delta\ge 2$ and $d,\eps'>0$, we assume
$(1-\eps')^\Delta>1/2$. We choose $\eps_{a,b}$ for each $0\le a\le\Delta$ and
$0\le b\le\Delta$ as follows. We set
$\eps_{\Delta,\Delta}=\eps'/2$ and we define the other $\eps_{a,b}$ inductively.
For each $a$ and $b$, we require that $\eps_{a,b}$ is smaller than
the $\eps_0$ returned by Lemma <ref> with input
$\eps_{a+1,b}/2$ and $d$ (provided $a<\Delta$), and that returned with
input $\eps_{a,b+1}/2$ and $d$ (provided $b<\Delta$), and the $\eps_0$
returned by Lemma <ref> with input $\eps_{a+1,b+1}/2$ and $d$
(provided $a<\Delta,b<\Delta$). Let $\eps$ be the minimum of the
$\eps_{a,b}$. Note that we then have $\eps_{a,b}=\eps_{b,a}$ for each $a,b$.
Let $c'$ be the minimum of all the constants $c_0$ returned by the applications of
Lemmas <ref> and <ref>.
Given $T$, let
\[c=\tfrac12\eps^2\eps'c'T^{-2}\,.\]

Let $\Gamma$ be a $(p,\beta)$-bijumbled graph on $n$ vertices with
$\beta\le c p^{\Delta+1}n$.
By Proposition <ref><ref> the
graph $\Gamma$ has density $(1\pm\eps)p$.

Proof of <ref>: Let $W\subset V(\Gamma)$ be a set with
$|W|\ge \eps p^{\Delta}n/T^2$. By
Proposition <ref><ref> the number of
vertices $v\in V(\Gamma)\setminus W$ such that
$\deg(v;W)\neq(1\pm\eps)p|W|$ is at most

\begin{equation*}
\frac{2\beta^2}{\eps^2p^2\cdot \eps p^{\Delta}nT^{-2}}
\le\frac{2c^2T^2p^{\Delta}n}{\eps^3}\le\eps p^{\Delta}\frac{n}{T^2}\,,
\end{equation*}

and hence $\Gamma$ has $\NS(\eps,T,\Delta+1)$.

Proof of <ref>: Assume $\beta\le c p^{(3\Delta+1)/2}n$.
Let $0\le j\le\Delta$ and $W\subset V(\Gamma)$ be a set with
$|W|\ge \eps p^{\Delta+j}n/T^2$. By
Proposition <ref><ref> the number of
vertices $v\in V(\Gamma)\setminus W$ such that
$\deg(v;W)\neq(1\pm\eps)p|W|$ is at most

\begin{equation*}
\frac{2\beta^2}{\eps^2p^2\cdot \eps p^{\Delta+j}nT^{-2}}
\le\frac{2c^2T^2p^{2\Delta-j-1}n}{\eps^3}\le\eps p^{2\Delta-j-1}\frac{n}{T^2}\,,
\end{equation*}

and hence $\Gamma$ has $\LNS(\eps,T,\Delta)$.

Proof of <ref>:
We shall prove that $\Gamma$ has
$\RI(\eps,(\eps_{a,b}),\eps',d,T,\Delta+1)$ if $\beta\le cp^{\Delta+2}n$ by contradiction.
Given $0\le a\le\Delta-1$ and $0\le b\le\Delta$, suppose that $(X,Y)$ is
an $(\eps_{a,b},d,p)$-fully-regular pair in $G\subset\Gamma$ with
$|X|\ge \eps'p^{\Delta-1}n/T^2$ and $|Y|\ge \eps'p^{\Delta}n/T^2$.
Let $Z$ be the set of vertices $z\in V(\Gamma)\setminus(X\cup Y)$ such that $(N_\Gamma(z; X), Y)$ is
not $(\eps_{a+1,b},d,p)$-fully-regular in $G$. Assume for contradiction
that $|Z|\ge\eps p^{\Delta}n/T^2$.
Then we have $\max\big(|X||Y|,|X||Z|\big)\ge\eps\eps'p^{2\Delta-1}n^2/T^4$.
Therefore, by choice of $c$ and since $(\log_2\tfrac{1}{p})^{-1}>p$, we see that

\[
\beta\le
cp^{\Delta+2}n\le c'\eps\eps' p^{\Delta+2} n/T^2< c'p^2(\log_2
\tfrac{1}{p})^{-1/2}\sqrt{\max\big(|X||Y|,|X||Z|\big)}\,,
\]

and thus, $\Gamma$ is bijumbled enough to apply Lemma <ref>,
whose statement contradicts the assumption on $Z$.

Similarly, given $0\le a,b\le\Delta-1$, suppose that $(X,Y)$ is an
$(\eps_{a,b},d,p)$-fully-regular pair in $G\subset\Gamma$
with $|X|\ge \eps'p^{\Delta-1}n/T^2$ and $|Y|\ge
\eps'p^{\Delta-1}n/T^2$.  Let $Z$ be the set of vertices $z\in
V(\Gamma)\setminus(X\cup Y)$ such that $(N_\Gamma(z;X,N_\Gamma(z; Y)$ is not $(\eps_{a+1,b+1},d,p)$-fully-regular in
$G$. Again, assuming for contradiction that $|Z|\ge\eps p^{\Delta-1}n/T^2$, we have

\[\max\big(|X||Y|,|Y||Z|, |X||Z|\big)\ge\eps\eps'p^{2\Delta-2}n^2/T^4,\]

so that by choice of $c$, we see that

\[
\beta\le
cp^{\Delta+2}n\le c'\eps' p^{\Delta+2} n/T^2<
c'p^3 \sqrt{\max\big(|X||Y|,|Y||Z|, |X||Z|\big)}\,,
\]

hence the conclusion of Lemma <ref> contradicts the
assumption on $Z$.

§ THE GENERAL SETUP

This section constitutes the first step towards the proofs of our blow-up
lemmas. More or less, one can think of this section as showing that, for each of our blow-up lemmas, it suffices to prove a corresponding blow-up lemma in which several extra conditions are required. This reduction, as mentioned in the proof overview (Section <ref>) involves refining the partitions $\cXbl$ of $H$ and $\cVbl$ of $G$ given by the user of the blow-up lemma to obtain new partitions $\cX$ of $H$ and $\cV$ of $G$, which in turn entails replacing the reduced graphs $\Rbl$ and $\Rpbl$ with new graphs $R$ and $R'$, and altering various constants mentioned in the blow-up lemmas. It is convenient to keep using the letter choices seen in our blow-up lemmas for these altered partitions, graphs and constants in the proofs to come, so in this section we use the suffix $\mathrm{BL}$ for objects mentioned in one of our blow-up lemmas which we will alter for the proof, following the style of the previous sentence.

For convenience, we shall collect the various conditions on the graphs $H$
and $G$ that we assume in our blow-up lemmas and those extra conditions
that we derive in this section in a general setup (see
Definition <ref>) which we shall use in many forthcoming
lemmas. Moreover, we will define the concept of good partial
embedding (see Definition <ref>), which is a collection of
invariants we maintain in our proofs when embedding $H$.

This section is structured as follows.  In
Section <ref> we collect and describe, mainly as
reference for the reader, the various constants that appear in our blow-up
lemma proofs. Sections <ref> and <ref> then list
the properties we require of the refined partitions of $H$ and $G$,
respectively. In Section <ref> we prove that partitions with
these desired properties can be obtained from partitions supplied to our
blow-up lemmas. In Section <ref> we define some further key
concepts used in our embedding procedures, such as candidate sets,
available candidate sets and good partial embeddings, which then allows us
to formally define our general setup.  Finally, in
Section <ref>, we define the notion of bad vertices
which will, as explained in the proof overview, be vertices avoided in our
embedding process, and prove Lemma <ref> which states that most
vertices in candidate sets are not bad.

§.§ Constants

In the following chapters, sections and lemmas we will use various constants.
These are listed below, with their meaning. Firstly, we have
the following constants which are chosen by the user of our blow-up

$\Delta$ is the maximum degree of $H$.

$\Delta_J$ is the maximum number of times a vertex of $\Gamma$ is a
restricting vertex, that is, appears in a set $J_x$ for $x\in V(H)$.

$D$ is a constant governed by the degeneracy of $H$, which is only
used in the degenerate graphs blow-up lemma.

$d$ is the minimum $p$-density of regular pairs.

The user of our blow-up lemmas further chooses the constants $\DeltaRpbl$, $\alphabl$, $\zetabl$, $\kappabl$ and $\ronebl$ (the last after being given $\epsbl$ and $\rhobl$). However our preprocessing in Lemma <ref> changes the values of these constants (and the reduced graphs $R$ and $R'$), giving the following constants which we use in the rest of the paper.

$\DeltaRp$ is the maximum degree of the reduced graph $R'$, which captures
super-regular pairs.

$\alpha$ is the fraction of a part required to be potential buffer vertices.

$\zeta$ is the minimum relative size of any image restriction set $I_x$.

$\kappa$ is the balancing factor (greater than $1$), bounding
$|V_i|/|V_j|$ for any pair of clusters of $G$ (and hence parts of $H$).

$r_1$ is the upper bound on the number of clusters.

The blow-up lemmas guarantee the existence of the following constants.

$\epsbl$ is the regularity we require in the regular partition
provided by the user of the blow-up lemma.

$\rhobl$ is the fraction of vertices in each part of the partition of $H$ supplied by the user which may be
image restricted.

$C$ is large, only appears in the random graphs blow-up lemmas and is the
constant factor in the bound on the probability $p$.

$c$ is small, only appears in the bijumbled graphs blow-up lemma and is the
constant factor in the bound on the bijumbledness error term $\beta$.

Furthermore, the most important additional constants appearing in the
proofs of the blow-up lemmas are the following.

$\mu$ is the fraction of each cluster of $G$ contained in each of
the “small” sets of the partition of $G$, thus $|\Vq_i|=|\Vc_i|=|\Vbuf_i|=\mu|V_i|$ for each $i$.

$\vartheta$ comes into the maximum fraction $\rho p^{\vartheta}$ of each part of $H$ which may be image restricted. It is equal to either zero (proving Lemmas <ref> and <ref>) or $\Delta$ (proving Lemma <ref>).

$\rho$ appears in the maximum fraction $\rho p^{\vartheta}$ of each part of $H$ which may be image restricted. We also use $\rho$ for a second purpose (which does not conflict with the first one): it is the fraction of
non-image restricted vertices in $X_i$ which may enter the queue
during the RGA without causing the RGA to fail. Hence in total at most $2\rho|X_i|$ vertices of $X_i$ may enter
the queue during the RGA.

$\eps'$ is the global worst case regularity appearing in the proof
of the blow-up lemmas. That is, whenever we use the fact that a pair is
$(\cdot,d,p)$-regular in $G$, it will be at worst

$\eps_{a,b}$ is the worst case regularity in the proofs between
underlying restriction sets of adjacent vertices in $H$ with respectively
$a$ and $b$ previously embedded neighbours (see Section <ref> for
definitions of these terms).

$\eps$ is the initial regularity after pre-processing, and also controls the deterministic properties we require of $\Gamma$.

In order to make our proofs work it is enough to have constants in the size order

\begin{align*}
0 &< \eps\ll\eps_{a,b} \le\eps'
\ll\rho \ll\mu
\ll \alpha,\zeta,d,\Delta^{-1},\DeltaRp^{-1},\Delta_J^{-1},D^{-1},\kappa^{-1} \\
\text{and}\quad 0&<c,C^{-1} \ll r_1^{-1},\eps
\end{align*}

where by $x\ll y$ we mean that there is a non-decreasing function
$f\colon(0,1]\to(0,1]$ such that our proof works if $0<x\le f(y)$.  Observe
that the constants on the right hand sides are (effectively) chosen by the user of the
blow-up lemma. We remark
that one can then safely read this paper assuming that, for example, any
function of $\rho$ appearing in the proofs tending to zero
with $\rho$ is much smaller than any function of $\mu$ appearing in the
proofs tending to zero with $\mu$. However, for the convenience of
the reader wishing to verify the proofs, we specify our constants (more or less)
explicitly in each of the following results. We have made no attempt to optimise the values we give.

§.§ The partition of $H$

We shall refine the partition $\cXbl$ of $H$ given
as input to one of our blow-up lemmas to obtain a partition
$\cX=\{X_i\}_{i\in[r]}$ of $V(H)$ with some additional properties, which we
shall need in our proofs.  We shall also refine the given partition of $G$
(see Section <ref> for the properties we require from this
refined partition of $G$). In this subsection we will define the properties
that we require from the refined partition of $H$. To put this definition
into context (and provide some explanations on how it fits to the
refinement of the partition of $G$ in the subsequent subsection) we first need
some explanations concerning our strategy in the proofs of the blow-up

We shall (in a series of steps, some of which are performed in
this preprocessing step, and some of which are performed on later parts of
the proof) construct subsets $\Xmain_i$, $\Xq_i$, $\Xc_i$ and
$\Xbuf_i$ of $X_i$.
We define

\begin{equation*}
\Xmain=\bigcup_{i\in[r]}\Xmain_i \,,\quad
\Xq=\bigcup_{i\in[r]}\Xq_i \,,\quad
\Xc=\bigcup_{i\in[r]}\Xc_i \,,\quad
\Xbuf=\bigcup_{i\in[r]}\Xbuf_i \,.
\end{equation*}

Here, $\Xbuf_i\subset\tX_i$ contains the buffer vertices, which will
be chosen from the set of potential buffer vertices (see Section <ref>).
The set $\Xc$ is only used in the
proof of the random graphs blow-up lemma, Lemma <ref>; in the
other proofs we set $\Xc=\emptyset$. The vertices in $\Xc$ shall form the
reserved cliques which we will use to fix so-called buffer
defects (see Section <ref> for more details). We choose this set of vertices at the beginning of the proof of Lemma <ref>. Once we
chose $\Xbuf$ and $\Xc$, we set
$\Xmain_i:=X_i\setminus(\Xbuf_i\cup \Xc)$. These sets will have sizes
$|\Xbuf_i|=4\mu|X_i|$ and $|\Xc_i|\le\mu|X_i|$ and hence
$(1-5\mu)|X_i|\le|\Xmain_i|\le(1-4\mu)|X_i|$.  The set $\Xq\subset\Xmain$
will form the queue and only gets chosen during the embedding, in
the random greedy algorithm; it will also be of size at most $\mu|X_i|$.
We remark that in the following definition we shall only refer to the
sets $X_i$ and $\Xbuf_i$. We only chose to mention the sets $\Xq_i$ and $\Xc_i$
here as well because we need them to motivate the refinement of the
partition of $G$ in the next subsection.

The properties that we require of our refined partition and the buffer
vertices are collected in the following
definition. We remark that the reduced graphs $R$ and $R'$ used for this
refined partition are blow-ups of the reduced graphs $\Rbl$ and $\Rpbl$ provided to the
respective blow-up lemma. These properties bound the number of buffer vertices per part, and state that the first and second
neighbourhoods of buffer vertices lie along edges of $R'$.
They also assert that any pair of vertices
within one part $X_i$, but also any pair of buffer vertices, and any pair
consisting of a buffer vertex and an image restricted vertex, are far apart. Note that this implies that $H[X_i,X_j]$ forms a matching for any
pair of parts $X_i$ and $X_j$, and it also implies that buffer vertices may
not be image restricted. We further require that all vertices in
any one $\Xbuf_i$ have the same degree, and distinguish between clique buffers
and non-clique buffers. The latter will be important for the selection of
reserved cliques in the proof of Lemma <ref> (Section <ref>).

We say that a partition
$\cX=\{X_i\}_{i\in[r]}$ of $V(H)$ is a good $H$-partition for
reduced graphs $R'\subset R$ on vertex sets $[r]$,
with buffer $\tcX=\{\tX_i\}_{i\in[r]}$, buffer vertices
$\Xbuf\subset\bigcup_{i\in[r]}\tX_i$ and image restricting vertices
$\cJ=\{J_x\}_{x\in  V(H)}$,
the following
conditions are satisfied for each $i,j,k\in[r]$.

*  $(H,\cX)$ is an $R$-partition and $\tcX$ is an
$(\alpha,R')$-buffer for $H$.

*  $\dist_H(x,y)\ge
10$ and $J_x\cap J_{y}=\emptyset$ for each $x,y\in X_i$ with $x\neq y$.

*  $|\Xbuf_i|=4\mu|X_i|$,
and $|\{x\in X_i\colon x\in N(\Xbuf)\}|\le 4\kappa\DeltaRp\mu|X_i|$.

*  $\dist_H(x,y)\ge 5$ for each $x,y\in\Xbuf$ with
$x\neq y$.

*  $\dist_H(x,y)\ge 3$ for each $x\in\Xbuf$ and each image restricted $y$.

*  All vertices of $\Xbuf_i$ have degree $b$ for some $0\le b\le\Delta$.
We then call $\Xbuf_i$ a degree-$b$ buffer.

*  Either all or none of the vertices of $\Xbuf_i$ are in copies of
$K_{\Delta+1}$. We then call $\Xbuf_i$ a clique buffer or non-clique
buffer, respectively.

*  If $\Xbuf_i$ is a clique buffer, then at
least $\tfrac{1}{2\Delta+4}\alpha|X_i|$ vertices of $\tX_i$ are in copies
of $K_{\Delta+1}$ which do not contain either vertices of $\Xbuf$ or
image restricted vertices.

Note that in this definition we do need to know about image restricting vertices (since they play a rôle in <ref>), which are in $\Gamma$, and we do need to know which vertices of $H$ are image restricted (since they play a rôle in <ref>), but we do not need to know anything about $G$.

§.§ The partition of $G$

We next define the properties we require from our refined partition
of $G$. Firstly, we shall subdivide each cluster of the partition $\cVbl$ of $G$, which is given as input to one of our blow-up lemmas, into several new
clusters to obtain a new partition $\cV$ matching the refined partition of $H$. Further, as also mentioned
in the proof overview, we shall partition each new cluster $V_i$ into parts
$\Vmain_i$, $\Vq_i$, $\Vc_i$ and $\Vbuf_i$.
Again, we set

\begin{equation*}
\Vmain=\bigcup_{i\in[r]}\Vmain_i \,,\quad
\Vq=\bigcup_{i\in[r]}\Vq_i \,,\quad
\Vc=\bigcup_{i\in[r]}\Vc_i \,,\quad
\Vbuf=\bigcup_{i\in[r]}\Vbuf_i \,.
\end{equation*}

As previously indicated, each vertex $x\in V(H)$ will be embedded into the cluster $V_i$
such that $x\in X_i$. In the rest of the paper, we often refer to $V_i$ simply by
$V(x)$, to $\Vmain_i$ by $\Vmain(x)$, and so on, to avoid the use of
indices whenever these are not important.

As explained before, most of the vertices from $\Vmain$ will be used to
embed most vertices of $\Xmain$, while some vertices from $\Vq$ will be
used to embed the remainder, which constitutes the queue $\Xq$. We also have the set $\Vc$, the clique
reservoir, that we will use in the proof of the random graphs blow-up
lemma to embed some of the vertices in $\Xc$. Some vertices of each $\Xc_i$ may need
to be used to fix so-called buffer defects, and these could be embedded
anywhere in $V_i$. All other vertices of each $\Xc_i$ get embedded to $\Vc_i$.
Finally, the vertices from
$\Vbuf$ together with all remaining vertices of $\Vmain\cup\Vq\cup\Vc$,
that is, vertices that were not
used when embedding $\Xmain\cup\Xq\cup\Xc$,
will be used for embedding the buffer vertices $\Xbuf$.

The properties we require of a good $G$-partition are as follows. It must be a regular $R$-partition, and furthermore the one-sided and two-sided inheritance properties of $\cVbl$ on $\Rpbl$ must be transferred to $\cV$ on $R'$. The super-regularity properties of $\cVbl$ on $\Rpbl$ must be transferred to give minimum degree conditions for each of the parts $\Vmain_i$, $\Vq_i$ and $\Vc_i$. Finally, we need to create new image restriction sets $\cI$ from the supplied $\cIbl$ which with the (unchanged) $\cJ$ form a restriction pair.

Given a good $H$-partition of $V(H)$ for reduced graphs $R'\subset R$ on
vertex sets $[r]$, with buffer $\tcX=\{\tX_i\}_{i\in[r]}$ and buffer vertices
$\Xbuf\subset\bigcup_{i\in[r]}\tX_i$, with
image restrictions $\cI=\{I_x\}_{x\in V(H)}$, and restricting vertices
$\cJ=\{J_x\}_{x\in V(H)}$, we say that a partition
$\cV=\{V_i\}_{i\in[r]}$ of $V(G)$ with a partition
$V_i=\Vmain_i\dcup\Vq_i\dcup\Vc_i\dcup \Vbuf_i$ of each cluster
is a good $G$-partition for
$R'\subset R$, if
the following conditions are satisfied.

For each $i$ we have $|\Vmain_i|=(1-3\mu)|V_i|$ and $|\Vq_i|=|\Vc_i|=|\Vbuf_i|=\mu|V_i|$.

$(G,\cV)$ is an $(\eps,d,p)$-regular $R$-partition,
has one-sided inheritance on $R'$,
and two-sided inheritance on $R'$ for $\tcX$.

For each $ij\in R'$ and $v\in V_i$, we have

\begin{align*}
\deg_G(v;\Vmain_j)&\ge(1-3\mu)(d-\eps)\max\big(p|V_j|,\deg_\Gamma(v;V_j)/2\big)\,,\\
\deg_G(v;\Vq_j)&\ge\mu(d-\eps)\max\big(p|V_j|,\deg_\Gamma(v;V_j)/2\big)\,,\\
\deg_G(v;\Vc_j)&\ge\mu(d-\eps)\max\big(p|V_j|,\deg_\Gamma(v;V_j)/2\big) \,.
\end{align*}

For each $x\in X_i$, we have

\begin{align*}
|I_x\cap \Vmain_i|&\ge(1-\eps)(1-3\mu)|I_x|\,,\\
|I_x\cap\Vq_i|\,,\,|I_x\cap \Vc_i|\,,\,|I_x\cap\Vbuf_i|&\ge(1-\eps)\mu|I_x|\,,\\
\big|\comN(J_x;\Vmain_i)\big|&=\big(1\pm\eps\big)(1-3\mu)p^{|J_x|}|V_i|\,,\text{ and}\\
\big|\comN(J_x;\Vq_i)\big|\,,\,\big|\comN(J_x;\Vc_i)\big|\,,\,\big|\comN(J_x;\Vbuf_i)\big|&=\big(1\pm\eps\big)\mu p^{|J_x|}|V_i|\,.
\end{align*}

$\cI$ and $\cJ$ form a $(\rho p^\vartheta,\zeta,\Delta,\Delta_J)$-restriction pair
for the partitions $\cX$ and $\cV$.

*  For each $i$, the number of image restricted vertices in $X_i$ is
at most $\rho p^\vartheta|X_i|$.

Note that the sizes of the sets $\Vmain_i$, $\Vq_i$, $\Vc_i$, $\Vbuf_i$
are not be the same as the sizes of the sets $\Xmain_i$, $\Xq_i$,
$\Xc_i$ and $\Xbuf_i$.  For example we will have
$|\Xmain_i|=(1-4\mu)|X_i|<(1-3\mu)|V_i|=|\Vmain_i|$, and
$|\Xq_i|,|\Xc_i|\le 2\rho|X_i|$, which is much smaller than $\mu
|V_i|$. Thus, the subsets $\Xmain_i$, $\Xq_i$, $\Xc_i$ of $X_i$ will be
significantly smaller than the corresponding set in $V_i$, while the set
$\Xbuf_i$ is larger than $\Vbuf_i$.
We also note that we do require two-sided inheritance for $\tcX$ in <ref>, not just for $\Xbuf$. In the proof of Lemma <ref>, when dealing with buffer defects, we will make use of this stronger statement.

§.§ Obtaining a good $H$-partition and a good $G$-partition

The following lemma proves that we can obtain good partitions of $H$
and $G$ from the partitions provided to our blow-up lemmas. The proof of
this lemma is straightforward, though not short since several conditions
must be checked. Briefly, the idea is that we will draw an auxiliary graph
$F_i$ on each part $\Xbl_i$ of $\cXbl$ with edges joining pairs of vertices
which are at distance less than $10$ or share an image restricting
vertex. We will apply our modification of the Hajnal-Szemerédi theorem
(Lemma <ref>) to each of these graphs together with the
set $\tX_i$ to obtain a partition $\cX$ and reduced graphs $R$ and $R'$
satisfying the first three conditions of a good $H$-partition, and then
construct the sets $\Xbuf_i$ greedily to obtain the remaining
properties. We will then randomly refine the partition $\cVbl$ to obtain a
matching partition $\cV$, and further randomly split each part $V_i$ of
$\cV$ into $\Vmain_i$, $\Vq_i$, $\Vc_i$ and $\Vbuf_i$. We will use the
concentration inequalities in Theorem <ref> to obtain
concentration for various set sizes in the randomly chosen parts, which in
particular show that with high probability we obtain the desired good
$G$-partition. We stress that although $p$ with a lower bound reminiscent
of our random graph blow-up lemmas makes an appearance in the lemma
statement, this does not mean we are going to assume $\Gamma$ is a random
graph. We will simply need to know that the quantity $p^bn$ is large
compared to $\log n$.

For all positive integers $\Delta$, $\DeltaRp$, $\Delta_J$, $r_1$, $\vartheta$ and
$b$, all $\kappa>2$, all $\alpha,\zeta,d,\eps>0$, and all sufficiently small $\mu,\rho>0$, there exists
$C$ such that the following holds whenever $p\ge C\big(\tfrac{\log
n}{n}\big)^{1/b}$ and $n>C$. Let
$\delta=\tfrac{1}{8}(\Delta+\Delta_J)^{-10}$ and $r\le r_1$.

Let $\Rbl$ be a graph on $\rbl=\delta r$ vertices and let $\Rpbl\subset \Rbl$ be a spanning
subgraph with $\Delta(\Rpbl)\leq \DeltaRpbl=\delta\DeltaRp$.
Let $H$ and $G\subset\Gamma$ be graphs with $\tfrac12\kappa$-balanced
size-compatible vertex partitions
$\cXbl=\{\Xbl_i\}_{i\in[\rbl]}$ and $\cVbl=\{\Vbl_i\}_{i\in[\rbl]}$,
respectively, which have parts of size at least $2n/(\kappa\delta r_1)$.
Let $\tcXbl=\{\tXbl_i\}_{i\in[\rbl]}$ be a family of subsets of $V(H)$,
$\cIbl=\{\Ibl_x\}_{x\in V(H)}$ be a family of image restrictions, and
$\cJ=\{J_x\}_{x\in  V(H)}$  be a family of restricting vertices.
Suppose that

* $\Delta(H)\le\Delta$, $(H,\cXbl)$ is an $\Rbl$-partition,
and $\tcXbl=\{\tXbl_i\}_{i\in[\rbl]}$ is a
$(2\alpha,\Rpbl)$-buffer for $H$,

* $(G,\cVbl)$ is a $\big(\tfrac{1}{2}\delta\eps,d,p\big)$-regular $\Rbl$-partition, which is
$\big(\tfrac{1}{2}\delta\eps,d,p\big)$-super-regular on $\Rpbl$,
has one-sided inheritance on $R'$, and two-sided inheritance on $R'$ for $\tcXbl$,

*  $\cIbl$ and $\cJ$ form
a $\big(\tfrac{1}{2}\delta\rho p^\vartheta,2\zeta,\Delta,\Delta_J\big)$-restriction pair ,
and $|J_x|\le b$ for each $x\in V(H)$.

Then there is a graph $R$ on $r$ vertices and a spanning subgraph
$R'\subset R$ with $\Delta(R')\le\DeltaRp$, together with
$\kappa$-balanced size-compatible partitions $\cX=\{X_i\}_{i\in[r]}$
of $H$ and $\cV=\{V_i\}_{i\in[r]}$ of $G$, which have parts of size at
least $n/(\kappa r_1)$, a family $\tcX=\{\tX_i\}_{i\in[r]}$ of potential
buffer vertices, a family $\cI=\{I_x\}_{x\in V(H)}$ of image restrictions,
subsets $\Xbuf_i\subset\tX_i$ for each $i\in[r]$, and a partition
$V_i=\Vmain_i\dcup\Vq_i\dcup\Vc_i\dcup\Vbuf_i$ for each $i\in[r]$,
which give a good $H$-partition and a corresponding good $G$-partition.

Let $\delta=\tfrac18(\Delta+\Delta_J)^{-10}$.
We set $C=10^6\delta^{-1}\mu^{-1}\eps^{-2}d^{-\Delta}\zeta^{-1}\kappa r_1$.
We require

\[\mu<\frac{\alpha}{10000\kappa\DeltaRp^4\Delta^{10}(\Delta+2)}\qquad\text{and}\qquad \rho\le\mu\,.\]

First we refine the vertex partition $\cXbl$  of $H$ to obtain properties <ref> and <ref>.
For each $i\in[\rbl]$ we define a graph $F_i$ on the vertex set $\Xbl_i$ by putting an edge between $x$ and $x'$ whenever either $J_x\cap J_{x'}\neq\emptyset$ or $x$ and $x'$ are at distance less than $10$ in $H$. Observe that $\Delta(F_i)\le(\Delta+\Delta_J)^{10}$. We now apply Lemma <ref> to $F_i$ with the set $\tXbl_i$. This returns an equitable partition of the vertices $\Xbl_i$ into independent sets in $F_i$ which also partitions $\tXbl_i$ equitably. We do this for each $i\in[\rbl]$ to obtain a partition $\cX$ of $V(H)$ into $8(\Delta+\Delta_J)^{10}\rbl=\delta^{-1}\rbl=r$ parts and a family $\tcX=\{\tX_i\}_{i\in[r]}$. We let $R$ be the graph obtained from $\Rbl$ by replacing each vertex with an independent set on $8(\Delta+\Delta_J)^{10}=\delta^{-1}$ vertices, and each edge with a complete bipartite graph between the corresponding sets. We obtain $R'$ similarly from $\Rpbl$. Thus $(H,\cX)$ is an $R$-partition, satisfying <ref> by construction. Furthermore, we have $\Delta(R')=\delta^{-1}\Delta(\Rpbl)\le\DeltaRp$.

Since each $\Xbl_i$ with $i\in[\rbl]$ has size at least $2n/(\kappa\delta r_1)$ and is equipartitioned into $\delta^{-1}$ parts, we see that, because $n$ is chosen sufficiently large, we have $|X_i|\ge n/(\kappa r_1)$ for each $i\in[r]$. Given $i,j\in[r]$ let $i',j'\in[\rbl]$ be such that $X_i\subset\Xbl_{i'}$ and $X_j\subset\Xbl_{j'}$. Then we have

\[|X_i|\le\delta|\Xbl_{i'}|+1\le\tfrac{\kappa}{2}\delta|\Xbl_{j'}|+1\le \tfrac{\kappa}{2}(|X_j|+1)+1\le\kappa|X_j|\]

where the final inequality is since $|X_j|\ge n/(\kappa r_1)$ and $n$ is sufficiently large. Thus $\cX$ is $\kappa$-balanced.

Given $i\in[r]$ let $i'\in[\rbl]$ be such that $X_i\subset\Xbl_{i'}$. Then we have

\[|\tX_i|\ge \delta|\tXbl_{i'}|-1\ge 2\alpha\delta|\Xbl_{i'}|-1\ge 2\alpha(|X_i|-1)-1\ge\alpha|X_i|\]

where again the final inequality is since $n$ is sufficiently large. Thus $\tcX$ forms an $(\alpha,R')$-buffer for $H$.

Before we verify the remaining good $H$-partition properties, it is convenient to check <ref>. By assumption <ref> of the lemma, at most $\tfrac12\delta\rho p^\vartheta|\Xbl_{i'}|$ vertices of any given $\Xbl_{i'}$ are image restricted. Thus for any $i$ such that $X_{i}\subset \Xbl_{i'}$, at most

\[\tfrac12\delta\rho p^\vartheta|\Xbl_{i'}|\le\tfrac12\rho p^\vartheta\big(|X_{i}|+1\big)\le\rho p^\vartheta|X_{i}|\]

vertices of $X_{i}$ are image restricted, as required for <ref>.

We proceed with properties <ref>–<ref> by choosing buffer vertices $\Xbuf_i$ from the potential buffer vertices $\tX_i$ for each $i\in[r]$ sequentially. For a given $i\in[r]$, we first decide on the degree of the buffer and whether or not it is a clique buffer. We split the vertices of $\tX_i$ into $\Delta+2$ subsets, one for each of the possible degrees in $\{0,\dots,\Delta-1\}$, one for vertices of degree $\Delta$ not in copies of $K_{\Delta+1}$, and one for vertices in copies of $K_{\Delta+1}$. We take a largest one $S_i$ of these sets, and will choose $\Xbuf_i$ within it. We do this greedily, one vertex at a time, always picking a vertex at distance at least five from previously chosen buffer vertices, and at distance at least three from any image restricted vertices. We now justify that it is possible to do this, that is, that we can pick the desired $4\mu|X_i|$ vertices in $S_i$ without running out of vertices in $S_i$.

Since all neighbours (respectively, second neighbours) in $H$ of vertices in $\tX_i$ are in clusters $V_j$ with $ij\in R'$ (respectively, $V_k$ with $ij,jk\in R'$), by <ref>, verified above, it follows that the number of image restricted vertices at distance $2$ or less to a vertex of $\tX_i$ is at most $(\DeltaRp^2+\DeltaRp+1)\rho\kappa|X_i|$. Each of these vertices has at most one neighbour or second neighbour in $\tX'_i$, since the distance between any two vertices of $X_i$ is at least ten. Similarly, if $x$ is in some $\tX_k$ and is at distance four or less from some vertex of $\tX_i$, then the path between $x$ and $\tX_i$ follows edges of $R'$, and there is only one vertex of $\tX_i$ which is at distance four or less from $x$. Thus the total number of vertices of $\tX_i$ which are at distance four or less from some vertex of $\Xbuf$ is at most
\[(1+\DeltaRp+\DeltaRp^2+\DeltaRp^3+\DeltaRp^4)\cdot 4\mu\kappa|X_i|\,.\]

Since $|S_i|\ge\tfrac{1}{\Delta+2}|\tX_i|$, it follows that at each step the number of vertices in $S_i\subset \tX_i$ we have to choose from is at least

\[\tfrac{1}{\Delta+2}\alpha|X_i|-3\DeltaRp^2\rho\kappa|X_i|-20\DeltaRp^4\mu\kappa|X_i|\,,\]

which is greater than $\tfrac{1}{2\Delta+4}\alpha|X_i|$ by choice of $\mu$ and $\rho$. Thus we can always choose the desired vertices of $\Xbuf_i$, giving <ref>–<ref>. In the event that $\Xbuf_i$ is a clique buffer, we have at the end at least $\tfrac{1}{2\Delta+4}\alpha|X_i|$ vertices of $\tX_i$ remaining which are in copies of $K_{\Delta+1}$ (by definition of $S_i$) that do not contain either vertices in $\Xbuf$ or image restricted vertices, giving <ref>.

Finally, neighbours of $\Xbuf$ in $X_i$ must be in parts $X_j$ such that $ij\in R'$. Since any two vertices in $X_i$ are at distance at least ten, each such vertex has at most one neighbour in $X_i$ and so at most $\DeltaRp4\mu\kappa|X_i|$ vertices of $X_i$ are in $N(\Xbuf)$, completing <ref>. This establishes that we have a good $H$-partition.

We now construct a corresponding good $G$-partition. The construction is simple: for each $\Vbl_i\in\cVbl$ we choose, uniformly at random, an equitable partition into $\delta^{-1}$ parts, which parts we associate (arbitrarily) to subparts of $\Xbl_i$ of corresponding size, obtaining $\cV$. Note that this is possible since $|Xbl_i|=|\Vbl_i|$. We then, for each $i\in[r]$, choose uniformly at random a partition of $V_i$ into one set of size $(1-3\mu)|V_i|$ and three of size $\mu|V_i|$, which form $\Vmain_i$, $\Vq_i$, $\Vc_i$ and $\Vbuf_i$ respectively. For each $x\in V_i$, we let $I_x=\Ibl_x\cap V_i$.

By construction $\cX$ and $\cV$ are size-compatible, so what remains is to show that $\cV$ is with positive probability a good $G$-partition. In fact, we will show this holds asymptotically almost surely. Recall that we have already established <ref>, and by construction <ref> holds, so that the remaining conditions are <ref>–<ref>.

Observe that the sets $V_i$, $\Vmain_i$, $\Vq_i$, $\Vc_i$ and $\Vbuf_i$ are all distributed as the uniform random set of that size within $\Vbl_{i'}$, where $V_i\subset \Vbl_{i'}$, though they are of course not independent. It follows that for any set $U\subset \Vbl_{i'}$, the sizes of each of the sets $V_i\cap U$, $\Vmain_i\cap U$, $\Vq_i\cap U$, $\Vc_i\cap U$ and $\Vbuf_i\cap U$ are hypergeometrically distributed, each with (since $n$ is sufficiently large) expectation at least $\tfrac12\mu\delta|U|$. In particular, if $|U|\ge 10^3\eps^{-2}\log n$, then the probability that any given one of these sizes is not within a $\big(1\pm\tfrac{\eps}{10}\big)$-factor of its expectation is by Theorem <ref> at most

\[2e^{-\eps^2|U|/300}\le n^{-2}\,.\]

We now give various sets $U$ to which we will apply this observation, and verify that each is sufficiently large.
For each $ij\in R'$ and each $v\in V_j$, by construction of $R'$ and since $(G,\cVbl)$ is super-regular on $\Rpbl$, we have

\begin{align*}
\deg_\Gamma(v;\Vbl_{i'})&\ge \deg_G(v;\Vbl_{i'})\\
&\ge (d-\eps)\max\big\{p|\Vbl_{i'}|,\tfrac12\deg_\Gamma(v;\Vbl_{i'})\big\}\ge10^3\eps^{-2}\log n\,,
\end{align*}

where the final inequality holds by choice of $p$ and $C$. We can thus take $U$ to be $N_\Gamma(v;\Vbl_{i'})$ or $N_G(v;\Vbl_{i'})$.

For each $x\in X_i$, where $X_i\subset\Xbl_{i'}$, since $\big(\cIbl,\cJ\big)$ form a $\big(\tfrac12\delta\rho,2\zeta,\Delta,\Delta_J\big)$-restriction pair, we have

\[\big|\comN_\Gamma(J_x;\Vbl_{i'})\big|\ge |\Ibl_x|\ge\zeta(dp)^{|J_x|}|\Vbl_i|\ge 10^3\eps^{-2}\log n\,,\]

where the final inequality comes from the assumption $|J_x|\le b$ and our choice of $p$ and $C$. We can thus also take $U$ to be $\comN_\Gamma(J_x;\Vbl_{i'})$ or $I_x$.

In total, we have at most $5r$ randomly chosen sets in which we are interested, and at most $4n$ choices of $U$ with which we intersect the random sets. Taking the union bound, we see that a.a.s. each of these intersections has size within a $\big(1\pm\tfrac{\eps}{10}\big)$-factor of its expectation. In particular, there exists a partition $\cV$ in which each of these intersections is within a $\big(1\pm\tfrac{\eps}{10}\big)$-factor of its expectation. We fix such a partition, and prove that it is the desired good $G$-partition.

We begin with <ref>. Suppose $ij\in R$. Then $V_i$ and $V_j$ come from two parts $\Vbl_{i'}$ and $\Vbl_{j'}$ of $\cVbl$ which form a $\big(\tfrac{1}{2}\delta\eps,d,p\big)$-regular pair, and we have $|V_i|>\tfrac12\delta|\Vbl_{i'}|$ and $|V_j|>\tfrac1{2}\delta|\Vbl_{j'}|$. It follows from the definition that $(V_i,V_j)$ is $(\eps,d,p)$-regular, so $(G,\cV)$ forms an $(\eps,d,p)$-regular $R$-partition. Given now $ij,jk\in R'$, with $V_j\subset\Vbl_j$ and $V_k\subset\Vbl_k$, and any $v\in V_i$, we have by construction of $\cV$ that $|\big|N_\Gamma(v;V_j)\big|\ge\tfrac12\delta\big|N_\Gamma(v;V_{j'})\big|$ and that $|V_k|\ge\tfrac12\delta|V_{k'}|$. Since the pair $\big(N_\Gamma(v;V_{j'}),V_{k'}\big)$ is $\big(\tfrac12\delta\eps,d,p\big)$-regular in $G$, it follows from the definition that the pair $\big(N_\Gamma(v;V_{j}),V_{k}\big)$ is $(\eps,d,p)$-regular in $G$, so that we have one-sided inheritance on $R'$. A similar argument shows that if also $jk\in R'$ and there is a triangle of $H$ with one vertex in each of $\tX_i$, $X-j$ and $X_k$, then also $\big(N_\Gamma(v;V_{j}),N_\Gamma(v;V_{k})\big)$ is $(\eps,d,p)$-regular in $G$, so that we have two-sided inheritance on $R'$ for $\tcX$.

Both of <ref> and <ref> follow directly from the construction of $\cV$ together with, respectively, the $\big(\tfrac12\delta\eps,d,p\big)$-super-regularity of $(G,\cVbl)$ on $\Rpbl$ and that $(\cIbl,\cJ)$ forms a $\big(\tfrac12\delta\rho p^\vartheta,2\zeta,\Delta,\Delta_J\big)$-restriction pair. The same holds for everything except <ref> in the definition of a restriction pair for <ref>, since <ref> was already established. Given an image restricted $x\in X_i\subset\Xbl_{i'}$ and an edge $xy\in E(H)$ with $Y\in X_j\subset\Xbl_{j'}$, the pair $\big(\comN_\Gamma(J_x;V_{i'}),\comN_\Gamma(J_y;V_{j'})\big)$ is $\big(\tfrac12\delta\eps,d,p\big)$-regular by assumption. Since $\big|\comN_\Gamma(J_x;V_i)\big|\ge\tfrac12\delta\big|\comN_\Gamma(J_x;V_{i'})\big|$, and similarly for $y$, it follows from the definition that $\big(\comN_\Gamma(J_x;V_{i}),\comN_\Gamma(J_y;V_{j})\big)$ is $(\eps,d,p)$-regular, completing the verification of <ref>.

With this we are ready to define the general setup which is common to
our proofs and encapsulates the definitions of good embeddings and the
constant choices above. This encapsulation is convenient because we will
use this general setup in many of the lemmas to come.

When we say that we assume the General Setup we assert that
constant choices satisfying the conditions of
Section <ref> have been made, that there exist
$\kappa$-balanced size-compatible partitions $\cX$ and $\cV$ of $V(H)$
and $V(G)$ respectively whose parts are of size at least
$\tfrac{n}{\kappa r_1}$, together with reduced graphs $R$ and $R'$ with
$\Delta(R')\le\DeltaRp$, an image restriction pair $(\cI,\cJ)$, an
$(\alpha,R')$-buffer $\tcX$, buffer vertices $\Xbuf$, and sets $\Vmain$,
$\Vq$, $\Vc$ and $\Vbuf$, that the partition of $V(H)$ is a good
$H$-partition, and that the partition of $G$ is a good $G$-partition.

§.§ Underlying restrictions, candidates and good partial embeddings

at (-1,0.75) $H$ ;
at (-1.5,3.75) $G\subset\Gamma$ ;
every node=[draw,circle,fill=black,minimum size=4pt,
inner sep=0pt]
(0,0) node (x) [label=left:$x$]
– ++(2.5,0.75) node (z) [label=right:$z$]
– ++(-2.5,0.75) node (y) [label=left:$y$] ;

at (0,3) (px) [label=left:$\psi(x)$]  ;
at (0,4.5) (py) [label=left:$\psi(y)$]  ;
every node=[draw=none,fill=none]
at (1,3.75) (Gaz)  ;
[draw] (px) edge [snake it] node  (Gaz.center)
(Gaz.center) edge [snake it] node  (py) ;
(4,3.75) ellipse (3cm and 2cm) ;
[line width=1pt] (4,3.75) ellipse (1.5cm and 1.25cm) ;
at (2.5,3.75) (Gz)  ;
[draw] (px) edge [line width=1pt,bend right] node  (Gz.center)
(Gz.center) edge [line width=1pt,bend right] node  (py) ;
[draw] (3.5,1.45) edge [bend right,dashed] node  (3.5,6.35) ;
at (3.7,6.1) (imp) [label=left:$\im(\psi)$]  ;
[fill=white] at (2.15,5.25) (Uz) $U(z)$ ;
[fill=white] at (2.95,2.9) (Cz) $C(z)$ ;
at (5.5,3.75) (Az) [label=left:$A(z)$]  ;

Underlying restriction sets, candidate sets, and available
candidate sets for an example in which $x$ and $y$ are embedded and their common neighbour $z$ is not.
The thick lines are edges of $G$, and the wavy lines of $\Gamma$.

In this section we provide definitions of a number of additional sets that
will play important roles in our embedding algorithms. We also state which
invariants are maintained throughout the embedding, and encapsulate this in
the definition of good partial embeddings.

Suppose $\psi$ is a partial embedding of $H$ into $G$, that is, an injective
graph homomorphism with domain $\dom(\psi)\subseteq V(H)$.
We call a vertex $x\in H$ embedded if $x\in\dom(\psi)$, and otherwise
unembedded. Of course this is with respect to $\psi$, but this will
always be clear from the context and we will not in future mention it. The set
of embedded neighbours of $x$ is

\[\Pi(x):=\big\{\psi(y):xy\in E(H),y\in\dom(\psi)\big\}\]

and we define
\[\pi(x):=\big|\Pi(x)\big|\quad \text{and}\quad
\pi^*(x)=\big|\Pi(x)\big|+\big|J_x\big|.\]

Thus, $\pi^*(x)$ counts the number of already embedded neighbours of $x$ by
the partial embedding $\psi$ plus the `neighbours' from $J_x$ (if any).

Given an unembedded vertex $x\in X_i$, we define the underlying
restriction set $U(x)$, the candidate set $C(x)$, and the
available candidate set $A(x)$ of $x$ by

\begin{align*}
U(x)&:=V(x)\cap \comN_\Gamma\big(\Pi(x)\cup
C(x)&:=I_x\cap \comN_G\big(\Pi(x)\big)\,,\text{ and}\\
A(x)&:=C(x)\setminus\im(\psi)\,,\text{ respectively.}
\end{align*}

For an illustration see Figure <ref>.

Recall that $G$ is a subgraph of $\Gamma$ (being either a random or a
bijumbled graph), which is typically far from being complete. The
underlying set signifies thus the vertices that could in principle be used
for embedding (if $G=\Gamma$), whereas the candidate sets denote the
vertices that are possible in $G$, and the available candidate sets
only consider those vertices from the candidate sets which have not been
previously taken as images by the vertices embedded earlier (in
$\im(\psi)$). We also refer to vertices from $C(x)$ as candidate vertices
for $x$.  Further, we define

\begin{align*}
\Umain(x)&:=U(x)\cap\Vmain(x)\,, &
\Uq(x)&:=U(x)\cap\Vq(x)\,, \\
\Uc(x)&:=U(x)\cap\Vc(x)\,, &
\Ubuf(x)&:=U(x)\cap\Vbuf(x)\,,
\end{align*}

and similarly for the respective subsets of the
candidate set $C(x)$ and the available candidate set $A(x)$ of $x$. For an illustration see
Figure <ref>.

(0,0.45) ellipse (5cm and 3cm) ;
[line width=1pt] (0.5,0) ellipse (4.2cm and 1.75cm) ;
[draw] (1,-3) edge node  (1,4) ;
[draw] (2.2,-3) edge node  (2.2,4) ;
[draw] (3.4,-3) edge node  (3.4,4) ;
at (0,3.7) $\Vmain$ ;
at (1.6,3.5) $\Vq$ ;
at (2.8,3.2) $\Vc$;
at (4.05,2.7) $\Vbuf$ ;
at (0,2.55) $\Umain(x)$ ;
at (1.6,2.35) $\Uq(x)$ ;
at (2.8,2) $\Uc(x)$ ;
at (4.05,1.4) $\Ubuf(x)$ ;
at (0,0) $\Cmain(x)$ ;
at (1.6,0) $\Cq(x)$ ;
at (2.8,0) $\Cc(x)$ ;
at (4.05,0) $\Cbuf(x)$ ;
[fill=white] at (-2,1.4) $C(x)$ ;
[fill=white] at (-4,2.2) $U(x)$ ;

Partitioning underlying restriction sets and candidate sets into
one big and three small parts

Further we define the underlying
restriction graph between $Y\subseteq X_i$ and
$Z\subseteq V_i$ to be the bipartite graph with parts $Y$ and $Z$ and edges $yz$
whenever $z\in U(y)$. We define similarly the candidate
graph between $Y\subseteq X_i$ and
$Z\subseteq V_i$ to be the bipartite graph with parts $Y$ and $Z$ and edges $yz$
whenever $z\in C(y)$. If $x\in V(H)$ and $v\in C(x)$ we say $v$ is a
candidate for $x$.

Now we can introduce the concept of good partial embeddings.
The intention of this definition is to fix properties which easily allow to
prove that a good partial embedding is `locally'
good: If $x$ is unembedded, then almost all of $C(x)$ consists of vertices $v$
such that if $v$ is not in $\im(\psi)$, then $\psi\cup\{x\to v\}$ is a good
partial embedding (this assertion is made formal in Lemma <ref>).

We call $\psi$ a good partial embedding if the following conditions hold.

*  For each $x\in\dom(\psi)$ we have $\psi(x)\in

*  For each unembedded $x\in X_i$ we have

\begin{align*}
\big|U(x)\big|=(p\pm\eps p)^{\pi^*(x)}\big|V(x)\big|\,,\quad
\big|\Umain(x)\big|&=(1-3\mu)(p\pm\eps p)^{\pi^*(x)}\big|V(x)\big|\,,\quad \text{and}\\
\quad \big|\Uq(x)\big|\,,\,\big|\Uc(x)\big|\,,\,\big|\Ubuf(x)\big|&=\mu(p\pm\eps p)^{\pi^*(x)}\big|V(x)\big|\,.
\end{align*}

*  For each unembedded $x$ we have

\begin{align*}
\big|C(x)\big|&\geq(1-\eps')(dp-\eps' p)^{\pi(x)}\big|I_x\big|\,,\\
\big|\Cmain(x)\big|&\geq(1-\eps')(1-3\mu)(dp-\eps' p)^{\pi(x)}\big|I_x\big|\,,\quad\text{and}\\
\big|\Cq(x)\big|\,,\,\big|\Cc(x)\big|\,,\,\big|\Cbuf(x)\big|&\geq(1-\eps')\mu(dp-\eps' p)^{\pi(x)}\big|I_x\big|\,.
\end{align*}

*  For each $xy\in E(H)$ with $x$ and $y$ unembedded,
the pair $\big(U(x),U(y)\big)$ is $(\eps_{\pi^*(x),\pi^*(y)},d,p)$-regular in

every node=[draw,circle,fill=black,minimum size=4pt,
inner sep=0pt]
at (-3,-0.5) (x) [label=left:$x$]  ;
at (-3,1.5) (xp) [label=left:$x'$]  ;
at (1,0.75) (y) [label=above left:$y$]  ;
at (1,-1.75) (yp) [label=below left:$y'$]  ;
at (5,0.75) (z) [label=right:$z$]  ;
(xp)–(x)–(yp)–(y) ;
(x)–(y)–(z) ;

at (-3,4) (psx) [label=left:$\psi(x)$]  ;
at (-3,6) (psxp) [label=left:$\psi(x')$]  ;
every node=[draw=none,fill=none]
[line width=1pt] (psx)–(psxp) ;

(1,2.75) ellipse (1.5cm and 0.75cm) ;
[line width=1pt] (1,2.75) ellipse (0.65cm and 0.3cm) ;
[draw] (psx) edge [snake it] node  (1-1.418*0.75,2.75+1.418*0.375) ;
[draw] (psx) edge [line width=1pt,bend right] node  (0.35,2.75) ;

(1,5.25) ellipse (1.5cm and 0.75cm) ;
[line width=1pt] (1,5.25) ellipse (0.65cm and 0.3cm) ;
[draw] (psx) edge [snake it] node  (1-1.418*0.75,5.25-1.418*0.375) ;
[draw] (psx) edge [line width=1pt,bend left] node  (0.35,5.25) ;

(5,5.25) ellipse (1.5cm and 0.75cm) ;
[line width=1pt] (5,5.25) ellipse (0.65cm and 0.3cm) ;

[pattern=north east lines] (2.5,5.25)–(2.6,5.45)–(3.4,5.45)–(3.5,5.25)–(3.4,5.05)–(2.6,5.05)–(2.5,5.25) ;
[pattern=north east lines] (1,3.5)–(1.2,3.6)–(1.2,4.4)–(1,4.5)–(0.8,4.4)–(0.8,3.6)–(1,3.5) ;

at (-4.5,0.5) $H$ ;
at (-4.5,5) $G\subset\Gamma$ ;
[fill=white] at (2,2.15) $U(y')$ ;
[fill=white] at (2,5.85) $U(y)$ ;
[fill=white] at (6,5.85) $U(z)$ ;
at (1,2.75) $C(y')$ ;
at (1,5.25) $C(y)$ ;
at (5,5.25) $C(z)$ ;

Good partial embeddings form embeddings when restricted to the
mapped vertices $x,x'$ and guarantee sizes and regularity for the
underlying restriction sets of unmapped vertices $y,y',z$. The thick lines are edges of $G$, the wavy lines of $\Gamma$, and the hatched areas represent regular pairs in $G$.

It is important to observe that the trivial partial embedding, in which no
vertices are embedded, is not automatically a good partial embedding: image
restricted vertices might destroy any
of <ref>–<ref>. However, it follows from
straightforward checking of the definitions that if we are provided with a
good $H$-partition and a corresponding good $G$-partition, then the trivial
partial embedding is a good partial embedding.

If we assume the General Setup for $H$ and $G$ then the trivial embedding
is a good partial embedding of $H$ into $G$.

Finally, in much of the rest of this paper we will want to consider not just one partial embedding, but a sequence $\psi_0,\dots$ of them. We will want to refer to sets $\Amain(x)$, $\Cmain(x)$ and so on, and quantities $\pi(x)$ and so on, with reference to each of these. We will do this by following the convention that a subscript $t$ attached to any of these means it is with reference to $\psi_t$. Thus we write $\Amain_t(x)$
for the set $\Amain(x)$ with respect to $\psi_t$, and similarly
$\Cmain_t(x)$, $\Pi_t(x)$, $\pi_t(x)$, $\pi^*_t(x)$, $U_t(x)$, $C_t(x)$,
$A_t(x)$ and so on.

§.§ Bad vertices

As mentioned in the proof overview, we will embed vertices of $H$ into $G$
one at a time, choosing each vertex in a way that allows for the future
continuation of the embedding. This `allowing for future continuation'
comes in two parts, `local' conditions which broadly say that we embed a
vertex of $H$ in a way which allows for the embedding of other vertices
nearby in $H$, and `global' conditions which say that the embedding of many
(distant) vertices of $H$ do not tend to cause problems for any given
vertex. We handle the latter probabilistically, and this constitutes the
main work of this paper.  The purpose of this subsection is to define
precisely what we require locally, by specifying which vertices of $G$ are
bad for $x\in V(H)$, that is, not suitable for embedding $x$ to, and to
show that this is always a small set of vertices (in comparison to the
set $A(x)$). In fact, the definition of badness also depends on a set
$Q\subset V(H)$. In the random greedy algorithm (outlined in the
proof overview, Section <ref>), $Q$ will be the current
queue, while at other times $Q$ will simply be  $V(H)$.

Let $\psi$  be a good partial embedding and $Q\subset V(H)$ be a set of
unembedded vertices. The vertex $v$ is called bad for $x$ with
respect to $\psi$ and $Q$ if the extension $\psi\cup\{x\to v\}$ is
not a good partial embedding or there is an unembedded neighbour $y$ of
$x$ with $y\not\in Q$ such that

\begin{equation}\label{eq:bad_vertices}
\deg_G\big(v;\Amain(y)\big)<(d-\eps')p|\Amain(y)|\,.
\end{equation}

We stress that in this equation we take $\Amain(y)$ with respect to the
embedding $\psi$ (and not the extended embedding).
When $\psi$ and $Q$ are clear from the context (as they always will be) we let $B(x)$ be the set of vertices in $C(x)$ which are bad for $x$ with respect to $\psi$ and $Q$.
When we have a sequence of embeddings $\psi_0,\dots$ and a sequence of sets
$Q_0,\dots$ then we write, again, $B_t(x)$ for the set of bad
vertices for $x$ with respect to $\psi_t$ and $Q_t$.
We will also refer to (<ref>) as the badness condition.

The following lemma provides control over the bad vertices with respect
to a good partial embedding. We remark that the definition of the
value $D$ in this lemma is somewhat complex, because we want to apply
this lemma in the proofs of all three of our blow-up lemmas, in
particular the blow-up lemma for degenerate graphs.

We assume the General Setup. Let $\psi$ be a good partial embedding and let $Q\subset V(H)$ be a set of vertices such that for each unembedded $x\in V(H)\setminus Q$ we

\[|\Amain(x)|\ge\tfrac12\mu(d-\eps')^{\pi^*(x)}p^{\pi^*(x)}|\Vmain(x)|\,.\]

Given an unembedded $x\in V(H)$, let $D$ be such that for all unembedded
$y,z\in V(H)$ we have

*  $D\ge\pi^*(x)+1$,

*  If $xy\in E(H)$ then $D\ge\pi^*(y)+1$,

*  If $xy,yz\in E(H)$ then $D\ge\pi^*(y)+2,\pi^*(z)+1$,

*  If $xy,yz,xz\in E(H)$ then $D\ge\pi^*(x)+2,\pi^*(y)+2,\pi^*(z)+2$.

Then the following holds.

*  If all neighbours of $x$ are embedded then no
vertex in $A(x)$ is bad for $x$ with respect to
$\psi$ and $Q$.

*  Suppose that $\Gamma$ satisfies $\NS(\eps,r_1,D)$
and $\RI(\eps,(\eps_{a,b}),\eps',d,r_1,D)$. Then at most
$20\Delta^2\eps'p^{\pi^*(x)}|V(x)|$ vertices of $C(x)$ are bad for $x$ with respect to $\psi$ and $Q$.

We require

\[\mu\le\tfrac16\,,\qquad \eps'\le\frac{\mu d^\Delta \zeta}{1000\kappa 4^{\Delta}}\qquad\text{and}\qquad \eps\le\frac{d\eps'}{\kappa}\,.\]

For <ref>, observe that all the conditions for a vertex $v$ to be in $B(x)$ are trivially false.

For part <ref>, we need to consider all of the possible reasons
$v$ could be bad for $x$ with respect to $\psi$ and $Q$.
It could be that
there is some unembedded neighbour $y\in V(H)\setminus Q$ of $x$ such
that the badness condition (<ref>) holds.
The pair $\big(U(x),U(y)\big)$ is $(\eps',d,p)$-regular in $G$
by <ref>.
By assumption and because <ref> holds for $y$ with respect to $\psi$
we have

\begin{equation*}\begin{split}
=\frac12\mu(1-3\mu)(d-\eps')^{\pi^*(y)}p^{\pi^*(y)}|V(y)| \\
\ge\eps'|U(y)|\,.
\end{split}\end{equation*}

So the badness condition (<ref>)
holds for at most $\eps'|U(x)|\le 2\eps'p^{\pi^*(x)}|V(x)|$
vertices $v$ of $C(x)$, where we use <ref> and $(1-\eps)^\Delta\le 2$.
Since $x$ has at most
$\Delta$ unembedded neighbours, in total there are at most
$2\Delta\eps'p^{\pi^*(x)}|V(x)|$ vertices $v$ of $C(x)$ such
that the badness condition (<ref>) holds for some unembedded neighbour of $x$.

It could be that $\psi\cup\{x\to v\}$
is not a good partial embedding. Since $v\in C(x)\subseteq
I_x$, <ref> cannot fail.
We next consider <ref>. Since $\psi$ is a good partial
embedding, <ref> cannot fail for any vertex $y$ which is not a
neighbour of $x$ (because the candidate sets of these vertices do not change).
So let $y$ be any neighbour of $x$ in $H$.
Recall that
$\big(U(x),U(y)\big)$ is $(\eps',d,p)$-regular in $G$ by <ref>.
We have

\begin{equation*}\begin{split}
|C(y)| &\geBy{\ref{GPE:sizeC}} (1-\eps')(dp-\eps'p)^{\pi(y)}|I_{y}|
\geBy{\ref{G:restr}}(1-\eps')(dp-\eps'p)^{\pi^*(y)}\zeta|V(y)| \\
\ge\eps'|U(y)|\,.
\end{split}\end{equation*}

Since $C(x)\subset U(x)$, there are at most $\eps'|U(x)|\le
2\eps'p^{\pi^*(x)}|V_i|$ vertices $v\in C(x)$ such that $|C(y)\cap
N_G(v)|<(d-\eps')p|C(y)|$. Since
$(d-\eps')p|C(y)|\ge(1-\eps')(dp-\eps'p)^{\pi(y)+1}|I(y)|$, there are
at most $2\eps'p^{\pi^*(x)}|V(x)|$ vertices $v\in C(x)$ such that the first
condition in <ref> fails for $y$ with respect to
$\psi\cup\{x\to v\}$. We can analogously argue for
each of the other four conditions. Since $x$ has at most $\Delta$
unembedded neighbours, we conclude that for all but at most $10\Delta\eps'p^{\pi^*(x)}|V_i|$
vertices $v\in C(x)$ we have that <ref> is satisfied with
respect to $\psi\cup\{x\to v\}$.

Now we turn to <ref>. Again, it suffices to consider
neighbours $y$ of $x$.  As <ref> holds with respect
to $\psi$, we see that $|U(y)|\ge(p-\eps p)^{\pi^*(y)}|V(y)|\ge\eps
p^{D-1}n/r_1$ since $|V(y)|\ge n/(\kappa r_1)$ and by
assumption <ref>.  It follows
that we can use $\NS(\eps,r_1,D)$ and assumption <ref> to
conclude that all but at most $\eps p^{D-1}n/r_1^2\le \eps'
p^{\pi^*(x)}|V(x)|$ vertices $v\in C(x)$ are such that $|U(y)\cap
N_\Gamma(v)|=(1\pm\eps)p|U(y)|=(p\pm\eps p)^{\pi^*(y)+1}|V(y)|$, again using <ref> for $y$ with respect to $\psi$.  Again, we
can argue analogously for the other four conditions, and so in total for
all but at most $5\Delta\eps' p^{\pi^*(x)}|V(x)|$ vertices $v\in C(x)$ we
have that <ref> is satisfied with respect to $\psi\cup\{x\to

It remains to consider <ref>. Again, we only need to consider
edges $yz\in E(H)$ between unembedded vertices such that $y\in N_H(x)$ or
$z\in N_H(x)$, or both. Consider first the case that only $y\in
N_H(x)$. The case that only $z\in N_H(x)$ follows
analogously. Since <ref> is satisfied with respect to $\psi$ we
have $|U(y)|\ge(p-\eps p)^{\pi^*(y)}|V(y)|$ and $|U(z)|\ge(p-\eps
p)^{\pi^*(z)}|V(z)|$, which together with assumption <ref>
implies $|U(y)|\ge(p-\eps p)^{D-2}n/(\kappa
r_1)\ge\eps'p^{D-2}n/r_1^2$ and
$|U(z)|\ge\eps'p^{D-1}n/r_1^2$.  Hence, since $\Gamma$ satisfies
$\RI(\eps,(\eps_{a,b}),\eps',d,r_1,D)$ and the pair $\big(U(y),U(z)\big)$
is $(\eps_{\pi^*(y),\pi^*(z)},d,p)$-regular in $G$ because <ref>
is satisfied with respect to $\psi$, we get that there are at most
$\eps p^{D-1}n/r_1^2\le\eps'p^{\pi^*(x)}|V(x)|$ vertices $v\in C(x)$ such that $\big(N_\Gamma(v)\cap
U(y), U(z)\big)$ is not
$(\eps_{\pi^*(y)+1,\pi^*(z)},d,p)$-regular in $G$. Analogously, in the second
case that $y,z\in N_H(x)$ we can use assumption <ref> to
conclude that there are at most $\eps p^{D-2}n/r_1^2\le\eps'p^{\pi^*(x)}|V_i|$ vertices $v\in C(x)$
such that $\big(N_\Gamma(v)\cap U(y), N_\Gamma(v)\cap U(z)\big)$ is not
$(\eps_{\pi^*(y)+1,\pi^*(z)+1},d,p)$-regular in $G$. So, in total there are at
most $\Delta^2 \eps'p^{\pi^*(x)}|V(x)|$ vertices $v\in C(x)$ such
that <ref> is not satisfied with respect to $\psi\cup\{x\to v\}$.

Summing up, there are at most

\begin{multline*}
p^{\pi^*(x)}|V(x)|+\Delta^2 \eps'p^{\pi^*(x)}|V(x)| \\
\le 20\Delta^2\eps'p^{\pi^*(x)}|V(x)|
\end{multline*}

vertices $v\in C(x)$ such
that $v$ is bad for $x$ with respect to $\psi$ and $Q$.

§ THE BEHAVIOUR OF RANDOM GREEDY ALGORITHMS

The proofs of our three blow-up lemmas each use, as crucial ingredient, a
slightly different random greedy algorithm (RGA). In this section we
collect four different lemmas which will be useful in conjunction with
these RGAs.

Roughly speaking, each of our RGAs has the property that we embed
vertices sequentially, at each time choosing an image of the next vertex
uniformly at random in a not-too-small subset of its candidate vertices,
and this, together with the General Setup, is all we need to know about
our RGAs for the purposes of this section. Nevertheless, the reader who
wishes to see a concrete example of an RGA before reading the following
lemmas should look at Algorithm <ref> in Section <ref>,
which is the simplest of our RGAs. The other two RGAs are
Algorithm <ref> in Section <ref> and
Algorithm <ref> in Section <ref>.

Our first lemma (Lemma <ref>) constructs the vertex ordering
which we shall use in the RGAs for the random graphs blow-up lemma
(Lemma <ref>) and the blow-up lemma for bijumbled graphs
(Lemma <ref>).  The point of the ordering we use is that we
need to analyse the way neighbours of (non-clique) buffer vertices are
embedded during the RGA. Putting them first in the order, with each
neighbourhood coming as an interval in the order, makes this
possible. Even then, for Lemma <ref> we need to insist that
in degree-$\Delta$ buffers the final two neighbours of a buffer vertex
are not adjacent, thus their embeddings do not affect each other

In the proof of our blow-up lemma for degenerate graphs
(Lemma <ref>) we cannot apply this lemma, because we have to
work with the order we are supplied with.  Ultimately, the fact that we
cannot expect these nice conditions from this supplied order is the
reason why we cannot obtain stronger bounds on $p$ in that lemma.

Let $H$ be a graph with $\Delta(H)\le\Delta$ and $V(H)=\Xbuf\dcup\Xmain\dcup\Xc$
such that $N(\Xbuf)\subset \Xmain$ and each pair of vertices in $\Xbuf$
has distance at least ten.
Then there exists an ordering $\tau$ of $\Xmain$ with the
following properties.

*  For all $x\in \Xmain\setminus N(\Xbuf)$ and $y\in N(\Xbuf)$ we
have $\tau(x)>\tau(y)$.

*  For all $x\in \Xbuf$ we can enumerate $N(x)$ as $y_1,\dots,y_b$
such that $\tau(y_{j+1})=\tau(y_j)+1$ for all
$j\in[b-1]$. Moreover, if $\deg_H(x)=\Delta$ and $x$ is not in a copy of $K_{\Delta+1}$ then
$y_{\Delta-1}y_\Delta\not\in E(H)$.

*  The neighbours of non-clique buffer vertices come before the neighbours of the
clique-buffer vertices.

Note that in this
lemma we do not need to assume the General Setup, but we
nevertheless use names for the parts of $H$ corresponding to those from
the General Setup.

We separate the vertices in $\Xbuf$ into two classes, those not in
copies of $K_{\Delta+1}$ and those in copies of $K_{\Delta+1}$. We take
an enumeration $\Xbuf=\{x_1,\ldots,x_{|\Xbuf|}\}$ with the vertices not
in copies of $K_{\Delta+1}$ coming first. We now create the ordering
$\tau$ as follows. We start with the empty ordering. For each $i$ in
succession such that $x_i\in\Xbuf$ is not in a copy of $K_{\Delta+1}$,
we append to $\tau$ the vertices $N_H(x_i)$ in some order such that if
$\deg_H(x_i)=\Delta$ then the last two vertices in $\tau$ of $N_H(x_i)$
are not adjacent. Note that if $\deg_H(x)=\Delta$ then there is a pair of non-adjacent vertices in
$N_H(x_i)$ because $x_i$ is not in a copy of $K_{\Delta+1}$. Next, for
each $i$ in succession such that $x_i\in\Xbuf$ is in a copy of
$K_{\Delta+1}$ we append to $\tau$ the vertices $N_H(x_i)$ in an
arbitrary order. Finally, we append to $\tau$ any remaining vertices of
$\Xmain$ in an arbitrary order.

The next lemma states that provided we embed vertices uniformly at random
into not-too-small sets, the candidate sets of unembedded vertices are
likely to be distributed uniformly. In this lemma, as will be the case for
much of the rest of the paper, we have a sequence $\psi_0,\dots$ of good
partial embeddings, and we want to talk about the various sets and
quantities defined in Section <ref>, such as candidate sets, with
respect to each of these good partial embeddings. As mentioned in
Section <ref>, we will follow the convention that (for example)
$C_t(x)$ is the candidate set of $x$ with respect to $\psi_t$.

We assume the General Setup. Suppose that for some integer $T$ we have a
sequence $\psi_0,\psi_1,\dots,\psi_T$ of good partial embeddings,
where $\psi_0$ is the trivial partial embedding
and each $\psi_t$ is obtained from $\psi_{t-1}$ by embedding some
vertex $x$ in $V(H)\setminus\dom(\psi_{t-1})$ to a uniform random
vertex from a subset $S$ of $C_{t-1}(x)$ with

Then the following holds with probability at least
$1-2^{-n/(\kappa r_1)}r_1$.  For every $i\in[r]$ and every set
$W\subseteq V_i$ of size at least $\rho |V_i|$, the number of
vertices $x\in X_i\setminus X^*_i$ (i.e. vertices which are not
image restricted) such that there exists $t=t(x)$ when $x$ is
unembedded and we have

\begin{equation}\label{eq:rga:welldistr}
|C_t(x)\cap W|<\big(dp-\eps'p\big)^{\pi^*_t(x)}|W|
\end{equation}

is at most $\rho |X_i|$.

This lemma corresponds to the Main Lemma of [49], and its proof is
similar in spirit. The proof of this lemma exploits the fact that when a
vertex $y$ is embedded, condition (<ref>) might become
true for at most one vertex from $X_i\setminus X^*_i$ (since
by <ref> the vertices in $X_i$ have distance at least
$10$). Moreover, by the condition of always embedding into not too small
subsets and by the regularity property <ref>, the vertex $y$ makes
an unlucky choice with a very small probability, so that many such choices
are extremely unlikely.

We require

\[\eps'<\min\big(4^{-\Delta}d^\Delta\rho,\tfrac{\mu\zeta d^{\Delta}}{20\Delta}2^{-4/\rho}\big)\quad\text{and}\quad 2^{-n/\kappa r_1}r_1<1\,.\]

Fix a set $W\subseteq V_i$ of size at least $\rho|V_i|$, and a set $X'\subseteq X_i\setminus X^*_i$ of size $\rho|X_i|$. We aim to show that the probability of the following event is at most $2^{-4|X_i|}$. For each $x\in X'$ there is a $t=t(x)$ such that $x$ satisfies (<ref>). The desired result then follows by taking the union bound over all $i$, subsets $W$ of $V_i$ and $X'$ of $X_i$.

If $x$ is any vertex of $X'$, then we have $C_0(x)=V_i$ since $x$ is not image restricted, thus
$|C_0(x)\cap W|=|W|$ and hence (<ref>) is false for $x$.
If there is a $t(x)$ such that $x$ satisfies (<ref>), then we can fix $t$ to be the smallest integer such that (<ref>) is true for $t+1$ and $x$.
Since the candidate set of $x$ changes
only when a neighbour of $x$ is embedded, it follows that
the vertex $y$ that is embedded to create $\psi_{t+1}$ from $\psi_t$ is a neighbour of $x$ in $H$ and thus $\pi^*_{t+1}(x)=\pi^*_{t}(x)+1$.
Moreover, since equation (<ref>) becomes true for $x$,
the vertex $y$ is embedded to a vertex $w$ such that

\begin{equation}\label{eq:welldist:bad}
\deg_G\big(w;C_{t}(x)\cap W\big)<(d-\eps')p\big|C_{t}(x)\cap W\big|\,,
\end{equation}

as otherwise we would still have

\[|C_{t+1}(x)\cap W|\ge ((d-\eps')p\big)|C_{t}(x)\cap W|\ge ((d-\eps')p)^{\pi^*_{t+1}(x)}|W|\,.\]

Since $\psi_{t}$ is a good partial embedding, by <ref> the pair
$\big(U_{t}(x),U_{t}(y)\big)$ is an $(\eps',d,p)$-regular pair in $G$, and by <ref> we have
$\big|U_{t}(x)\big|=(p\pm\eps'p)^{\pi^*_{t}(x)}|V_i|$, and $\big|U_{t}(y)\big|=(p\pm\eps'p)^{\pi^*_{t}(y)}|V(y)|$. Since (<ref>) is false for $x$ at time $t$,
we have $\big|C_{t}(x)\cap W\big|\ge \big((d-\eps')p\big)^{\pi^*_{t}(x)}|W|$, and so

\[
\big|C_{t}(x)\cap W\big|\ge \left(\tfrac{d-\eps'}{1+\eps'}\right)^{\pi^*_{t}(x)}\rho |U_{t}(x)|\ge\eps' |U_{t}(x)|\,,
\]

by the requirements on the constants at the beginning of the proof.
We conclude by $(\eps',d,p)$-regularity of $\big(U_{t}(x),U_{t}(y)\big)$ that at most $\eps'\big|U_{t}(y)\big|\le 2\eps'p^{\pi^*_{t}(y)}|V(y)|$ vertices $w$ of $U_{t}(y)$ satisfy (<ref>).

Since $\psi_{t+1}$ is created by embedding $y$ uniformly at random into a subset of $C_t(y)\subset U_t(y)$ of size at least $\tfrac{1}{10}\mu\zeta(dp)^{\pi^*_t(y)}|V(y)|$, the probability of embedding $y$ to a vertex $w$ satisfying (<ref>), conditioning on any history, is at most

\begin{equation}\label{eq:bad_probability}
\frac{2\eps'p^{\pi^*_{t}(y)}|V(y)|}{\tfrac{1}{10}\mu\zeta(dp)^{\pi^*_t(y)}|V(y)|}
\le 20\eps'\mu^{-1}\zeta^{-1}d^{-\Delta}\,.
\end{equation}

Next we argue that the probability that for each $x\in X'$ there is a first time $t=t(x)$ such that $x$ satisfies (<ref>) is at most

\[\big(20\Delta\eps'\mu^{-1}\zeta^{-1}d^{-\Delta}\big)^{\rho|X_i|}\le 2^{-4|X_i|}\,.\]

Let us denote this event by $\cE_{X'}$. Observe that $\cE_{X'}$ is split into $\Delta^{|X'|}$ events (since $\Delta(H)\le\Delta$) by specifying for each $x\in X'$ a neighbour $y_x$ of $x$ whose embedding occurs at time $t(x)$. Let $(y_x)_{x\in X'}$ be any such assignment, and $\cE_{X',(y_x)}$ be the corresponding event. We aim to bound $\Pr(\cE_{X',(y_x)})$.

By <ref> the vertices of $X_i$ are at distance at least ten in $H$, so the vertices $(y_x)_{x\in X'}$ are distinct. The corresponding conditional probabilities thus multiply, and we have

\[\Pr(\cE_{X',(y_x)})\le\big(20\eps'\mu^{-1}\zeta^{-1}d^{-\Delta}\big)^{|X'|}\]

by (<ref>). Applying the union bound over the events $\cE_{X',(y_x)}$ we conclude

\[\Pr(\cE_{X'})\le \big(20\Delta\eps'\mu^{-1}\zeta^{-1}d^{-\Delta}\big)^{\rho|X_i|}\le 2^{-4|X_i|}\,.\]

where the final inequality is by choice of $\eps'$.

Taking the union bound over the at most $2^{|V_i|}=2^{|X_i|}$ choices of $W$ in $V_i$ and $2^{|X_i|}$ choices of $X'$ in $X_i$, we see that the probability that, for any fixed $i$, there exist subsets $W$ of $V_i$ and $X'$ of $X_i$, of sizes at least $\rho|V_i|$ and $\rho|X_i|$ respectively, such that each vertex $x$ of $X'$ satisfies (<ref>) at some time $t$, is at most $2^{2|X_i|}2^{-4|X_i|}=2^{-2|X_i|}$. Now we have $|X_i|\ge n/(\kappa r_1)$, and $n\ge n_0$ where $n_0$ is chosen large enough such that $2^{-n_0/(\kappa r_1)}r_1<1$. Thus taking the union bound over the at most $r_1$ choices of $i$, we conclude that the probability that there exists $i$, and a subset $W$ of $V_i$ such that there are $\rho|X_i|$ vertices $x$ of $X_i\setminus X^*_i$ each of which satisfies (<ref>) at some time $t$, is at most $2^{-n/(\kappa r_1)}r_1$ as desired.

The next lemma, Lemma <ref>, shows that, again provided we embed vertices uniformly
into not-too-small sets, we do not tend to cover vertex neighbourhoods
in $G$ disproportionately fast. Specifically, if $ij\in E(R')$ then,
by <ref>, each $v\in V_i$ has a large $G$-neighbourhood in
$V_j$. At some time $T$ when only a small but linear fraction of each
part of $H$ has been embedded, it is very likely that less than half of
this $G$-neighbourhood is in the image $\im(\psi_T)$ of the current
partial embedding. One should think of this as: early on in the
embedding process, the minimum degree conditions <ref> provided by
super-regularity are preserved.

We will apply this lemma in the proofs of the random graphs blow-up
lemma (Lemma <ref>) as well as the jumbled graphs blow-up
lemma (Lemma <ref>). For the proof of the degenerate graphs
blow-up lemma, on the other hand, we cannot use it; but we will replace
it by a suitable modification of the ideas in its proof.

The idea behind Lemma <ref> is as follows. As discussed in
the proof overview (Section <ref>), we will need our
RGAs to guarantee that each $v\in V_i$ is a candidate for many vertices
$x\in\Xbuf_i$ in order to complete the embedding. This means we need it
to be not too unlikely that $N_H(x)$ is embedded to $N_G(v)$ for any
given $x\in\Xbuf_i$, and as a first step to showing this, it is
necessary to show that we have not covered $N_G(v)$ with embedded
vertices before we get around to embedding $N_H(x)$. In the proofs of
the random graphs blow-up lemma and the bijumbled blow-up lemma, we show
this by embedding $N(\Xbuf)$ first and applying
Lemma <ref>.

We assume the General Setup. Suppose that $\Gamma$ has
$\NS(\eps,r_1,B)$. Suppose that for some $T$ we have a sequence
$\psi_0,\psi_1,\dots,\psi_T$ of good partial embeddings, where
$\psi_0$ is the trivial partial embedding and each $\psi_t$ is
obtained from $\psi_{t-1}$ by embedding one vertex $x_t\in V(H)$ to a
uniform random vertex from a subset $S$ of $C_{t-1}(x_t)$ with
$|S|\ge\tfrac{1}{10}(dp)^{\pi_{t-1}^*(x_t)}|V(x_t)|$. Suppose furthermore
that for each $t$ the vertex $x_t$ has at most $B-2$ neighbours in
$\dom(\psi_{t-1})$, and that for each $i\in[r]$ we have
$\big|\dom(\psi_T)\cap X_i\big|\le 8\mu\kappa\DeltaRp|X_i|$.

Then with probability at least $1-\exp(-\eps p n/r_1)$, for each
$i\in[r]$, each vertex $v\in V_i$, and each $j$ such that
$ij\in E(R')$
we have $\big|N_{G}(v;\Vmain_j)\setminus \im(\psi_T)\big|\ge \tfrac12\deg_{G}(v;V_j)$.

In the proof of the bijumbled blow-up lemma we set $B=\Delta+1$ and will show
that this is enough for Lemma <ref> to handle all of
$N(\Xbuf)$. In the proof of the random graphs blow-up lemma, by contrast, we set
$B=\Delta$, which turns out to be good enough to handle buffers of degree
up to and including $\Delta$ which are not clique buffers. This is one of
the reasons why we have to handle clique buffers differently.

The proof of Lemma <ref> involves estimating the probability
of embedding $x_t$ to $N_G(v)$, conditioned on $\psi_{t-1}$. We show that
either this probability is small, or that a previously embedded neighbour
of $x_t$ was embedded oddly, which is guaranteed to be a low-probability
event. In either case, for $x_t$ to be embedded to $N_G(v)$ an unlikely
event must occur. For $N_G(v)$ to be substantially filled up, many of these
events, which are sequentially dependent, have to occur. The sequential
dependence lemma, Lemma <ref>, then shows this is unlikely
enough to take a union bound over all choices of $v$.

We require

\[\mu<\tfrac{d^{\Delta}}{1320\kappa\DeltaRp}\,,\quad\eps<\tfrac{\mu d}{10\kappa}\quad\text{and}\quad r_1 n\exp(-\eps p n/r_1)<1\,.\]

Fix $ij\in E(R')$ and a vertex $v\in V_i$. We first estimate the conditional probability that $x_t\in X_j\cap\dom(\psi_T)$ is embedded to $N_G(v)\cap\Vmain (x_t)$, given the history. Because $x_t$ is embedded uniformly at random to a subset of $C_{t-1}(x_t)$ of size at least $\tfrac{1}{10}(dp)^{\pi^*_{t-1}(x_t)}|V_j|$, this probability is at most

\begin{equation}\label{eq:large_nbs:prob}
\frac{\big|\Umain_{t-1}(x_t)\cap N_G(v)\big|}{\tfrac{1}{10}(dp)^{\pi^*_{t-1}(x_t)}|V_j|}\,,
\end{equation}

which we will show to be at most $20d^{-\Delta}\tfrac{\deg_G(v;V_j)}{|V_j|}$.

This clearly holds when $\big|\Umain_{t-1}(x_t)\cap N_G(v)\big|\le (p+\eps p)^{\pi^*_{t-1}(x_t)}\deg_G(v;V_j)$
and we therefore assume the opposite.
In this case the estimate on the conditional
probability (<ref>) that $x_t$ occupies a vertex from
$N_G(v)$ could be as great as $1$, but we will show that this is an unlikely event. Specifically, for this  to occur
there must be a first neighbour $y_t$ of $x_t$ in $H$ which is
embedded oddly at time $t'<t$, that is, is such that $\big|\Umain_{t'-1}(x_t)\cap N_G(v)\big|\le (p+\eps p)^{\pi^*_{t'-1}(x_t)}\deg_G(v;V_j)$ but (with $\pi^*_{t'}(x_t)=\pi^*_{t'-1}(x_t)+1$)

\begin{equation}\label{eq:large_candidate_NG}
\deg_\Gamma\big(\psi_{t'}(y_t);\Umain_{t'-1}(x_t)\cap N_G(v)\big)>(p+\eps p)^{\pi^*_{t'-1}(x_t)+1}\deg_G(v;V_j)\,.
\end{equation}

Let $W$ be a superset of $\Umain_{t'-1}(x_t)\cap N_G(v)$ of size $(p+\eps p)^{\pi^*_{t'-1}(x_t)}\deg_G(v;V_j)>\mu(d-\eps)p^{B-1}|V_j|$, where the inequality uses the fact that $\pi^*_{t'-1}(x_t)\le B-2$ and <ref>.
By property $\NS(\eps,r_1,B)$, which $\Gamma$ satisfies, we see that there are at most $\eps p^{B-1} n/r_1$ vertices $Z$ of $\Gamma$ which have this many neighbours in $W$ and thus satisfy (<ref>).
Now $\pi^*_{t'-1}(y)\le B-2$ by the conditions of the lemma. We conclude that the probability of embedding $y$ to a vertex of $Z$, conditioning on the history, is at most

\begin{equation}\label{eq:occupy_prob_two}
\tfrac{\eps p^{B-1}n/r_1}{\tfrac{1}{10}(dp)^{B-2}|V(y)|}\le 10\eps d^{-\Delta}\kappa p<10d^{-\Delta+1}p\leq 20d^{-\Delta}\tfrac{\deg_G(v;V_j)}{|V_j|}\,,
\end{equation}

where we use $|V(y)|\ge n/(\kappa r_1)$ in the first and the choice of $\eps$ in the second and <ref> in the third inequality.

We define a sequence of Bernoulli random variables $Y_1,\ldots,Y_T$ as follows. Given the embedding $\psi_{t-1}$, if $x_t$ is a neighbour of a vertex in $X_j\cap\dom(\psi_T)$ none of whose previous neighbours were oddly embedded, and $x_t$ is oddly embedded, we set $Y_t=1$. If $x_t$ is in $X_j$, none of its previous neighbours were oddly embedded, and $x_t$ is embedded to $N_G(v;V_j)$, we set $Y_t=1$. Otherwise we set $Y_t=0$. By assumption, the total number of $Y_t$ which are not deterministically zero (that is, are in $X_j\cap\dom(\psi_T)$ or are neighbours of such a vertex) is at most $8\mu\kappa\DeltaRp(\Delta+1)|X_i|$. Observe furthermore that for all of the $Y_t$ which are not deterministically zero, we have just shown in (<ref>) that $Y_t$ is one with probability at most $20d^{-\Delta}\tfrac{\deg_G(v;\Vmain_j)}{|V_j|}$ conditioning on the history up to, but not including, embedding $x_t$. This history determines $Y_{t-1}$, so that the $Y_1,\dots,Y_T$ are sequentially dependent. It follows that we can apply Lemma <ref>, with

\[x=8\mu\kappa\DeltaRp(\Delta+1)|X_j|\cdot20d^{-\Delta}\tfrac{\deg_G(v;V_j)}{|V_j|}=160\mu\kappa d^{-\Delta}\DeltaRp(\Delta+1)\deg_G(v;V_j)\]

and $\delta=1$, to show that

\[
\Pr\big(Y_1+\dots+Y_T\ge 2x\big)\le 2\exp\big(-\tfrac{x}{3}\big)
<\exp\big(-\tfrac{2\eps p n}{r_1}\big)\,,
\]

where the final inequality is by choice of $\eps$ and since $\deg_G(v;V_j)\ge (1-3\mu)(d-\eps)p|V_j|$ by <ref>. By choice of $\mu$, we conclude that with probability at most $\exp(-2\eps p n/r_1)$ we have $Y_1+\dots+Y_T\ge\tfrac14\deg_G(v;V_j)$. Now observe that for any vertex to be embedded to $N_G(v;\Vmain_j)$ one of these variables $Y_1,\ldots,Y_T$ must be one, and since vertices of $X_j$ are at distance at least ten in $H$ (by <ref>), no $Y_t$ can be responsible for two different vertices of $X_j$ being embedded to $N_G(v;\Vmain_j)$. Thus $Y_1+\dots+Y_T$ is an upper bound for $\im(\psi_T)\cap N_G(v;\Vmain_j)$. Taking a union bound over the choices of $j$ and of $v$, and using <ref>, we see that with probability at least $1-r_1 n\exp(-2\eps p n/r_1)>1-\exp(-\eps p n/r_1)$ the statement of the lemma holds.

Our final lemma in this section complements the above lemma, showing that
provided $v\in V_i$ does not have $N_G(v)$ more than half covered by
$\im(\psi)$ early in the embedding, it is reasonably likely that $N_H(x)$
is embedded to $N_G(v)$ for any given $x\in\Xbuf_i$. As with the previous
lemma, it contains a parameter $B$ which will be either set to $\Delta$
(in the proof of the random graphs blow-up lemma) or to $\Delta+1$ (in the proof
of the bijumbled graphs blow-up lemma), and again in the former case the consequence
is that we cannot use it to deal with clique buffers (that is, when
$N_H(x)$ is a copy of $K_\Delta$). For the degenerate graphs blow-up lemma
we again need to replace this lemma by suitable similar ideas.

We assume the General Setup. Let
$B\in\{\Delta,\Delta+1\}$ and assume that $\Gamma$ has $\NS(\eps,r_1,B)$
and $\RI(\eps,(\eps_{a,b}),\eps',d,r_1,B)$.  Given $v\in V_i$ and
let $y_1,\ldots,y_b$ be the neighbours
of $x$, and suppose that if $b=B$ then $y_{b-1}y_b$ is not an edge of
Let $\psi_0$ be a good partial embedding in which
no vertex at distance two or less from $x$ is embedded, and let
$Q_0\subset\Xmain$. Suppose further that
for each $j$ such that $ij\in R'$.

Let $\psi_1,\ldots,\psi_b$ be good partial embeddings and
$Q_1,\ldots,Q_b$ subsets of $\Xmain$, such

that for each $t=1,\dots,b$ the embedding $\psi_t$ is obtained
from $\psi_{t-1}$ by embedding $y_t$ uniformly at random into its
available candidates minus the vertices which are bad for $y_t$, that is, into
$\Amain_{t-1}(y_t)\setminus B_{t-1}(y_t)$, and such that
we have

\[Q_t=Q_{t-1}\cup\big\{z\in \Xmain\setminus\dom(\psi_t)\colon \big|\Amain_t(z)\big|<\tfrac12
\mu(d-\eps')^{\pi^*_{t}(z)}p^{\pi^*_{t}(z)}|\Vmain(z)|\big\}\,.\]

Then with probability at least $\big(d^{\Delta}p/10\big)^b$, we have $\psi_b\big(N_H(x)\big)\subset N_G(v)$.

The proof of this lemma is quite long, but much of it is `bookkeeping'.
Briefly, the idea is as
follows. In $\psi_0$, no neighbour of any $y_j$ is embedded and hence
each $y_j$ has candidate set $C_0(y_j)=V(y_j)$. We know that
$N_G\big(v;V(y_1)\big)$ is not covered by $\im(\psi_0)$, so if we
choose a uniform random vertex of $A_0(y_1)$ the probability of
choosing a member of $N_G(v)$ is at least $dp/4$. However, the random
greedy algorithm does not choose a random vertex of $A_0(y_1)$, but
rather of $A_0(y_1)\setminus B_0(y_1)$. Thus we have to show that
$B_0(y_1)$ does not cover too much of $N_G(v)$, which we can do using
properties <ref> and <ref> of the partition of $G$,
and $\NS(\eps,r_1,B)$ and $\RI(\eps,(\eps_{a,b}),\eps',d,r_1,B)$ which
we assume of $\Gamma$, in much the same way as the proof of
Lemma <ref>. In addition we have to show that some extra
properties are preserved which allow us to analyse the embedding of
$y_2,\dots,y_b$, which we can show is likely in a similar way. We will
refer to a good partial embedding with these extra properties as a
buffer-friendly partial embedding. We conclude that the probability of
embedding $y_j$ to $N_G(v)$ and maintaining a buffer-friendly partial embedding
is at least $d^{\Delta}p/10$, conditioning on the history, for each
$j$. The conditional probabilities multiply, giving the desired

We require

\[\mu\le\tfrac16\,,\qquad \eps<(\eps')^2,\qquad\eps'\le \frac{\mu d^\Delta \zeta}{1000\kappa\Delta^2}\qquad\text{and}\qquad (d-\eps')^{10\Delta}>\tfrac12 d^{10\Delta}\,.\]

For each $0\le t\le b$ and each $y_j$, $j\in[b]$, we define
$\hatA_t(y_j):=\Amain_t(y_j)\cap N_G(v)$ and
for any vertex $x'\in X$ we set $\hatU_t(x'):=U_t(x')\cap N_\Gamma(v)$.

Observe that since $y_t$ is embedded to a vertex of $C_{t-1}(y_t)\setminus
B_{t-1}(y_t)$ for each $t=1,\dots,b$ we automatically maintain the property
that $\psi_t$ is a good partial embedding for each $t$ (see
Definition <ref> of bad vertices). We now formulate five
additional conditions on $\psi_t$ for $t=0,\dots,b$, which allow us to show
a lower bound on the desired probability inductively. If $\psi_t$ satisfies
these conditions we say that it is a buffer-friendly partial embedding (w.r.t. $v$).

*  We have that $\{\psi_t(y_1),\dots, \psi_t(y_t)\}
\subset N_G(v)$,

*  $|\hatU_{t}(y_k)|= (p\pm\eps' p)^{\pi_{t}^*(y_k)} \deg_{\Gamma}(v;V(y_k))$ for $k=t+1,\ldots,b$,

*  $|\hatA_{t}(y_k)|\ge \tfrac12(dp-\eps'p)^{\pi_{t}^*(y_k)} \deg_G(v;V(y_k))$ for $k=t+1,\ldots,b$,

*  for unembedded $y_k$ and $y_\ell$ with
$y_k y_\ell\in E(H)$ we have $(\hatU_{t}(y_k),\hatU_{t}(y_\ell))$ is
$(\eps_{\pi_{t}^*(y_k),\pi_{t}^*(y_\ell)},d,p)$-regular in $G$,

*  for unembedded $y_k$ and $z$ with
$y_k z\in E(H)$ the pair  $(\hatU_{t}(y_k),U_{t}(z))$ is
$(\eps_{\pi_{t}^*(y_k),\pi_{t}^*(z)},d,p)$-regular in $G$.

Observe that these conditions are all satisfied for $\psi_0$, i.e. $\psi_0$ is a buffer-friendly partial embedding. Indeed, <ref> is vacuously satisfied. <ref> holds by
definition of $\hatU$ and since no neighbours of any $y_k$ are embedded. <ref> holds by the definition of $\hatA$, the assumption on
$\deg_G\big(v;V(x_k)\setminus\im(\psi_0)\big)$ of the lemma, and since no neighbours of any $y_k$ are embedded. If $y_k$ and $y_\ell$ are adjacent in $H$ then $xy_ky_\ell$ is a triangle in $H$ with $x\in\Xbuf_i\subset\tX_i$, so by <ref> we have <ref>. Finally, again since $x\in\Xbuf_i\subset\tX_i$, by <ref> we have <ref>.

For each $t=0,\dots,b-1$ we let $P_t$ be the set of unfriendly vertices
$u$ in $\hatA_t(y_{t+1})$, that is, the vertices that are such that if $\psi_t(y_{t+1})=u$ then $\psi_t$ is not a buffer-friendly partial embedding.

We now show that, for any $t=1,\dots,b$, given a buffer-friendly partial embedding $\psi_{t-1}$, the probability that $\psi_t$ is a buffer-friendly partial embedding is at least
$d^\Delta p/10$. This clearly yields, by multiplying the conditional probabilities,
the lower bound of $(d^\Delta p/10)^b$ claimed
in the statement of the lemma.
For the analysis it will suffice to show that only a tiny proportion of vertices
from $\hatA_{t-1}(y_t)$ are in $B_{t-1}(y_t)$ or $P_{t-1}$.

So assume that $\psi_{t-1}$ is a buffer-friendly partial embedding.
We first give some lower bounds on set sizes. Since $\psi_{t-1}$ is a good partial embedding
we have for an unembedded vertex $z$ that

\begin{equation}\label{eq:buffer:largeUC}
|\Uq_{t-1}(z)|\ge\mu(p-\eps p)^{\pi_{t-1}^*(z)}\big|V(z)\big|\ge \eps'p^{\pi^*_{t-1}(z)}n/r_1
\end{equation}

where the first inequality is by <ref>
and the second because $|V(z)|\ge n/(\kappa r_1)$ and by choice of $\eps'$. The same lower bound also holds for $U_{t-1}(z), C_{t-1}(z)$ et cetera since these sets are all by <ref> and <ref> at least as large.
Since in addition $\psi_{t-1}$ is a buffer-friendly partial embedding, we
have for any $y_k$ with $k\ge t$ that

\begin{equation}\label{eq:buffer:largehat}
\end{equation}

where the second inequality is by <ref> and the third is by <ref> and choice of $\eps'$.
We also have for $k\ge t$, using <ref>, <ref>, <ref>, <ref> and the choice of $\eps$ and $\eps'$ that

\begin{equation}\label{eq:buffer:relhat}
|\hatA_{t-1}(y_k)|\ge \max\big(\tfrac14d^{\Delta}p|U_{t-1}(y_k)|\,,\,\tfrac14d^{\Delta}|\hatU_{t-1}(y_k)|\big)\ge\eps'|\hatU_{t-1}(y_k)|\,.
\end{equation}

We are next going to estimate the number of bad vertices in $\hatA_{t-1}(y_t)$.

$|\hatA_{t-1}(y_t)\cap B_{t-1}(y_t)| \le 30\Delta^2 d^{-\Delta}\eps' |\hatA_{t-1}(y_t)|$.

We need to estimate the number of vertices $w$ from $\hatA_{t-1}(y_t)$
which are bad with respect to $\psi_{t-1}$ and $Q_{t-1}$. For that we will consider
all of the possible reasons.

First assume that  there is some unembedded
neighbour $z\in V(H)\setminus Q_{t-1}$ of $y_t$ such
that the badness condition

\begin{equation}\label{eq:bad_vts_ncbl}
\deg_G\big(w;\Amain(z)\big)<(d-\eps')p|\Amain(z)|
\end{equation}

holds for $w$ and $z$. The pair
$\big(\hatU_{t-1}(y_t),U_{t-1}(z)\big)$ is $\big(\eps_{\pi_{t-1}^*(y_t),\pi_{t-1}^*(z)},d,p\big)$-regular
in $G$ by <ref>.
Because $z\not\in Q_{t-1}$ we have that

\begin{align*}
|\Amain_{t-1}(z)|&\ge \tfrac{1}{2}\mu(d-\eps')^{\pi^*_{t-1}(z)}p^{\pi^*_{t-1}(z)}|\Vmain(z)|\\
&\ge \tfrac{1}{2}\mu(1-3\mu)(d-\eps')^{\pi^*_{t-1}(z)}p^{\pi^*_{t-1}(z)}|V(z)|\ge \eps'|U_{t-1}(z)|\,,
\end{align*}

where the first inequality is by  definition of $Q_{t-1}$ in the statement of the lemma,
the second inequality is by <ref> and the last by choice of $\eps'$ and by <ref>.
Therefore the badness condition (<ref>) holds
for at most

\[
\eps_{\pi_{t-1}^*(y_t),\pi_{t-1}^*(z)} |\hatU_{t-1}(y_t)|\leByRef{eq:buffer:relhat} 4d^{-\Delta}\eps' |\hatA_{t-1}(y_t)|
\]

$w$ of $\hatA_{t-1}(y_t)$.
Since $y_t$ may have at most $\Delta$ unembedded neighbours,
in total there are at most $4\Delta d^{-\Delta}\eps' |\hatA_{t-1}(y_t)|$ vertices $w$ of $\hatA_{t-1}(y_t)$ such
that the badness condition (<ref>) holds for some unembedded neighbour of $y_t$.

Next we need to estimate the number of vertices $w$ from $\hatA_{t-1}(y_t)$ such that
$\psi_{t-1}\cup\{y_t\to w\}$ is not a good partial embedding (i.e. does not satisfy properties <ref>–<ref>). First observe that since $w\in \hatA_{t-1}(y_t)\subseteq C_{t-1}(y_t)\subseteq I_{y_t}$,
<ref> cannot fail.

Next we turn to <ref>. It is  sufficient
to consider unembedded neighbours $z$ of $y_t$, so $\pi^*_{t-1}(z)\le\Delta-1$. As the bound in (<ref>) also holds for $U_{t-1}(z)$ we have $|U_{t-1}(z)|\ge\eps' p^{\Delta-1}n/r_1$.
Therefore, by the neighbourhood size property $\NS(\eps,r_1,B)$, all but at most $\eps p^{B-1}n/r_1^2$ vertices $w$ from $\hatA_{t-1}(y_t)$
are such that $|U_{t-1}(z)\cap N_{\Gamma}(w)|=(1\pm\eps)p|U_{t-1}(z)|=(p\pm\eps p)^{\tau^*_{t-1}(z)+1}|V(z)|$, referring to <ref> for $z$ with respect to $\psi_{t-1}$.
Further we have $\pi^*_{t-1}(y_t)\le B-2$ since $y_t$ has at most $y_1,\dots,y_{B-2}$ as embedded neighbours (if $b=B$ then by assumption $y_by_{b-1}$ is not an edge of $H$), so since $\eps<(\eps')^2$ we have

\[\eps p^{B-1}n/r_1^2\leByRef{eq:buffer:largehat} \eps'|\hatA_{t-1}(y_t)|\,.\]

We  can argue analogously for the other four conditions of <ref> obtaining
in total  that for
all but at most $5\Delta\eps' |\hatA_{t-1}(y_t)|$ vertices $w$ from $\hatA_{t-1}(y_t)$,
<ref> is satisfied with respect to $\psi_{t-1}\cup\{y_t\to w\}$.

Now we consider <ref>. Let $z$ be any unembedded neighbour of $y_t$. Because $z$ is at distance at most $2$ from $x\in\Xbuf$, by <ref> $z$ is not image restricted, so $I_z=V(z)$. Since
<ref> and <ref> hold for $\psi_{t-1}$ we have:

\begin{equation*}
|C_{t-1}(z)|\ge (1-\eps')(dp-\eps'p)^{\pi^*_{t-1}(z)}|V(z)|\ge\eps'|U_{t-1}(z)|.
\end{equation*}

By <ref>,  $(\hatU_{t-1}(y_t),U_{t-1}(z))$ is
$(\eps_{\pi_{t-1}^*(y_t),\pi_{t-1}^*(z)},d,p)$-regular in $G$.
So, there are at most

\[\eps_{\pi_{t-1}^*(y_t),\pi_{t-1}^*(z)}|\hatU_{t-1}(y_t)|\leByRef{eq:buffer:relhat}4d^{-\Delta}\eps'|\hatA_{t-1}(y_t)|\]

vertices $w$ in
$\hatU_{t-1}(y_t)$ such that $|C_{t-1}(z)\cap N_G(w)|< (d-\eps')p|C_{t-1}(z)|$.
Similarly we argue for each of the other four conditions.
Thus, since $y_t$ has at most $\Delta$ unembedded neighbours, in total for all but at most
$20\Delta d^{-\Delta}\eps' |\hatA_{t-1}(y_t)|$ vertices $w\in \hatA_{t-1}(y_t)$ we have that <ref>
is satisfied with respect to $\psi_{t-1}\cup\{y_t\to w\}$.

It remains to consider <ref>. Again, we only need to consider
edges $zz'\in E(H)$ between unembedded vertices such that $z\in N_H(y_t)$. Consider first the case that $z'\not\in
N_H(y_t)$. In this case we have $\pi^*(z)\le \Delta-2$, $\pi^*(z')\le \Delta-1$ and $\pi^*_{t-1}(y_t)\le\Delta-2$ (since both $x$ and $z$ are unembedded neighbours of $y_t$). Since $\Gamma$ satisfies
property $\RI(\eps,(\eps_{a,b}),\eps',d,r_1,B)$, using (<ref>) and the fact that by <ref> the pair $\big(\hat U_{t-1}(z),\hat U_{t-1}(z')\big)$
is $(\eps_{\pi_{t-1}^*(z),\pi_{t-1}^*(z')},d,p)$-regular in $G$, we see that there are at most

\[
\eps p^{\Delta-1}n/r_1^2\leByRef{eq:buffer:largehat}  \eps'|\hatA_{t-1}(y_t)|
\]

vertices $w\in \hatA_{t-1}(y_t)$ such that the pair
$\big(N_\Gamma(w;U_{t-1}(z)), U_{t-1}(z')\big)$ is not

$(\eps_{\pi_{t-1}^*(z)+1,\pi_{t-1}^*(z')},d,p)$-regular in $G$.

In the case that
$z,z'\in N_H(y_t)$ we have $\pi_{t-1}^*(z')\le\Delta-2$. We also have $\pi^*_{t-1}(y_t)\le B-3$. This requires a little explanation. Observe that $y_t$ has unembedded neighbours $z$ and $z'$, so $\pi^*_{t-1}(y_t)\le\Delta-2$, and if $B=\Delta+1$ then we are done. If $B=\Delta$, then observe that the embedded neighbours of $y_t$ are contained in $\{y_1,\ldots,y_{t-1}\}$. It follows that if $t\le\Delta-2$, we have $\pi^*_{t-1}(y_t)\le\Delta-3$ as desired. If $t=\Delta$, then $x$, $z$ and $z'$ are distinct (since the only unembedded neighbour of $x$ is $y_t$) and we again have $\pi^*_{t-1}(y_t)\le\Delta-3$. It remains to consider the case $t=\Delta-1$. Again we are done if $x$, $z$ and $z'$ are distinct. If however (without loss of generality) we have $x=z$, then $z'$ is an unembedded neighbour of $x$ which is not $y_t$; in other words, we have $z'=y_\Delta$. But we assumed that $y_{\Delta-1}y_\Delta$ is not an edge of $H$, contradicting the assumption $y_tz'\in H$. We have thus justified $\pi^*_{t-1}(y_t)\le B-3$, so by $\RI(\eps,(\eps_{a,b}),\eps',d,r_1,B)$ we conclude that there are at most

\[
\eps p^{B-2}n/r_1^2\leByRef{eq:buffer:largehat}  \eps'|\hatA_{t-1}(y_t)|
\]

vertices $w\in \hatA_{t-1}(y_t)$
such that the pair $\big(N_\Gamma(w; U_{t-1}(z)), N_\Gamma(w; U_{t-1}(z'))\big)$ is not
$(\eps_{\pi_{t-1}^*(z)+1,\pi_{t-1}^*(z')+1},d,p)$-regular. So, in total there are at
most $\Delta^2 \eps' |\hatA_{t-1}(y_t)|$ vertices $w\in \hatA_{t-1}(y_t)$ such
that <ref> is not satisfied with respect to
$\psi_{t-1}\cup\{y_t\to w\}$.

Summing up, we conclude that $|\hatA_{t-1}(y_t)\cap B_{t-1}(y_t)|\le
4\Delta d^{-\Delta}\eps' |\hatA_{t-1}(y_t)|+5\Delta\eps' |\hatA_{t-1}(y_t)|+20\Delta d^{-\Delta}\eps' |\hatA_{t-1}(y_t)|
+\Delta^2 \eps' |\hatA_{t-1}(y_t)|$ as required.

Next we will estimate the number of unfriendly vertices in $\hatA_{t-1}(y_t)$.

$|P_{t-1}|\le 10\Delta^2d^{-\Delta}\eps' |\hatA_{t-1}(y_t)|$.

Observe that by definition, since $\psi_{t-1}$ is a buffer-friendly partial embedding, for each $w\in\hatA_{t-1}(y_t)$ the embedding $\psi_{t-1}\cup\{y_t\to w\}$ has <ref>. For $t=b$ the remaining properties <ref>–<ref> are trivial, so we from now on assume $t\le b-1$.

For <ref>, let $k\in\{t+1,\ldots,b\}$ be such that $y_ty_k\in E(H)$. Observe that $\pi^*_{t-1}(y_t)\le t-1\le b-2\le B-2$.
Therefore,  by $\NS(\eps,r_1,B)$ and (<ref>), for all but at most $\eps p^{B-1}n/r_1^2\le  \eps'|\hatA_{t-1}(y_t)|$ vertices $w$ we have
$|N_\Gamma(w; \hatU_{t-1}(y_k))|= (1\pm\eps')p|\hatU_{t-1}(y_k)|$.

To estimate the number of vertices $w$ that do not preserve <ref>, we only need to consider those
$y_k$ with $k\ge t+1$ such that $y_ty_k\in E(H)$. We
use that $\big(\hatU_{t-1}(y_t),\hatU_{t-1}(y_k)\big)$ is $(\eps',d,p)$-regular in $G$ by <ref>.
Further, by (<ref>) we have $|\hatA_{t-1}(y_t)|\ge \eps'|\hatU_{t-1}(y_t)|$, so there are at most

\[\eps'|\hatU_{t-1}(y_t)|\leByRef{eq:buffer:relhat} 4d^{-\Delta}\eps'|\hatA_{t-1}(y_t)|\]

vertices $w$ in
$\hatA_{t-1}(y_t)$ such that $\deg_G(w;\hatA_{t-1}(y_k))<(d-\eps')p|\hatA_{t-1}(y_k)|$.

Next we consider <ref>. Let $k\in\{t+1,\dots,b\}$,
and $z\in V(H)$ be such that $y_kz\in E(H)$. By <ref>
the pair $\big(\hatU_{t-1}(y_k),U_{t-1}(z)\big)$ is $(\eps_{\pi^*_{t-1}(y_k),\pi^*_{t-1}(z)},d,p)$-regular in $G$.
There are  three cases to consider: $y_ty_k\in E(H)$, $y_tz\in E(H)$, and both.

In the first case (i.e. $y_ty_k\in E(H)$, $y_tz\not\in E(H)$), we have $t<B-1$ because $y_{B-1}y_B$ is not an edge of $H$,
so we conclude $\pi^*_{t-1}(y_t),\pi^*_{t-1}(y_k)\le t-1\le B-3$, and $\pi^*_{t-1}(z)\le\Delta-1$.
By (<ref>) and (<ref>),
and $\RI(\eps,(\eps_{a,b}),\eps',d,r_1,B)$, we see that for all vertices $w$ of $\hatA_{t-1}(y_t)$ but at most

\[\eps p^{B-1}n/r_1^2\leByRef{eq:buffer:largehat} \eps' |\hatA_{t-1}(y_t)|\,,\]

the pair $\big(N_\Gamma(w;\hatU_{t-1}(y_k)),U_{t-1}(z)\big)$ is $(\eps_{\pi^*_{t-1}(y_k)+1,\pi^*_{t-1}(z)},d,p)$-regular in $G$.

In the second case (i.e. $y_ty_k\not\in E(H)$, $y_tz\in E(H)$), we have
$\pi^*_{t-1}(y_t),\pi^*_{t-1}(y_k)\le t-1\le B-2$, and $\pi^*_{t-1}(z)\le t-1\le\Delta-2$ and similarly, by $\RI(\eps,(\eps_{a,b}),\eps',d,r_1,B)$,  there are not more than $ \eps' |\hatA_{t-1}(y_t)|$ vertices $w$ of $\hatA_{t-1}(y_t)$ for which the pair
$\big(\hatU_{t-1}(y_k),N_\Gamma(w; U_{t-1}(z))\big)$ is not $(\eps_{\pi^*_{t-1}(y_k),\pi^*_{t-1}(z)+1},d,p)$-regular in $G$.

In the final case (i.e. $y_ty_k\in E(H)$, $y_tz\in E(H)$), again we have $t<B-1$, hence $\pi^*_{t-1}(y_t),\pi^*_{t-1}(y_k)\le B-3$, and $\pi^*_{t-1}(z)\le\Delta-2$, and again all but at most $\eps' |\hatA_{t-1}(y_t)|$ vertices $w$ of $\hatA_{t-1}(y_t)$ are such that $\big(N_\Gamma(w; \hatU_{t-1}(y_k)),N_\Gamma(w; U_{t-1}(z))\big)$ is $(\eps_{\pi^*_{t-1}(y_k)+1,\pi^*_{t-1}(z)+1},d,p)$-regular in $G$.

In total, we see that for all but at most $\Delta^2\eps'|\hatA_{t-1}(y_t)|$ vertices $w$ of $\hatA_{t-1}(y_t)$, the partial embedding $\psi_{t-1}\cup\{y_t\to w\}$ has <ref>.

Finally, we handle <ref>. Let $k,\ell\in\{t+1,\dots,b\}$ be such that
$y_ky_\ell\in E(H)$. We have $\pi^*_{t-1}(y_t),\pi_{t-1}^*(y_k),\pi_{t-1}^*(y_\ell)\le t-1\le B-3$. By <ref>, the pair $\big(\hatU_{t-1}(y_k),\hatU_{t-1}(y_\ell)\big)$ is
$(\eps_{\pi_{t-1}^*(y_k),\pi_{t-1}^*(y_\ell)},d,p)$-regular in $G$. Without loss of generality we may assume $y_ty_k\in E(H)$, and again there are two cases to consider depending on whether $y_ty_\ell\in E(H)$ or not. As before, using (<ref>), by $\RI(\eps,(\eps_{a,b}),\eps',d,r_1,B)$, at most

\[\eps p^{B-2} n/r_1^2\leByRef{eq:buffer:largehat} \eps'|\hatA_{t-1}(y_t)|\]

vertices $w\in\hatA_{t-1}(y_t)$ are such that
$\big(N_\Gamma(w;\hatU_{t-1}(y_k)),N_\Gamma(w;\hatU_{t-1}(y_\ell))\big)$ is not
$(\eps_{\pi_{t-1}^*(y_k)+1,\pi_{t-1}^*(y_\ell)+1},d,p)$-regular in $G$. The other case follows similarly, and we conclude that for all but at most $\Delta^2 \eps'|\hatA_{t-1}(y_t)|$ vertices $w$ of $\hatA_{t-1}(y_t)$, the partial embedding $\psi_{t-1}\cup\{y_t\to w\}$ has <ref>.

In total we get $|P_{t-1}|\le\Delta\eps'|\hatA_{t-1}(y_t)|+4\Delta
as claimed.

We conclude from Claim <ref> and Claim <ref> that
the number of vertices $w\in \hatA_{t-1}(y_t)$ such
that $w$ is bad for $y_t$ with respect to $\psi_{t-1}$ and $Q_{t-1}$ or
$w\in P_{t-1}$ is at most $50\Delta^2 d^{-\Delta} \eps' |\hatA_{t-1}(y_t)|$.

Now we can estimate the probability that $\psi_t$ is a buffer-friendly partial embedding, conditioning on the history and on $\psi_{t-1}$ being a buffer-friendly partial embedding. This event occurs if $y_t$ is embedded to a member of $\hatA_{t-1}(y_t)\setminus\big(B_{t-1}(y_t)\cup P_{t-1}\big)$. The number of such vertices is at least

\[\big|\hatA_{t-1}(y_t)\big|-50\Delta^2 d^{-\Delta} \eps' |\hatA_{t-1}(y_t)|\ge\tfrac12\big|\hatA_{t-1}(y_t)\big|\geByRef{eq:buffer:largehat}\tfrac14(dp-\eps'p)^{\pi^*_{t-1}(y_t)+1}|V(y_t)|\,,\]

while $y_t$ is embedded into a set of size at most $U_{t-1}(y_t)$, which by <ref> has size at most $(p+\eps p)^{\pi^*_{t-1}(y_t)}|V(y_t)|$. We see that the desired conditional probability is at least

\[\frac{\tfrac14(dp-\eps'p)^{\pi^*_{t-1}(y_t)+1}|V(y_t)|}{(p+\eps p)^{\pi^*_{t-1}(y_t)}|V(y_t)|}\ge \frac{d^\Delta p}{10}\,.\]

The statement of the lemma follows since the conditional probabilities multiply.

CHAPTER: PROOF OF THE BLOW-UP LEMMA FOR RANDOM GRAPHS

In this chapter we provide the proof of Lemma <ref>. This
proof relies on four main lemmas: The RGA Lemma (Lemma <ref>), the
queue embedding lemma (Lemma <ref>), the buffer defect lemma
(Lemma <ref>, and the buffer embedding lemma
(Lemma <ref>). These lemmas and the actual proof of
Lemma <ref> are provided in Section <ref>. The RGA
Lemma is then proved in Section <ref>, the queue embedding lemma in
Section <ref>, and the buffer defect lemma in
Section <ref>. The proof of Lemma <ref> is
short and thus given already in Section <ref>.

§ MAIN LEMMAS AND THE PROOF OF THE BLOW-UP LEMMA

We divide the proof of Lemma <ref> into four lemmas, which
correspond to our four different embedding stages described in the proof
overview in Section <ref>. At the end of this section we
show how these four lemmas together with Lemma <ref> imply
Lemma <ref>.

The first of our lemmas encapsulates the outcome after applying the
random greedy algorithm (RGA) which tries to embed $\Xmain$
into $\Vmain$. How this RGA operates is explained in the proof of
this lemma in Section <ref>.  The lemma claims the existence of a
good partial embedding with certain deterministic properties which we
require and which the RGA with high probability produces. Recall that the
RGA constructs the queues $\Xq_i$.

We assume the General Setup. Suppose that $\Gamma$ has
$\NS(\eps,r_1,\Delta)$ and
$\RI(\eps,(\eps_{a,b}),\eps',d,r_1,\Delta)$. Then there is a good
partial embedding $\psiRGA$ of $H$ into $G$ with the following
properties. For each $i$, let $\Xq_i:=\Xmain_i\setminus\dom(\psiRGA)$.
Then the
following hold for each $i$. Let $b$ be such that $\Xbuf_i$ is a degree-$b$

*  All neighbours of all buffer vertices
are embedded by $\psiRGA$.

*  Every vertex in $X_i\cap\dom(\psiRGA)$ is
embedded to $\Vmain_i$ by $\psiRGA$.

*  We have $|\Xq_i|\le2\rho|X_i|$.

*  For every set $W\subset V_i$ of size at least
$\rho|V_i|$, there are at most $\rho|X_i|$
vertices in $\Xbuf_i$ with fewer than $(dp)^b|W|/2$ candidates in $W$.

*  If $\Xbuf_i$ is not a clique buffer, then every vertex in $V_i$ is a
candidate for at least $\mu\big(d^\Delta p/100\big)^b|X_i|$ vertices of $\Xbuf_i$.

We shall next extend the good partial embedding provided by the RGA lemma
and embed the queue vertices into the sets $\Vq_i$. That this is possible
is stated by the following lemma. As mentioned in the proof overview, the
proof of this lemma relies on $\Gamma$ not having a dense spot, which the
congestion condition $\CON(\rho,r_1,\Delta)$ guarantees.

We assume the General Setup. Suppose that $\Gamma$ has $\NS(\eps,r_1,\Delta)$, $\RI(\eps,(\eps_{a,b}),\eps',d,r_1,\Delta)$ and $\CON(\rho,r_1,\Delta)$.
Let $\psi$ be a good partial embedding whose image is disjoint from the sets
$\Vq_i$, and suppose that for each $i$ we have a set $\Xq_i\subset X_i$ of
size at most $2\rho|X_i|$. Then there is a good partial embedding $\psiq$
extending $\psi$ such that

\[\dom(\psiq)\setminus\dom(\psi)=\Xq\text{ and }
\im(\psiq)\setminus\im(\psi)\subset\Vq\,.\]

Note that in the RGA lemma, Lemma <ref>, we do not have that all vertices $v$ in $V_i$ are candidates for many
vertices of $\Xbuf_i$ if $\Xbuf_i$ is a clique buffer (and in fact our RGA
may fail to produce this property). In this case we say that $v$ has
a buffer defect for $\Xbuf_i$.
It follows from <ref>, however, that only at most $\rho|V_i|$
vertices of $V_i$ can have a buffer defect for $\Xbuf_i$.
Our next lemma, the buffer defect lemma, deals with fixing these buffer defects.

In order to apply this lemma we need to alter the embedding strategy
described so far slightly.
Indeed, before we begin the embedding, we will reserve some copies of
$K_{\Delta+1}$ in $H$, each of which has a vertex in $\tX_i$. We call these the
reserved cliques and denote the family of reserved cliques for $\tX_i$
by $\cK_i$. We put the vertices
of all reserved cliques into the set $\Xc$, which is disjoint from $\Xmain$ and
$\Xbuf$. Then we apply the RGA lemma and the queue embedding lemma to
obtain a good partial embedding of all of $H$ but the reserved
cliques $\Xc$ and the buffer vertices $\Xbuf$.
Next, we use the buffer defect lemma to embed the reserved
cliques (and, for technical reasons, also
some vertices of $\Xbuf_i$) on vertices with buffer defects, to obtain a good partial embedding $\psigood$ in which only
the vertices of $\Xbuf$ remain unembedded and without any buffer defects
Note that in the following lemma $\Abuf(x)=A(x)\cap\Vbuf(x)=C(x)\cap\Vbuf(x)\setminus\im(\psi)$.

We assume the General Setup. Suppose that $\Gamma$ has
$\NS(\eps,r_1,\Delta)$, $\RI(\eps,(\eps_{a,b}),\eps',d,r_1,\Delta)$ and
$\CON(\rho,r_1,\Delta)$. Let $\psi$ be a good partial embedding whose
image is disjoint from the
sets $\Vc_i$ and whose domain contains $N(\Xbuf)$. Suppose that for each $i$ we are given a family $\cK_i$ of
reserved cliques $K_{\Delta+1}$, not embedded by $\psi$, such that for each $K\in\cK_i$ and $x,y\in K$ we have $x\in X_j$ and
$y\in X_k$ with $jk\in R'$, and that either

* $\Xbuf_i$ is a degree-$b$ non-clique buffer with $\cK_i=\emptyset$,
and all vertices in $V_i$ are candidate for at least $\mu\big(d^\Delta p/100\big)^b|X_i|$
vertices in $\Xbuf_i$, or

* $\Xbuf_i$ is a clique buffer with $|\cK_i|=2\rho|X_i|$, and
all but at most $\rho|V_i|$ vertices of
$V_i$ are candidate for at least $\mu(dp)^\Delta|X_i|/2$ vertices in

Let $\Xc_i$ be the set of vertices
of $X_i$ contained in some reserved clique from $\cK_i$ and assume that
$|\Xc_i|\le 2\kappa(\DeltaRp+1)\rho|X_i|$.

Then there is a good partial
embedding $\psigood$ extending $\psi$ such that for each $i$ the
following hold. Let $b$ be such that $\Xbuf_i$ is a degree-$b$

*  $\Xc_i\subseteq\dom(\psigood)$.

*  For each $x\in\Xbuf_i\setminus\dom(\psigood)$ we have
$|\Abuf(x)|\ge \mu(dp)^b|V_i|/4$.

*  Each $v\in V_i\setminus\im(\psigood)$ is candidate
for at least $\mu\big(d^\Delta p/100\big)^b|X_i|$ of the vertices $\Xbuf_i\setminus\dom(\psigood)$.

It remains to embed the buffer vertices, which is performed with the help
of the following lemma.

We assume the General Setup. Suppose that $\Gamma$ has
$\CON(\rho,r_1,\Delta)$. Suppose that $\psi$ is a good partial embedding,
in which all the vertices $N(\Xbuf)$ are embedded, and that for each $i$
we have a subset $X'_i$ of $\Xbuf_i$, and a subset $V'_i$ of
$V_i\setminus\im(\psi)$ with $|X'_i|=|V'_i|$. Suppose $\Xbuf_i$ is a
degree-$b$ buffer, and for some $\delta>0$ and $\rho\le \frac{\delta\mu d^b}{100\kappa}$ we have

*  for each $x\in X'_i$ we have
$|C(x)\cap V'_i|\ge \mu(dp)^b|V_i|/4$,

*  for each $W\subset V'_i$ with $|W|\ge\rho|V_i|$, there are at most $\rho|X_i|$ vertices in $X'_i$ which do not have a candidate in $W$, and

*  each $v\in V'_i$ is a candidate
for at least $\delta p^b|X_i|$ vertices in $X'_i$.

Then there is a good partial embedding $\psi'$ extending $\psi$ such that
$\dom(\psi')=\dom(\psi)\cup \bigcup_i X'_i$ and $\im(\psi')=\im(\psi)\cup\bigcup_{i} V'_i$.

The proof of this lemma mainly consists of a straightforward check of
Hall's condition and we provide it right away.
We remark that we will use this lemma again in the proof of the degenerate
graphs blow-up lemma, which
is why we do not give an explicit constant in place of $\delta$ in <ref>.

Since $\Xbuf$ is independent in H (and the sets $V'_i$ are disjoint in $G$), we can embed the vertices of $X'_i$
for each $i$ in succession, without affecting the vertices in any
other $X'_{i'}$. So we fix $i$ and will show that $X'_i$ can be embedded into $V'_i$.

Let $Y\subseteq X'_i$ be non-empty, and let $W$ be the set of vertices in
$V'_i$ which are a candidate for some member of $Y$. We wish to verify
Hall's condition, i.e. show that $|W|\ge|Y|$. We separate three cases.

First, suppose $0<|Y|\le \rho|X_i|$. If $|W|<|Y|$, then we can take a
subset $Y'$ of $Y$ of size $|W|$. Recall that the candidate graph
between $Y'$ and $W$ is the bipartite graph with edges $yw$ for $y\in Y'$
and $w\in W$ with $w\in C(y)$, and that this is a subgraph of the
underlying restriction graph between $Y'$ and $W$ with edges $yw$ with
$w\in U(y)$. Observe, moreover, that this underlying restriction graph is
isomorphic to the congestion graph $\AG(\Gamma,W,\cF)$ with
$\cF=\big\{\psi\big(N_H(y)\big)\colon y\in Y'\big\}$, which has edges
$wF$ with $w\in\comN_\Gamma(F)$. Now, since by <ref> each vertex
in $Y'$ has at least $\mu(dp)^b|V_i|/4$ candidates in $V'_i$, which must
lie in $W$, the number of edges in the candidate graph between $Y'$ and
$W$ is at least

\begin{align*}\tfrac{1}{4}\mu(dp)^b|V_i||Y'|&=
\tfrac{1}{8}\mu(dp)^b|V_i||Y'|+\tfrac{1}{8}\mu(dp)^b|V_i||Y'|\\
&> \frac{\mu d^b}{8\rho}p^b|Y'||W| +\frac{\mu
d^b}{8 \kappa r_1} p^b n|Y'|\\
&> 7p^b|Y'||W|+\rho p^b n|Y'|/r_1\,,
\end{align*}

where the second line comes from substituting $|V_i|=|X_i|>|Y'|/\rho=|W|/\rho$
and using $|V_i|\ge n/(\kappa r_1)$, and
the third follows from the bound on $\rho$.
Hence $e(\AG(\Gamma,W,\cF))>7p^b|Y'||W|+\rho p^b n|Y'|/r_1$, in
contradiction to $\CON(\rho,r_1,\Delta)$. We conclude that $|W|\ge |Y|$ in this

Second, if $\rho|X_i|<|Y|\le|X'_i|-\rho|X_i|=|V_i'|-\rho|V_i|$ and $|W|<|Y|$, then
$|V_i'\setminus W|>\rho|V_i|$, so by <ref> there are at most
$\rho|X_i|$ vertices of $X'_i$ which do not have candidates in $V'_i\setminus W$. In particular there is a vertex of $Y$ with
candidates in $V'_i\setminus W$, in contradiction to the definition of $W$. We
conclude that $|W|\ge|Y|$ in this case as well.

Finally, suppose $|Y|>|X'_i|-\rho|X_i|=|V_i'|-\rho|V_i|$. The vertices $V_i'\setminus W$
are candidates only for vertices in $X'_i\setminus Y$, and each vertex in
$V_i'\setminus W$ is a candidate for at least $\delta p^b|X_i|$ vertices in
$X_i'\setminus Y$ by <ref>. If $|W|<|Y|$, then $|V_i'\setminus
W|>|X'_i\setminus Y|$, and we can take a set $\tilde W\subset V_i'\setminus W$ of size $|X'_i\setminus Y|$.
Now the number of edges in the candidate graph
between $\tilde W$ and $X'_i\setminus Y$ is at least

\begin{align*}\delta p^b|X_i||\tilde W|
&>\tfrac12\delta p^b\big(\tfrac{1}{\rho}|X'_i\setminus Y||\tilde W|+\tfrac{n}{\kappa r_1}|X'_i\setminus Y|\big)\\
&>7p^b|X'_i\setminus Y||\tilde W|+\rho p^b n|X'_i\setminus Y|/r_1
\end{align*}

by essentially the same calculation as in the first case, using
$|X_i|=|V_i|\geq n/(\kappa r_1)$.
Taking $\cF'=\big\{\psi\big(N_H(x)\big)\colon x\in X'_i\setminus Y\big\}$,
the number of edges in the corresponding congestion graph
$\AG(\Gamma,\tilde W,\cF')$ is also at least this quantity, in contradiction to

This completes the verification of Hall's condition, so there is a partial
embedding $\psi'$ extending $\psi$ with $\dom(\psi')=\dom(\psi)\cup X'_i$
in which the vertices $X'_i$ are embedded to $V'_i$. Since $\Xbuf$ is independent and all the vertices $N(\Xbuf)$ are
embedded in $\psi$, it is trivially the case that $\psi'$ is a good partial embedding.

We are now ready to prove Lemma <ref>. Summarising, the proof will
go as follows. We will apply Lemma <ref> to find partitions
of $G$ and $H$, and graphs $R$ and $R'$, satisfying the General Setup. We
choose, for each $i$ such that $\Xbuf_i$ is a clique buffer a set of
reserved cliques with vertices $\Xc$. We can then apply the RGA lemma, the
queue embedding lemma, the buffer defect lemma, and the buffer embedding
lemma, in this order.

First we choose constants as follows. Given $\Delta$, $\DeltaRpbl$,
$\Delta_J$ integers, $\alphabl$, $\zetabl$ and $d>0$, and $\kappabl>1$, we
set $\vartheta=0$, $\DeltaRp=8(\Delta+\Delta_J)^{10}\DeltaRpbl$,
$\alpha=\tfrac12\alphabl$, $\zeta=\tfrac12\zetabl$ and $\kappa=2\kappabl$.
We now choose $\mu$, $\rho$ and $\eps'>0$ satisfying the conditions in
Lemmas <ref>, <ref>, <ref>,
<ref>, <ref> and <ref>. For convenience we provide here sufficient choices:

\[
\mu<\frac{d^\Delta}{1320\kappa\DeltaRp},\text{  and  } \rho\le \frac{\mu^2d^{\Delta^2+1}}{250^{\Delta+1}\kappa\DeltaRp},
\text{  and  } \eps'\le \frac{\mu\zeta\rho d^\Delta}{32^{\Delta+2}2^{4/\rho}\kappa\Delta^2\DeltaRp}\,.
\]

Now for input $\Delta$, $d$ and $\eps'$, Lemma <ref> returns constants $\eps_{a,b}$ and $\eps>0$. Here we additionally require that $\eps<(\eps')^2$.
We let $\epsbl=\tfrac{1}{16}(\Delta+\Delta_J)^{-10}\eps$ and $\rhobl=\tfrac{1}{16}(\Delta+\Delta_J)^{-10}\rho$.
Now Lemma <ref> returns $\epsbl$ and $\rhobl$. Given $\ronebl$ we let $r_1=8(\Delta+\Delta_J)^{10}\ronebl$. We choose $C$ sufficiently large for Lemma <ref> with input $\Delta$, $d$, $\eps'$, $T=r_1$ and $\rho$.

Given $p\ge C\big(\tfrac{\log n}{n}\big)^{1/\Delta}$, Lemma <ref> states that a.a.s. $\Gamma=G(n,p)$ has properties $\NS(\eps,r_1,\Delta)$, $\RI(\eps,(\eps_{a,b}),\eps',d,r_1,\Delta)$ and $\CON(\rho,r_1,\Delta)$ respectively. From now on we will assume $\Gamma$ is an $n$-vertex graph which satisfies these three properties.

Given a graph $\Rbl$ on $\rbl\le\ronebl$ vertices, and a spanning subgraph
$\Rpbl$ with $\Delta(\Rpbl)\le\DeltaRpbl$, and graphs $H$ and
$G\subset\Gamma$ with vertex partitions $\cXbl$ and $\cVbl$, families of
image restrictions $\cIbl$ and of image restricting vertices $\cJ$, and a
family of potential buffer vertices $\tcXbl$, suppose that the conditions
of Lemma <ref> are satisfied. Then
Lemma <ref> gives (with $\Delta$ in place of $b$) a graph
$R$ on $r\le r_1$ vertices, a spanning subgraph $R'$ with
$\Delta(R')\le\DeltaRp$, and $\kappa$-balanced size-compatible partitions
$\cX$ and $\cV$ of $H$ and $G$ respectively, each part having size at
least $n/(\kappa r_1)$, together with a family $\tcX$ of potential buffer
vertices and $\cI$ of image restrictions, subsets $\Xbuf_i$ of $\tX_i$ for
each $i\in[r]$, and partitions
$V_i=\Vmain_i\dcup\Vq_i\dcup\Vc_i\dcup\Vbuf_i$ for each $i\in[r]$ which
satisfy the General Setup.

Now for each $i\in[r]$ such that $\Xbuf_i$ is a clique buffer, in
succession, we create a collection of reserved cliques $\cK_i$ and a set
$\Xc$ as follows. We choose $2\rho|X_i|$ vertices from $\tX_i$ which are
in copies of $K_{\Delta+1}$ that do not contain image restricted vertices,
vertices of $\Xbuf$, or vertices previously added to $\Xc$. We add these
copies of $K_{\Delta+1}$ to $\cK_i$, and their vertices to $\Xc$. Observe
that this is possible since <ref> guarantees that each
$\tX_i$ contains at least $\tfrac{1}{2\Delta+4}\alpha|X_i|$ vertices in
copies of $K_{\Delta+1}$ whose vertices are neither image restricted nor
in $\Xbuf$ and, moreover, by <ref> the edges of these cliques lie
along $R'$, so the number of these cliques which are chosen for some
$\cK_j$ with $j<i$ is at most
$\DeltaRp2\rho\kappa|X_i|<\tfrac{1}{4\Delta+8}\alpha|X_i|$ by choice of
$\rho$. We conclude the following properties for these reserved cliques.

*  The sets $\{\cK_i\}_{i\in[r]}$ are pairwise disjoint, and if $\Xbuf_i$
is a clique buffer, then $\cK_i$ contains $2\rho|X_i|$ cliques, each with
one vertex in $X_i$, otherwise it
is empty.

*  For each $i\in[r]$, $K\in\cK_i$ and $x,y\in K$ we have $x\in X_j$ and
$y\in X_k$ where $jk\in R'$.

*  For each $i$,  the set $\Xc_i$ of vertices
$x\in X_i$ contained in some reserved clique satisfies $|\Xc_i|\le 2\kappa(\DeltaRp+1)\rho|X_i|$.

Notice that <ref> holds by <ref>, since the
first and second neighbours of vertices from $\tX_i$ go along the edges of
$R'$ by the definition of an $(\alpha,R')$-buffer.

We let $\Xmain=V(H)\setminus(\Xbuf\cup\Xc)$. We now begin the embedding of $H$ into $G$.
By Lemma <ref>, there is a good partial embedding $\psiRGA$ with
properties <ref>–<ref>. Letting
$\Xq=\Xmain\setminus\dom(\psiRGA)$, by <ref> we have
$|\Xq_i|\le 2\rho|X_i|$ for each $i$, and by <ref> we see
that $\im(\psiRGA)$ is disjoint from each set $\Vq_i$, so the conditions of
Lemma <ref> are met. Feeding $\psiRGA$ into
Lemma <ref> we obtain a good partial embedding $\psiq$ extending
$\psiRGA$ whose domain is $\Xmain$ and whose image is contained in
$\Vmain\cup\Vq$. By <ref> all neighbours of all buffer
vertices are in $\dom(\psiRGA)$, and therefore the candidate sets of all
buffer vertices are the same with respect to $\psiRGA$ as with respect to
$\psiq$. In particular $\psiq$ satisfies <ref>
and <ref>.

We now verify the conditions for Lemma <ref>. Since $\psiq$
extends $\psiRGA$ and the vertices $\im(\psiq)\setminus\im(\psiRGA)$ are
embedded in the sets $\Vq_i$ it follows by <ref> that
$\im(\psiq)$ is disjoint from the sets $\bigcup_i\Vc_i$ and $\bigcup_i
\Vbuf_i$. By <ref>, if $\Xbuf_i$
is not a clique buffer then all vertices in $V_i$ are candidate for at least
$\mu(d^\Delta p/100)^b|X_i|$ vertices in $\Xbuf_i$ and $\cK_i$ is empty by <ref>.

If on the other hand $\Xbuf_i$ is a clique buffer, then $|\cK_i|=2\rho|X_i|$. Now let
$W$ be the set of vertices in $V_i$ which are candidates for fewer than
$\mu(dp)^\Delta|X_i|/2$ vertices of $\Xbuf_i$. We will show that $|W|<\rho
If $|W|\ge\rho|V_i|$, then by <ref> there are at most
$\rho|X_i|$ vertices in $\Xbuf_i$ with fewer than $(dp)^\Delta |W|/2$ candidates in $W$. It follows that the average over $v\in W$ of the number of
vertices of $\Xbuf_i$ for which $v$ is a candidate, is at least

\[\frac{1}{|W|}\big(|\Xbuf_i|-\rho|X_i|\big)\frac{(dp)^\Delta

where we used the facts $|\Xbuf_i|=4\mu|X_i|$ and $\rho<\mu$ in the inequality.
Since at least one $v\in W$ attains at least the average, we have a
contradiction to the definition of $W$.

conditions of Lemma <ref> are thus satisfied, and by applying it
we obtain a good partial embedding $\psigood$. Since $\psigood$ extends
$\psiq$ and all sets $\Xc_i$ are contained in $\dom(\psigood)$
by <ref>, we conclude that the only vertices remaining
unembedded are in $\Xbuf$.

Finally, for $i\in[r]$, let $X'_i=\Xbuf_i\setminus\dom(\psigood)$ and let
$\Xbuf_i$ be a degree-$b$ buffer for some $b$. Let
$V'_i=V_i\setminus\im(\psigood)$. Because $|X_i|=|V_i|$ we have
$|X'_i|=|V'_i|$. Because $\psigood$ satisfies <ref>, we
have <ref>. Because $\psigood$ satisfies <ref>, in
particular we have <ref>. Finally, because $\psigood$
satisfies <ref> we have <ref> with
$\delta=\mu(d^\Delta/100)^b$. Thus by Lemma <ref> there
is an embedding $\psi'$ extending $\psigood$ which embeds $H$ into $G$.

§ PROOF OF THE RANDOM GRAPHS RGA LEMMA

In this section we describe the random greedy algorithm (RGA) and prove
that it produces a partial embedding which satisfies the assertions of
the RGA lemma, Lemma <ref>, with high probability.  This is Algorithm <ref>.  It embeds vertices $x$ of $H$
sequentially, following an order $\tau$ given by Lemma <ref>. In
doing so, it builds up a sequence $\psi_0,\dots$ of good partial
embeddings, and a queue of vertices which it will not embed; we
let $Q_t$ be the queue at time $t$ (i.e. corresponding to $\psi_t$).
Recall that by $\Amain_t(x)$ we mean the set $\Amain(x)$ with reference
to the partial embedding $\psi_t$. We let $B_t(x)$ denote the set of bad
vertices (defined in Section <ref>) with respect
to $\psi_t$ and $Q_t$. As mentioned in the proof overview
(Section <ref>), to create $\psi_{t+1}$ from $\psi_t$
we embed some vertex $x$ uniformly at random into the set
$\Amain_t(x)\setminus B_t(x)$, the set of available candidate vertices in
$\Xmain$ minus the bad vertices; and we add $y$ to the queue if
the set $\Amain_t(y)\setminus B_t(y)$ gets small.

Note that exactly $t$ vertices are embedded in $\psi_t$, though these
vertices are not necessarily the first $t$ vertices of $\tau$ because
vertices in $Q_t$ are skipped. The queue set $Q_{t_\RGend}$ at the time
$t_\RGend$ when the RGA terminates will then form the queue $\Xq$.

Random greedy algorithm for random graphs
$G\subseteq \Gamma$ and $H$ with partitions satisfying the General Setup; an ordering $\tau$ of $\Xmain$
$Q_0:=\{x\in V(H):|I_x|<\tfrac12\mu(d-\eps)^{|J_x|}p^{|J_x|}|\Vmain(x)|\}$
$\dom(\psi_t)\cup Q_t=\Xmain$
let $x\in \Xmain\setminus (\dom(\psi_t)\cup Q_t)$ be the next vertex in
the order $\tau$
choose $v\in \Amain_t(x)\setminus B_t(x)$ uniformly at random
$\psi_{t+1}:=\psi_t\cup\{x\to v\}$
$y\in \Xmain\setminus \dom(\psi_{t+1})$
\mu(d-\eps')^{\pi^*_{t+1}(y)}p^{\pi^*_{t+1}(y)}|\Vmain(y)|)$

$t_\RGend:=t \;$

The proof that Algorithm <ref> a.a.s. produces a good partial
embedding with the properties required in Lemma <ref> is now
quite straightforward: most of the work is to check that the conditions
of the various lemmas on RGAs given in Section <ref> are
met. The critical point is to show that certain invariants (see
Claim <ref> below) are maintained.

We require

\[\rho< \mu\le\frac{1}{100\kappa\DeltaRp}\,,\quad \eps'\le \frac{\mu\zeta d^\Delta\rho2^{-4/\rho}}{1000\kappa\Delta^24^\Delta\DeltaRp}\,,\quad\eps\le\frac{\eps'}{\kappa d}\]

\[ p\ge 10r_1\eps^{-1} \big(\tfrac{\log n}{n}\big)^{1/\Delta}\,,\quad n>\kappa r_1^2\,.\]

First, we apply Lemma <ref> to obtain an ordering $\tau$ of the
vertices of $H$ with properties <ref>–<ref> of this lemma.
With this ordering $\tau$ we run the random greedy algorithm, Algorithm <ref>, and in the following we show
that a.a.s.
it produces a good partial embedding $\psiRGA=\psi_{t_\RGend}$ satisfying
properties <ref>–<ref> of Lemma <ref>.

We first show that some invariants are maintained (deterministically)
throughout the algorithm. Recall that $\pi^*_t(x):=\pi_t(x)+|J_x|$, where
$\pi_t(x)$ denotes the number of the embedded neighbours of $x$ at time

The following hold at each time $t$ in Algorithm <ref>.

*  $\psi_t$ is a good partial embedding.

*  For each $x\in\Xmain\setminus\dom(\psi_t)$, either $x\in Q_t$ or we have

\[|\Amain_t(x)|\ge\tfrac12\mu(d-\eps')^{\pi^*_t(x)}p^{\pi^*_t(x)}|\Vmain(x)|\,.\]

*  When we embed $x$ to create $\psi_{t+1}$, we do so
uniformly at random into a set of size at least $\frac{1}{10}\mu\zeta
(dp)^{\pi^*_{t}(x)} |V(x)|$.

We remark that the bound given in <ref> is not sharp, but we
give this relaxed bound in order to re-use the same invariants in the
proofs of our other two blow-up lemmas.

[Proof of Claim <ref>]
The invariant <ref> is maintained by definition of $A_t(x)$ and
$B_t(x)$. Observe that at the end of each iteration of the repeat loop
of Algorithm <ref> the
queue is updated by adding precisely any vertices which would
fail <ref>, so that this invariant also holds.
Finally, by choice of $\eps'$ and by <ref>, if the vertex $x$
is embedded to create $\psi_{t+1}$, then we have
$|\Amain_{t}(x)|\ge\tfrac14\mu(dp)^{\pi^*_{t}(x)}|V(x)|$. Now, if all
neighbours of $x$ are embedded under $\psi_{t}$ then by Lemma <ref><ref>
we have <ref>, while otherwise we apply
Lemma <ref><ref> with $D=\Delta$, for which the
required assumptions on $\Gamma$ hold, to bound $|B_{t}(x)|$. We conclude that <ref> holds.

We now begin to verify the conclusions of Lemma <ref>. Property <ref>, stating that all vertices in $X_i\cap
\dom(\psiRGA)$ are embedded to $\Vmain_i$, holds by our RGA.

Property <ref> holds. Moreover,
let $x$ be a buffer vertex and $y$ its neighbour whose embedding creates $\psi_{t+1}$, then

\begin{equation}\label{eq:rga:Amain}
\big|\Amain_t(y)\big|\ge\tfrac23(dp-\eps'p)^{\pi^*_t}|V(y)|\,.
\end{equation}

We require $\mu\le 1/(100\kappa\DeltaRp)$.
To show <ref>, i.e., that all
neighbours of buffer vertices are in $\dom(\psiRGA)$, it is sufficient to
prove that none of the neighbours of buffer vertices are in $Q_{t_\RGend}$.
However, this is clear. Indeed, suppose that $y_1,\dots, y_{b}$ with $b\leq
\Delta$ are the neighbours of a buffer vertex $x$ appearing in this order
in $\tau$.  Suppose the embedding of $y_1$ creates $\psi_{t_1+1}$. By <ref>, buffer vertices are at distance at least five in $H$, hence,
the neighbours of the vertices have distance at least three, and by <ref> they are not image restricted. Therefore,
at time $t_1$ the available candidate set of each $y_j$ is
$\Amain_{t_1}(y_j)=\Vmain(y_j)\setminus \im(\psi_{t_1})$. The size of
$\Amain_{t_1}(y_j)$  is by <ref>, <ref> and choice of $\mu$ at least

\[
|\Vmain(y_j)|-4\kappa\DeltaRp\mu|V(y_j)|=(1-3\mu-4\kappa\DeltaRp\mu)|V(y_j)|\ge \tfrac{2}{3}|V(y_j)|\,.
\]

It follows that $y_j$ is not added to $Q_t$ for any $t\le t_1$. Now the
vertices $y_1,\ldots,y_b$ are embedded consecutively by
Lemma <ref><ref>, and since they are neighbours of $x$,
by <ref>, into distinct clusters of $G$.
By Definition <ref> (of bad vertices with respect to $\psi$ and $Q$),
for each time $t'$ with $t_1\le t'\le t$, where $y_j$ is embedded to create $\psi_{t+1}$, we have

\[|\Amain_{t'}(y_j)|\ge \tfrac23(dp-\eps'p)^{\pi^*_{t'}(y_j)}|V(y_j)|\,,\]

which gives (<ref>) and that $y_j$ never enters $Q_t$, as desired.

We next verify <ref> and <ref>. To this end
observe that because Algorithm <ref> preserves <ref>,
the conditions of Lemma <ref> are met. Thus with
probability at least $1-2^{-n/(\kappa r_1)}$, the following event
$\ev_{\sublem{lem:rga:welldistr}}$ holds. For every $i\in[r]$ and $W\subset
V_i$ with $|W|\ge\rho|V_i|$, the number of vertices $x\in X_i\setminus
X^*_i$ such that for some time $t$ (at which $x$ is unembedded) we have
$\big|C_t(x)\cap W\big|<(dp-\eps'p)^{\pi^*_t(x)}|W|$ is at most

Suppose now that $\ev_{\sublem{lem:rga:welldistr}}$ holds. We first show
that then <ref> holds. Set
$W:=\Vmain_i\setminus\im(\psi_{t_\RGend})$. By <ref>
and <ref>, we have $|\Xmain_i|\le (1-4\mu)|X_i|$ and
$|\Vmain_i|=(1-3\mu)|V_i|$. We conclude $|W|\ge\mu|V_i|$. Suppose that
$x\in Q_{t_\RGend}$. Then there is a first time $t$ at which $x\in Q_t$.
Since we have $\Amain_t(x)\supseteq C_t(x)\cap W$, by the construction of
$Q_t$ in Algorithm <ref>, we have

\[|C_t(x)\cap W|<\tfrac12\mu(d-\eps')^{\pi^*_t(x)}p^{\pi^*_t(x)}|\Vmain(x)|<\big((d-\eps')p\big)^{\pi^*_t(x)}|W|\]

so that $x$ satisfies condition (<ref>) of
Lemma <ref>. Since $|W|>\rho|V_i|$, and because
$\ev_{\sublem{lem:rga:welldistr}}$ holds, the number of $x\in \Xmain_i\cap
Q_{t_\RGend}$ which are in $X_i\setminus X^*_i$ is at most $\rho|X_i|$.
By <ref>, we have $|X^*_i|\le\rho|X_i|$, so $|\Xmain_i\cap
Q_{t_\RGend}|\le\rho|X_i|+|X^*_i|\le2\rho|X_i|$. By definition of
Algorithm <ref>, the vertices $\Xmain_i\cap Q_{t_\RGend}$ are
precisely the vertices of $\Xmain_i$ not in $\dom(\psi_{t_\RGend})$,
giving <ref> as desired.

Property <ref> follows from
$\ev_{\sublem{lem:rga:welldistr}}$ by observing that $\Xbuf_i\subset X_i$
and that when $\Xbuf_i$ is a degree-$b$ buffer we have
$(dp-\eps'p)^{\pi^*_{t_\RGend}(x)}\ge (dp)^b/2$ by choice of $\eps'$.

To complete the proof of Lemma <ref> we now verify that a.a.s.after Algorithm <ref> finishes, also <ref> is
satisfied. By <ref> and <ref>  of
Lemma <ref>, the set of vertices in $N(\Xbuf)$ which are not
neighbours of clique buffer vertices is an initial segment of $T$ vertices
of $\tau$. We first show that the embedding of these $T$ vertices cannot
fill up vertex neighbourhoods in $G$. For this purpose we want to apply
Lemma <ref> to the
sequence of good partial embeddings produced by Algorithm <ref> on
this initial segment. Observe that by Claim <ref>, all
vertices in this initial segment satisfy (<ref>) and none
enters the queue. By (<ref>), Lemma <ref>, and the
choice of $\eps'$, each such $y$, embedded to create $\psi_{t+1}$, is
embedded into a subset of $C_{t}(y)$ of size at least

\[\tfrac{2}{3}(dp-\eps'p)^{\pi^*_{t}}|V(y)|-20\Delta^2\eps'p^{\pi^*_t(y)}|V(y)|>\tfrac1{10}(dp)^{\pi^*_{t}(y)}|V(y)|\,.\]

Furthermore, for each such $y$ we have $\pi^*_{t}(y)\le \Delta-2$ by
Lemma <ref><ref>. Finally, by <ref> we have
$\big|\dom(\psi_T)\cap X_i\big|\le 4\mu\kappa\DeltaRp|X_i|$ for each
$i\in[r]$. This justifies that we can apply Lemma <ref> with
$B=\Delta$, and the result is that with probability at least $1-\exp(-\eps
p n/r_1)$, the following event $\ev_{\sublem{lem:large_nbs}}$ holds. For
each $v\in V_i$ and $j$ such that $ij\in E(R')$, we have

\begin{equation}\label{eq:rga:initial}
\big|N_G(v;\Vmain_j)\setminus\im(\psi_T)\big|\ge\tfrac12\deg_G(v;V_j)\,.
\end{equation}

We assume from now on that $\Xbuf_i$ is a non-clique degree-$b$ buffer, and
we fix a vertex $v\in V_i$. We would like to estimate the probability
that <ref> fails for $v$. To that end, first fix
$x\in\Xbuf_i$, and let $y_1,\ldots,y_b$ be an enumeration of $N_H(x)$ in
the order $\tau$. We now justify that if $\ev_{\sublem{lem:large_nbs}}$
holds, then we are in a position to apply Lemma <ref>
with $B=\Delta$. Recall that no vertices of $N(\Xbuf)$ enter the queue, by
Claim <ref>, so that $\psi_{\tau(y_1)}$ is the good partial
embedding created by the embedding of $y_1$ (and so on). By <ref>,
and since $\dom(\psi_{\tau(y_1)-1})\subset N(\Xbuf)$, no vertices at
distance two or less from $x$ in $H$ are embedded in $\psi_{\tau(y_1)-1}$.
Note that Lemma <ref><ref> states that if $b=\Delta$
then $y_{b-1}y_b$ is not an edge of $H$. Algorithm <ref> thus
creates a sequence $\psi_{\tau(y_1)-1},\dots,\psi_{\tau(y_b)}$ of good
partial embeddings, and a sequence of queue sets
$Q_{\tau(y_1)-1},\dots,Q_{\tau(y_b)}$, matching the requirements of
Lemma <ref>. Thus, by
Lemma <ref>, the probability that $N_H(x)$ is embedded
to $N_G(v)$, conditioning on $\psi_{\tau(y_1)-1}$ and that
for each $j$ such that $ij\in R'$ (which is justified by (<ref>)), is at least $(d^\Delta p/10)^b$.

Now we use this to estimate the cumulative effect of all $x\in\Xbuf_i$. Let
$x_1,\dots,x_m$ be an enumeration of $\Xbuf_i$ according to the order on
$N(\Xbuf)$ given by $\tau$. Let $Y_1,\ldots,Y_m$ be Bernoulli random
variables with $Y_j=1$ if either $N_H(x_j)$ is embedded by
$\psi_{t_\RGend}$ to $N_G(v)$ or we witness a failure of
$\ev_{\sublem{lem:large_nbs}}$ before the first neighbour of $x_j$ is
embedded. Then we have just shown that $Y_j$ has probability at least
$(d^\Delta p/10)^b$ of being one, conditioned on the history up to, but not
including, the embedding of the first vertex of $N_H(x_j)$. This history
determines $Y_{j-1}$, so we can apply Lemma <ref>, with
$x=4\mu|X_i|(d^\Delta p/10)^b$ and $\delta=\tfrac12$, to conclude that
$Y_1+\dots+Y_m\ge 2\mu|X_i|(d^\Delta p/10)^b$ with probability at least
$1-\exp(-\mu|X_i|(d^\Delta p/10)^b/3)$. Taking the union bound over all
$v\in V(G)$ we see that with probability at least $1-n\exp(-\eps p^\Delta
n/r_1)>1-1/n$ (where the inequality is by choice of $p$ and since
$b\le\Delta$), either we witness a failure of
$\ev_{\sublem{lem:large_nbs}}$, or <ref> holds.

Putting together the three probability bounds, we conclude that a.a.s. the events $\ev_{\sublem{lem:rga:welldistr}}$, $\ev_{\sublem{lem:large_nbs}}$ and <ref> all hold, proving Lemma <ref>.

§ QUEUE EMBEDDING

In this section we prove Lemma <ref>. The idea is as follows. For each $i\in[r]$ in succession, we embed $\Xq_i$ into $\Vq_i$, maintaining a good partial embedding. The way we do this is as follows. We need to embed each $x\in\Xq_i$ into $\Cq(x)\setminus B(x)$, where $B(x)$ is the set of bad vertices for $x$ with respect to the current good partial embedding and $Q=V(H)$. (This choice of $Q$ is
made only so that we are able to apply Lemma <ref> without having to verify the at this time pointless badness condition (<ref>).)
We therefore try to find a system of distinct representatives $v_x\in
\Cq(x)\setminus B(x)$ for each $x\in \Xq_i$, which we do by verifying