Hall's condition. In turn, we verify Hall's condition by showing that its
failure implies the existence of a dense spot in $G$, violating
$\CON(\rho,r_1,\Delta)$, which $\Gamma$ satisfies. At this point one might
be concerned that embedding $x'\in\Xq_i$ to $v_{x'}$ could change $B(x)$.
Observe, however, that since $x$ and $x'$ are at distance at least ten in $H$
by <ref> this does not occur.

We require

\[\mu\le\frac16\,,\qquad\rho\le\frac{\mu\zeta d^\Delta}{200\kappa\Delta}\,, \qquad \eps'\le \frac{\mu\zeta d^\Delta}{1000\kappa4^\Delta\Delta^2}\qquad\text{and}\qquad\eps\le\frac{\eps'}{\kappa d}\,.\]

Let $\psi_0$ be a good partial embedding whose image is disjoint from $\Vq$, and suppose that for each $i\in[r]$ the set $\Xq_i$ has size at most $2\rho|X_i|$. We now define a sequence of good partial embeddings $\psi_1,\ldots,\psi_r$ with $\dom(\psi_t)=\dom(\psi_0)\cup\bigcup_{j=1}^t\Xq_j$ and $\psi_t(x)\in \Vq_j$ for each $x\in\Xq_j$ and $1\le j\le t$. We let $C_t(x)$ be the candidate set of $x$ with respect to $\psi_t$, and so on, and let $B_t(x)$ be the set of bad vertices for $x$ with respect to $\psi_t$ and $Q=V(H)$.

Suppose that for some $1\le t\le r$ we have constructed $\psi_{t-1}$ as above. We let $(v_x)_{x\in\Xq_t}$ be a system of distinct representatives for the sets $\big(\Cq_{t-1}(x)\setminus B_{t-1}(x)\big)_{x\in\Xq_t}$, and we set $\psi_t=\psi_{t-1}\cup\{x\to v_x\colon x\in\Xq_t\}$. We need to prove that this system of distinct representatives exists, and that the resulting $\psi_t$ is a good partial embedding.

To see that the system of distinct representatives exists, we verify Hall's condition. Let $X\subset\Xq_i$ be non-empty, and let $W=\bigcup_{x\in X} \Cq_{t-1}(x)\setminus B_{t-1}(x)$. Then we need to show $|W|\ge|X|$. Assume for a contradiction that $|W|<|X|$ holds. By averaging, there is $b\in\{0,\dots,\Delta\}$ such that we find a subset $X_b$ of (not necessarily all) vertices $x$ in $X$ with $\pi_{t-1}^*(x)=b$ of size exactly $\tfrac{1}{\Delta+1}|W|$. Now each $x\in X_b$ has $\Cq_{t-1}(x)\ge (1-\eps')\mu(dp-\eps'p)^{b-|J_x|}|I_x|$ by <ref>, and $|I_x|\ge\zeta(dp-\eps'p)^{|J_x|}|V_i|$ by <ref>. We conclude, by Lemma <ref>, that

\[\big|C_{t-1}(x)\setminus B_{t-1}(x)\big|\ge \tfrac12\mu\zeta(dp)^b|V_i|-20\Delta^2\eps'p^b|V_i|\ge\tfrac14\mu\zeta(dp)^b|V_i|\]

by choice of $\eps'$. In particular, we see that for each $x\in X_b$ we have $\big|U_{t-1}(x)\cap W\big|\ge\tfrac14\mu\zeta(dp)^b|V_i|$. We therefore have

\[
\sum_{x\in X_b}\big|U_{t-1}(x)\cap W\big|\ge|X_b|\cdot \tfrac14\mu\zeta(dp)^b|V_i|\,.
\]

Since we would like to resort to the congestion property $\CON(\rho,r_1,\Delta)$ we eventually need to pass to a subset $W'$ of $W$ of size  $|X_b|$. Picking uniformly at random a subset $W'$ of $W$ of size $|X_b|=\tfrac{|W|}{\Delta+1}$, we

\[
\Exp_{W'}\sum_{x\in X_b}\big|U_{t-1}(x)\cap W'\big|\ge\tfrac{|X_b|}{\Delta+1}\cdot \tfrac14\mu\zeta(dp)^b|V_i|\,,
\]

and so in particular there is a subset $W'$ of $W$ of size $|X_b|$ such that

\begin{equation}\label{eq:queue:sumU}
\sum_{x\in X_b}\big|U_{t-1}(x)\cap W'\big|\ge
\tfrac{|X_b|}{\Delta+1}\cdot \tfrac14\mu\zeta(dp)^b|V_i|\,.
\end{equation}

Recall that $\Pi_{t-1}(x)$ is the set of embedded neighbours of $x$ in $\psi_{t-1}$.
We now apply $\CON(\rho,r_1,\Delta)$ with
$\mathcal{F}=\big\{\psi_{t-1}\big(\Pi_{t-1}(x)\cup J_x\big)\colon x\in
and the set $W'$. Note that
because the sets $\psi_{t-1}\big(\Pi_{t-1}(x)\cup J_x\big)$ are disjoint, so that we
can do this. We conclude that the congestion graph
$\AG(\Gamma,W',\mathcal{F})$ satisfies

\begin{equation}\label{eq:queue:AG}
e\big(\AG(\Gamma,W',\mathcal{F})\big)\le7p^b|W'||\mathcal{F}|+\rho p^b
\end{equation}

But the edges of this congestion graph are precisely the pairs $F_xu$
such that $F_x=\psi_{t-1}\big(\Pi_{t-1}(x)\cup J_x\big)$
for $x\in X_b$ and $u\in U_{t-1}(x)\cap W'$, so
combining (<ref>) and (<ref>) we have

\[\tfrac{1}{4(\Delta+1)}\mu\zeta (dp)^b|X_b||V_i|\le 14\rho p^b|X_b||V_i|+\rho\kappa p^b |X_b||V_i|\,,\]

where we use $|X_b|=|W'|=|\mathcal{F}|\le 2\rho|V_i|$ and $|V_i|\ge n/(\kappa r_1)$. This is a contradiction by choice of $\rho$. We conclude that the desired system of distinct representatives exists.

Now we show that $\psi_t$ is a good partial embedding. Since the $v_x$ are
distinct, $\psi_t$ is injective. Since $\Cq_{t-1}(x)\subset I_x$ for each
$x$, we have <ref> for each $x\in\Xq_i$. If <ref>
or <ref> were to fail for some $y$, then $y\in N_H(x)$ for some
$x\in\Xq_i$. Since by <ref>, vertices of $\Xq_i$ are at distance
at least $10$ in $H$, this $x$ is unique. But by definition of
$B_{t-1}(x)$ the vertex $v_x$ is not bad for $x$ with respect to
$\psi_{t-1}$, i.e. this case does not occur. Finally, if <ref>
fails for some $yz\in E(H)$, then again at least one of $y$ and $z$
(possibly both) is a neighbour of some $x\in\Xq_i$. Again
by <ref> this $x$ is unique, and again by definition of
$B_{t-1}(x)$ the vertex $v_x$ is not bad for $x$ with respect to $\psi_{t-1}$, so this case too does not occur. Thus $\psi_t$ is a good partial embedding as desired.

By induction on $t$, the final $\psiq:=\psi_r$ is a good partial embedding satisfying the conclusion of Lemma <ref>.

§ FIXING BUFFER DEFECTS

To prove Lemma <ref> we need to embed the reserved
cliques. The basic idea is as follows. If $\Xbuf_i$ is a clique buffer,
and a vertex $v$ of $V_i$ is a candidate for too few vertices in
$\Xbuf_i$ and not in the image of $\psi$ (we call such a vertex poor),
then we will embed a reserved clique $K\in\cK_i$ on $v$ and some further vertices
of $\Vc$. Observe that, since $K$ is a $(\Delta+1)$-clique, none of the
vertices of $K$ have embedded neighbours, hence $v$ is in the available
candidate set of the vertex of $K$ in $X_i$.

The only difficulty now is that some of the poor vertices $v$ may
lie in $\Vbuf_i$, and we risk destroying the hard-earned property that
every vertex in $\Xbuf_i$ has many candidates. In order to deal with this,
we will need to embed some vertices from $\Xbuf_i$ as well, at which point
further vertices of $V_i$ may become poor and require embedding, and so

Before we prove Lemma <ref> we state two auxiliary lemmas. The
first justifies that the process just described terminates without eating up too many
vertices, that is, that we can find for each $i$ small subsets $P_i$ of $V_i$ and
$D_i$ of $\Xbuf_i$ such that every vertex $x\in\Xbuf_i\setminus D_i$ has many candidates in $\Vbuf_i\setminus P_i$, and every vertex of
$V_i\setminus P_i$ is a candidate for many vertices of $\Xbuf_i\setminus D_i$.

We assume the General Setup. Suppose that $\Gamma$ has
$\CON(\rho,r_1,\Delta)$ and let $i$ be fixed.  Suppose $\psi$ is a good
partial embedding whose domain contains $N(\Xbuf)$, and that $\Xbuf_i$
is a clique buffer. Suppose furthermore that all but at most $\rho
|V_i|$ vertices of $V_i$ are candidates for at least
$\mu(dp)^\Delta|X_i|/2$ vertices of $\Xbuf_i$. Then there are subsets
$P_i$ of $V_i$ and $D_i$ of $\Xbuf_i$ with the following properties.

*  We have $|P_i|<2\rho|V_i|$ and

*  Each vertex of $\Xbuf_i\setminus D_i$
has at least $\mu(dp)^\Delta|V_i|/4$ candidates in $\Vbuf_i\setminus

*  Each vertex of $V_i\setminus P_i$ is a
candidate for at least $\mu(d p/100)^{\Delta}|X_i|$ of the vertices in
$\Xbuf_i\setminus D_i$.

*  Each vertex in $D_i$ has at least
$\mu(dp)^\Delta|V_i|/4$ candidates in $P_i\cap\Vbuf_i$.

The conclusion <ref> will be used to show that we can embed $D_i$ into $P_i\cap\Vbuf_i$.

We require

\[\rho<\frac{\mu d^\Delta}{250\kappa}\,.\]

We start with $D_i=\emptyset$ and $P_i$ being the set of vertices which
fail <ref>.  We sequentially add vertices to $D_i$
and $P_i$ which fail <ref>
and <ref> respectively (note that the property of
failing either condition is monotone), until either there are no
failing vertices to add to either set or one of the two sets reaches
$2\rho|V_i|$ vertices. Observe that any vertex $x$ of $D_i$ has
by <ref> at least $(1-\eps')\mu(d-\eps')^\Delta p^\Delta
|V_i|$ candidates in $\Vbuf_i$. Since $x$ must have
violated <ref> at some point, by choice of $\eps'$
it therefore has at least $\mu(dp)^\Delta|V_i|/4$ candidates in
$P_i\cap\Vbuf_i$, establishing <ref>.

In the process of building $D_i$ and $P_i$ we call a vertex $v\in V_i\setminus P_i$
poor if $v$ is a candidate for less than $\mu(d p/100)^{\Delta}|X_i|$ vertices of $\Xbuf_i\setminus D_i$.
If $P_i$ reaches $2\rho|V_i|$ vertices first, let $P=P_i$
and let $D$ a superset of $D_i$, both of size exactly $2\rho|V_i|$. Since at most
$\rho|V_i|$ vertices in $V_i$ are poor with respect to $\Xbuf_i$, at
least $\rho|V_i|$ of the vertices in $P$ were added to $P_i$ because
they became poor, that is, they are candidate for at least
$\mu(dp)^\Delta|X_i|/2$ vertices of $\Xbuf_i$, but for less than
$\mu(dp/100)^\Delta|X_i|$ of the vertices $\Xbuf_i\setminus D_i$. It
follows that each is candidate for at least $\mu(dp)^\Delta|X_i|/4$
vertices of $D_i$, and so there are at least
$\rho|V_i|\mu(dp)^\Delta|X_i|/4$ edges in the candidate graph between $P$
and $D$. Now

\begin{align*}
\tfrac{1}{4}\rho\mu(dp)^\Delta|X_i||V_i|&=
\tfrac{1}{8}\rho\mu(dp)^\Delta|X_i||V_i|+\tfrac{1}{8}\rho\mu(dp)^\Delta|X_i||V_i|\\
&> \frac{\mu d^\Delta}{32\rho}p^\Delta|P||D| +\frac{\mu
d^\Delta}{8 \kappa r_1} p^\Delta n|D|\\
&> 7p^\Delta|P||D|+\rho p^\Delta n|D|/r_1\,,
\end{align*}

where the first inequality comes from the sizes of $P$ and $D$, and the
second from the choice of $\rho$ sufficiently small. The last line is in
contradiction to the congestion condition $\CON(\rho,r_1,\Delta)$, since the candidate graph
between $P$ and $D$ is a subgraph of $\AG(\Gamma,P,\cF_D)$ with
$\cF_D:=\{\psi(N_H(x))\colon x\in D\}$.

If on the other hand $D_i$ reaches
$2\rho|V_i|$ vertices first, we define similarly $P$ a superset of $P_i$ and $D=D_i$, both of size $2\rho|V_i|$.  Each
vertex of $D$ has at least $\mu(dp)^\Delta|V_i|/4$ candidates in $P$
by <ref>, and thus the candidate graph between $P$ and
$D$ has at least $2\rho|X_i|\mu(dp)^\Delta|V_i|/4$ edges, which is larger
than in the previous case and so also gives a contradiction to

We conclude that the process terminates for lack of failing vertices, which establishes <ref>.

The second lemma simply gives a condition on a vertex $v\in V_i$ under which
we can find a clique $K_{\Delta+1}$ containing $v$ in $G$ whose remaining
vertices lie in $\Vc\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
$i,j_1,\ldots,j_\Delta$ form a copy of $K_{\Delta+1}$ in $R'$ and $v$ be a
vertex of $V_i$. Suppose that $\psi$ is any good partial embedding
which embeds no vertex on $v$, and is such that $v$ has at least

\begin{equation}\label{eq:findclique:deg}
\tfrac{\mu d}{8}\max\big(p|V_{j_k}|,\deg_\Gamma(v;V_{j_k})\big)
\end{equation}

neighbours in
$\Vc_{j_k}\setminus\im(\psi)$ in $G$ for each $1\le k\le\Delta$.
Suppose that there is a copy of $K_{\Delta+1}$ in $H$ using a vertex of
$\tilde{X}_i$ and a vertex of each of $X_{j_1},\ldots,X_{j_\Delta}$. Then there are vertices $v_{k}\in\Vc_{j_k}\setminus\im(\psi)$ for $1\le k\le\Delta$,
such that $v,v_1,\ldots,v_\Delta$ form a copy of $K_{\Delta+1}$ in $G$.

We require

\[\eps<\eps'<\frac{(d/32)^\Delta\mu}{2\kappa\Delta^2}\,.\]

We choose the vertices $v_1,\ldots,v_\Delta$ in succession. When we choose
$v_s$, if $s<\Delta$ we require that for each $s+1\le k\le\Delta$ we have

\begin{equation}\label{eq:degree_reg_Kc}
|\comN_\Gamma(v,v_1,\ldots,v_s)\cap V_{j_k}|= (p\pm\eps p)^s
\deg_\Gamma(v;V_{j_k})\text{ and }
\end{equation}

\begin{equation}\label{eq:degree_two_Kc}
|\comN_G(v,v_1,\ldots,v_s)\cap \left(\Vc_{j_k}\setminus \im(\psi)\right)|\ge
\big(\tfrac{dp}{4}\big)^{s}\tfrac{\mu
\end{equation}

If $s<\Delta-1$ we further require that for
each $s+1\le k<k'\le\Delta$ the pair

\begin{equation}\label{eq:RI_Kc}
\big(\comN_\Gamma(v,v_1,\ldots,v_s)\cap
V_{j_k},\comN_\Gamma(v,v_1,\ldots,v_s)\cap V_{j_{k'}}\big)
\end{equation}

is $(\eps_{s,s},d,p)$-regular.

Note that these conditions are satisfied, with $s=0$, before we have chosen
any vertices. Indeed, the first is a tautology, the second is the assumption on $v$
in the lemma statement, and the third is a statement that $V_i$ has
two-sided inheritance with respect to $V_{j_k}$ and $V_{j_{k'}}$, which
holds since we assumed there is a triangle of $X$ using one vertex of each
of $\tX_i$, $X_{j_k}$ and $j_{k'}$ and
by <ref> and <ref>.

Suppose we have chosen vertices $v_1$,…, $v_{s-1}$ so far
and that we have $s\le \Delta-1$.
Because $\Gamma$ has $\NS(\eps,r_1,\Delta)$, at
step $s$ the number of vertices $w$ failing condition (<ref>) with $v_s=w$, is at most

\[\Delta\eps
$(\eps_{s-1,s-1},d,p)$-regularity of the pair

\[\big(\comN_\Gamma(v,v_1,\ldots,v_{s-1})\cap
V_{j_k},\comN_\Gamma(v,v_1,\ldots,v_{s-1})\cap V_{j_{k'}}\big)\,,\]

and using the upper bound from (<ref>) on
$\comN_\Gamma(v,v_1,\ldots,v_{s-1})\cap V_{j_k}$, at most

\[\Delta\eps'(p+\eps
$w\in \Vc_{j_s}\setminus \im(\psi)$ fail condition (<ref>) with $v_s=w$.
Finally, if $s\le\Delta-2$ and since $\Gamma$ has $\RI(\eps,(\eps_{a,b}),\eps',d,r_1,\Delta)$, at most

\[\Delta^2\eps

vertices fail condition (<ref>). Thus there are at least

\[\big(\tfrac{dp}{4}\big)^{s-1}\tfrac{\mu
vertices which
satisfy all three conditions, and we can choose $v_s$ for each $1\le s\le\Delta$ as desired.

Furthermore observe that for $s=\Delta$ it suffices to choose
an arbitrary vertex from $\comN_G(v,v_1,\ldots,v_{\Delta-1})\cap \left(\Vc_{j_\Delta}\setminus \im(\psi)\right)$.
The lemma follows.

We can now prove Lemma <ref>. We construct the desired
embedding in two steps. First, we embed each $D_i$ into $P_i\cap\Vbuf_i$,
which by verifying Hall's condition. Let $P'_i$ be those vertices
of $P_i$ not covered in this process. It then remains to cover all $P'_i$
using the reserved cliques, and embed any left-over reserved cliques
at the end of this process. We do this sequentially by applying
Lemma <ref> to find a destination for a reserved clique,
either letting $v$ be the next poor vertex or, if all of these are used,
letting $v$ be some vertex of $\Vc$. Note that in this step, we
need to maintain the degree condition (<ref>) of
Lemma <ref>. We have this condition initially
by <ref>, and we will see that to maintain it, it suffices to
choose at each step a most dangerous vertex $v$, that is, one
minimising the parameter $\mindeg$ we define in the proof.

We require

\[\rho<\min\Big(\frac{\mu
d^\Delta}{250\kappa},\frac{\mu d}{64\kappa(\DeltaRp+1)}\Big) \quad\text{ and  }
\eps<\eps'<\frac{d^\Delta}{32^\Delta\kappa\Delta\DeltaRp}\,,\]

and assume that $\Gamma$ has $\NS(\eps,r_1,\Delta)$, $\RI(\eps,(\eps_{a,b}),\eps',d,r_1,\Delta)$ and

For each $i$ such that $\Xbuf_i$ is a clique buffer, we let $P_i$ and $D_i$
be as given by Lemma <ref>.
If $\Xbuf_i$ is not a clique buffer, then we let $P_i=D_i=\emptyset$.

Now for each $i$ in succession, we find a matching in the candidate graph
between $D_i$ and $P_i\cap\Vbuf_i$. To do this we simply verify Hall's
condition, using the congestion condition and <ref>.
Specifically, suppose we have a non-empty $W\subseteq D_i$, and $Z\subseteq
P_i$ is the set of vertices in $P_i$ which are candidate for some $w\in W$.
We need to verify that $|W|\le|Z|$. If this were false, then we could let
$Z'$ be a superset of $Z$ of size $|W|$, and the number of edges in the
candidate graph between $W$ and $Z'$ is by <ref> at
least $\mu(dp)^\Delta|V_i||W|/4$. Notice that $|D_i|$, $|P_i|<2\rho|V_i|$
by <ref>. Hence we have

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

which is in contradiction to $\CON(\rho,r_1,\Delta)$, applied with $Z'$
and the family $\cF=\{\psi(N_H(w)) \colon w\in W\}$ to the congestion
graph $\AG(\Gamma,Z',\cF)$. We conclude that Hall's condition holds and
hence the desired matching exists. We let $\psi'$ be the embedding
obtained from $\psi$ by embedding each vertex of each $D_i$ to its
matching partner in $P_i\cap\Vbuf_i$, and let $P'_i\subset P_i$ be the
set of those vertices in $P_i$ not embedded by $\psi'$.  Observe that
$\psi'$ is a good partial embedding since all neighbours of the buffer
vertices are already embedded under $\psi$, and
thus <ref>–<ref> trivially hold for $\psi'$.

As second step, we provide an algorithm, Algorithm <ref>, to embed the reserved cliques
in $\cK_i$ for each $i\in[r_1]$.  Given a vertex $v\in V_i$ and a
partial embedding $\psi$ we define the parameter

\[\mindeg_{\psi}(v):=
\min_{j:ij\in R'}\frac{\deg_G\big(v;\Vc_j\setminus\im(\psi)\big)}

which is used in Algorithm <ref>.
Observe that
we have initially $\mindeg_{\psi}(v)\ge \mu (d-\eps)/2$ for
all $v\in V_i$ with $\deg_{R'}(i)>0$,  which follows from <ref>.
We claim that the algorithm runs correctly and the finally returned
$\psigood$ is the desired good partial embedding. It remains to justify this

Removing poor vertices
$\bigcup_i \cK_i\neq\emptyset$
$I:=\{i\colon\text{there is an unembedded clique in }\cK_i\}$
$\bigcup_i P'_i\setminus\im(\psi_t)\neq\emptyset$
choose $v\in \bigcup_i P'_i\setminus\im(\psi_t)$ minimising

choose $v\in \bigcup_{i\in I} \Vc_i\setminus\im(\psi_t)$ minimising $\mindeg_{\psi_t}(v)$

set $i$ such that $v\in V_i$
choose an unembedded clique $K_H$ in $\cK_i$
choose a clique $K_G$ containing $v$ and one vertex
from each $\Vc_j\setminus\im(\psi_t)$ such that $X_j$ intersects $K_H$ and $j\neq i$
set $\psi_{t+1}:=\psi_t\cup\{K_H\to K_G\}$

return $\psigood:=\psi_t$

Roughly speaking
each of the vertices from $P'_i$ can serve us as an image for each of the
$2\rho|X_i|$ cliques from $\cK_i$.
During the first first phase of the algorithm, that is, while the
if-condition is true, we embed reserved cliques in these vertices,
always choosing a vertex $v$ minimising $\mindeg_\psi(v)$, which will guarantee
successful completion.
Note that $|P'_i|<2\rho|V_i|$ holds by <ref> and $|\cK_i|=2\rho|X_i|$, so
if the algorithm doesn't fail then all the vertices from
$\bigcup_i P'_i$ will be used. In the second phase, when the
if-condition becomes false, we have to take
care of the remaining unembedded cliques in $\bigcup_i\cK_i$.
Since the
algorithm embeds only onto vertices $\bigcup P'_i\cup \Vc_i$, if it
completes successfully, then the desired
properties <ref> and <ref> are
guaranteed for $\psigood$
by <ref>  and <ref>.

Therefore, it remains to show that the algorithm succeeds, that is,
that there is no
failure while choosing  a clique $K_G$ in some iteration.
By Lemma <ref>, this is
guaranteed if we can show that at each time $t$ the vertex $v\in V_i$ chosen
has at least

\begin{equation}\label{eq:delbad:fail}
\tfrac{\mu
\end{equation}

neighbours in each set $\Vc_j\setminus \im(\psi_t)$ such that $ij\in

By the assumption of the lemma, for each $i$,  the set $\Xc_i$ of vertices
$x\in X_i$ contained in some reserved clique from $\bigcup_{j}\cK_j$ satisfies
$|\Xc_i|\le 2\kappa(\DeltaRp+1)\rho|X_i|$.
It follows that for
any $t$ we have

\begin{equation}\label{eq:delbad:psi}
|\im(\psi_t)\cap\Vc_j|\le 2\kappa(\DeltaRp+1)\rho|X_j|\,.
\end{equation}

For any $t$ at most $\DeltaRp\eps p^{\Delta-1}|V(\Gamma)|/r_1^2$
vertices $v\in V_i$ satisfy
\[\mindeg_{\psi_t}(v)<3\mu d/16\,.\]

Each vertex $v$ of $V_i$ has at least

\[\mu (d-\eps)\max\big(p|V_j|,\deg_\Gamma(v;V_j)/2\big)>\tfrac{\mu
neighbours in
$\Vc_j$ by <ref>.
Moreover, it is a direct consequence of the
neighbourhood size property $\NS(\eps,r_1,\Delta)$ of $\Gamma$ and (<ref>)
that the number of vertices in
$\Gamma$ which have more than $4\kappa(\DeltaRp+1)\rho p|X_j|$
neighbours in $\im(\psi_t)\cap\Vc_j$ is at most $\eps
Since $4\kappa(\DeltaRp+1)\rho p|X_j|<\mu
dp|V_j|/16$, it follows that for any $t$ there are at most
$\DeltaRp\eps p^{\Delta-1}|V(\Gamma)|/r_1^2$ vertices in $V_i$ with
fewer than $\tfrac{3\mu
d}{16}\max\big(p|V_j|,\deg_\Gamma(v;V_j)\big)$ neighbours in any
set $\Vc_j\setminus\im(\psi_t)$ such that $ij\in R'$, that is, with
$\mindeg_{\psi_t}(v)<3\mu d/16$.

In the remainder we show that if Algorithm <ref> chooses a vertex $v$
such that (<ref>) fails, then we obtain a contradiction to
Claim <ref>.
Indeed, in each iteration at most one vertex is embedded in any given $\Vc_j$. So if
there is a time $t$ at which a vertex $v\in V_i$ is chosen with fewer

than the bound in (<ref>)
in some set $\Vc_j\setminus\im(\psi_t)$ such that $ij\in R'$, then at each
of the preceding $\mu dp|V_j|/16$ times $t'$ the vertex $v$ had
$\mindeg_{\psi_{t'}}(v)<3\mu d/16$. Hence each of the at least $\mu d p
n/(16\kappa r_1)$ vertices $v'$ chosen at these times has

\[\mindeg_{\psi_t}(v')\le\mindeg_{\psi_{t'}}(v')<3\mu d/16\,.\]

there are at most $r_1$ clusters $V_i$ in $G$, and since
\[\mu d p
n/(16\kappa r_1)>r_1\DeltaRp\eps p^{\Delta-1}|V(\Gamma)|/r_1^2\,,\]
contradicts Claim <ref>.

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

§ THE RGA LEMMA AND THE PROOF OF THE BLOW-UP LEMMA

In this section we prove Lemma <ref>, conditional on the random greedy lemma (Lemma <ref>) which we prove in Section <ref>.

The proof is quite similar to that of Lemma <ref>, and indeed we make use of the same General Setup. The difference is that we can no longer use property $\CON(\rho,r_1,\Delta)$ as
a bijumbled graph $\Gamma$ need not satisfy it (see the discussion in Section <ref>). Instead, we `replace' it with the lopsided neighbourhood size property $\LNS(\eps,r_1,\Delta)$.

In the next section we will use a somewhat different random greedy strategy than Algorithm <ref> to prove the following lemma. However, we will re-use the auxiliary lemmas proved in Section <ref> in its proof.

We assume the General Setup. Suppose further that $\Gamma$ has properties $\NS(\eps,r_1,\Delta+1)$, $\RI(\eps,(\eps_{a,b}),\eps',d,r_1,\Delta+1)$ and $\LNS(\eps,r_1,\Delta)$, and that at most $\rho p^\Delta|X_i|$ vertices in each $X_i$ are image restricted. Then there is a good partial embedding $\psiRGA$ such that the
following hold for each $i$. Let $b$ be such that $\Xbuf_i$ is a degree-$b$

*  Every vertex in
$\Xmain$ is embedded to
$\Vmain\cup \Vq$ by $\psiRGA$, and no vertex in $\Xbuf$ is embedded.

*  Every vertex in $V_i$ is a
candidate for at least $\mu(d^\Delta p/100)^b|X_i|$ vertices of $\Xbuf_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 $\tfrac12(dp)^b|W|$ candidates in $W$.

*  For all $x\in \Xbuf_i$ we have

\begin{equation*}
\sum_{y\in\Xbuf_i:\big|\Ubuf(y)\cap \Cbuf(x)\big|>(p+\eps p)^{b}|\Cbuf(x)|} \frac{\big|\Ubuf(y)\cap \Cbuf(x)\big|}{\big|\Cbuf(y)\big|}
\le\frac{|\Cbuf(x)|}{20}\,.
\end{equation*}

For each $i$, for all but at most $\eps' p^\Delta |V_i|$ vertices $v\in V_i$, there are at most $\eps'p^\Delta|V_i|$ vertices $v'\in V_i$ such that

\[\big|\{x\in\Xbuf_i:v,v'\in C(x)\}\big|>24\mu\Delta^2\big(20\mu^{-1}\zeta^{-1}d^{-\Delta}\big)^b p^{2b}|X_i|\,.\]

Comparing this lemma to Lemma <ref> (RGA lemma), one notices that we demand more of the $\NS$ and $\RI$ pseudorandomness properties. The reason for doing this is that we can then make use of Lemmas <ref> and <ref> for all buffer vertices, whether or not they are in copies of $K_{\Delta+1}$, and thus there is no exception for clique buffers in <ref>. Recall that Lemma <ref> asserts that while embedding a small initial segment (in particular the neighbours of the buffer vertices), the neighbourhoods of other vertices are reduced by at most a factor of $1/2$ in size, while Lemma <ref> gives a lower bound on the (conditional) probability
of the event that a given vertex from $G$ can be used as an image of a particular buffer vertex. This simplifies our proof substantially—we no longer need to fix buffer defects—and in this case has very little effect on the bijumbledness we ultimately require of $\Gamma$ (it only affects the result in the case $\Delta=2$).

Property <ref> corresponds to <ref>.  We
also see that we ask for an additional pseudorandomness property
$\LNS(\eps,r_1,\Delta)$, which we require in order to embed all
vertices (the algorithm does generate a queue, but it also embeds it)
and also in order to obtain <ref> and <ref>,
which then form the `no dense spots' property we require in order to
complete the embedding, which rôle was played in the proof of
Lemma <ref> by the $\CON$ property. Somewhat
informally, <ref> asserts that typically candidate sets
intersect as if they are random sets, while
property <ref> states the same about intersections of the
neighbourhoods of vertices from $V(G)$ in the candidate graph.

§.§ Outline of the proof of Lemma <ref>

The proof of Lemma <ref> now looks quite similar to the proof of Lemma <ref>. Again, we use Lemma <ref> to obtain the General Setup. However this time we do not choose any reserved cliques, whether or not we have buffer vertices in cliques. We note that although we could state a version of Lemma <ref> which asked only for $\NS(\eps,r_1,\Delta)$ and $\RI(\eps,(\eps_{a,b}),\eps',d,r_1,\Delta)$ rather than with $\Delta+1$, and which made exceptions for clique buffers, this would not improve our eventual bijumbledness requirement on $\Gamma$, except for $\Delta=2$, since for $\Delta\ge 3$ the requirement is determined by $\LNS(\eps,r_1,\Delta)$. We apply Lemma <ref> to obtain a good partial embedding whose domain is $\Xmain$ with the additional properties stated there. We then have only to embed $\Xbuf$. Again, we do this one part at a time, by verifying Hall's condition, and again we separate the verification into small, large and medium-sized subsets of $\Xbuf_i$. Again, the `medium-sized' case is dealt with quickly using <ref>.

However now we approach the `small' and large cases differently, since we no longer have access to the $\CON$ property. In the `small' case (Claim <ref>), our approach is the following. Given $X\subset\Xbuf_i$, we try to construct an embedding of $X$ into $\Vbuf_i$ such that each $x$ is embedded into $C(x)$. Although this embedding is not part of the embedding we will finally give, its existence verifies Hall's condition for $X$. The way we will construct the embedding is simply to embed $X$ vertex by vertex, at each step choosing for $x$ uniformly at random a so far unused vertex of $\Cbuf(x)$. Since $\psiRGA$ has <ref> we know $\Cbuf(x)$ is always reasonably large, and we will show that with high probability it is never more than half covered. Let us briefly explain how this works. We assume that no candidate sets are more than half covered before reaching $x$. When we embedded some vertex $y$, the probability of embedding it to $C(x)$ was at most

\[\frac{\big|\Ubuf(y)\cap \Cbuf(x)\big|}{\tfrac12|\Cbuf(y)|}\]

since (by assumption) we embed $y$ into a set of size at least $\tfrac12|\Cbuf(y)|$, of which certainly at most $\big|\Ubuf(y)\cap \Cbuf(x)\big|$ are in $\Cbuf(x)$. But <ref> gives us an upper bound for the sum of these probabilities over all $y\in\Xbuf_i$ such that the probability is `large', and it is easy to account for the $y\in\Xbuf_i$ such that the probability is not large. We can thus apply Lemma <ref> to conclude that it is unlikely that $\Cbuf(x)$ was more than half covered, and by the union bound over all $x\in\Xbuf_i$ we conclude that with high probability we never fail.

For the `large' case, Claim <ref>, we use a similar argument, but using <ref> and <ref> instead of <ref> and <ref>.

§.§ Proof of Lemma <ref>

Now we give the full details outlined above.

First we choose constants as follows. Given $\Delta$, $\DeltaRpbl$, $\Delta_J$ integers, $\alphabl$, $\zetabl$ and $d>0$, and $\kappabl>1$, we set $\vartheta=\Delta$, $\DeltaRp=8(\Delta+\Delta_J)^{10}\DeltaRpbl$, $\alpha=\tfrac12\alphabl$, $\zeta=\tfrac12\zetabl$ and $\kappa=2\kappabl$. We now choose

\begin{align*}
\mu&= \frac{\alpha d^\Delta}{20000\kappa \DeltaRp^4\Delta^{10}(\Delta+2)},
&\rho&= \tfrac{\mu^2\zeta^2}{2000\Delta^2}\big(\tfrac{\mu \zeta d^{4\Delta+2}}{10^{6\Delta}}\big)^\Delta\,,\\
&\text{and}\quad&\eps'&=\tfrac{\mu\zeta d^{\Delta^2}\rho}{100^{3\Delta}\Delta^3\kappa4^\Delta}2^{-4/\rho}\,.
\end{align*}

Now for input $\Delta$, $d$ and $\eps'$, Lemma <ref> returns constants $\eps_{a,b}$ and $\eps_{\sublem{lem:det_jumbled}}>0$.
We set

\[\eps=  \min\big(\tfrac{2^{10\Delta}d(\eps')^2}{\kappa\DeltaRp},\eps_{\sublem{lem:det_jumbled}}\big)\,.\]

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 small for Lemma <ref> with input $\Delta$, $d$, $\eps'$ and $T=r_1$.

We require

\[p\ge \tfrac{10^6(\Delta+\Delta_J)^{10}\kappa r_1}{\mu\zeta\rho d^\Delta \eps^{-2}} \big(\tfrac{\log n}{n}\big)^{1/(2\Delta)}\,,\]

where the condition on the constant in front of $\big(\tfrac{\log n}{n}\big)^{1/(2\Delta)}$-term comes from Lemma <ref>, while the term $\big(\tfrac{\log n}{n}\big)^{1/(2\Delta)}$ is required for Lemma <ref>.
We remark however that this lower bound is not a restriction since a somewhat stronger lower bound  on $p$ of the form $\Omega(n^{1/2(t-1)})$ for any $(p,cp^tn)$-bijumbled graph follows by considering the inequality (<ref>) which defines bijumbledness for, say, sets $X=\{v\}$ and $Y=V(\Gamma)\setminus(\{v\}\cup N_\Gamma(v))$.

Let $\Gamma$ be an $n$-vertex, $(p,cp^{\max(4,3\Delta/2+1/2)}n)$-bijumbled graph. Then Lemma <ref> states that $\Gamma$ has the three properties $\NS(\eps,r_1,\Delta+1)$, $\RI(\eps,(\eps_{a,b}),\eps',d,r_1,\Delta+1)$ and $\LNS(\eps,r_1,\Delta)$. From now on we will simply assume $\Gamma$ is an $n$-vertex graph which satisfies these three properties.

Given a graph $\Rbl$ on $\rbl\le\ronebl$ vertices, a spanning subgraph $\Rpbl$ with $\Delta(\Rpbl)\le\DeltaRpbl$, and graphs $H$ and $G\subset\Gamma$ with vertex partitions $\cXbl$ and $\cVbl$, a family of potential buffer vertices $\tcXbl$, and a $(\rhobl p^\Delta,\zetabl,\Delta,\Delta_J)$-restriction pair $\cIbl$, $\cJ$, suppose that the conditions of Lemma <ref> are satisfied. Then Lemma <ref> (with $b_{\sublem{lem:matchreduce}}=\Delta$) gives 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.

We let $\Xmain=V(H)\setminus\Xbuf$. We now begin the embedding of $H$ into $G$. By Lemma <ref>, there is a good partial embedding $\psiRGA$ of $\Xmain$ into
$\Vmain\cup\Vq$ with properties <ref>–<ref> stated in that lemma.

Our aim now is to complete the embedding of $H$ into $G$ by finding for each
$i$ a matching in the available candidate graph between $V'_i:=V_i\setminus\im(\psiRGA)$ and $\Xbuf_i$. Let us assume that $\Xbuf_i$ is a degree-$b$ buffer. To show there is a matching, we will verify Hall's condition, so let $Y$ be a non-empty subset of $\Xbuf_i$. Let $U$ be the set of vertices in $V'_i$ which are candidate for at least one vertex of $Y$, then our aim is to show $|U|\ge|Y|$. We split this into three cases, the harder two of which are done in the following claims.

If $0<|Y|\le\rho|X_i|$, then we have $|U|\ge|Y|$.

By <ref> no $y\in Y$ is image restricted, so because $\psiRGA$ is a good partial embedding, by <ref> for each $y\in Y$ we have

\[|\Cbuf(y)|\ge(1-\eps')\mu(d-\eps')^bp^b|V_i|\ge\tfrac12\mu (dp)^b|V_i|\,,\]

where the second inequality is by choice of $\eps'$. Let $y_1,\ldots,y_{|Y|}$ be an enumeration of $Y$.
Now for each $j=1,\ldots,|Y|$ we choose $v_j$ uniformly at random from $\Cbuf(y_j)\setminus \{v_1,\ldots,v_{j-1}\}$ if this is possible; if not, we say $v_j$ does not exist. Our aim is to show that this does not occur, in other words that we obtain $|Y|$ distinct vertices of $|U|$, verifying the claim.

Let $\hist_0$ be the empty history, and for each $1\le j\le |Y|$, let $\hist_j$ be the history of this process up to and including the choice of $v_j$. We claim that a.a.s.
\begin{equation}\label{eq:psr:smallY}
\big|\Cbuf(y_j)\setminus\{v_1,\ldots,v_{j-1}\}\big|\ge\tfrac12\big|\Cbuf(y_j)\big|
\end{equation}

holds for each $j$. For a given $j$ we define random variables $Z^{(j)}_\ell$, $\ell\in[j-1]$, as follows.
We set $Z^{(j)}_\ell=1$ if $v_\ell\in \Cbuf(y_j)$ and $|\Cbuf(y_\ell)\setminus\{v_1,\ldots, v_{\ell-1}\}|\ge \tfrac{1}{2}|\Cbuf(y_\ell)|$ hold, and
$Z^{(j)}_\ell=0$ otherwise. For any history $\hist_{\ell-1}$ of this process we can bound the
conditional expectation of $Z^{(j)}_\ell$ by

\begin{multline}\label{eq:psr:expZ}
\Exp(Z^{(j)}_\ell|\hist_{\ell-1})=\Pr(Z^{(j)}_\ell=1|\hist_{\ell-1})\\
\le \frac{\big|\Cbuf(y_\ell)\cap \Cbuf(y_j)\setminus\{v_1,\ldots,v_{\ell}\}\big|}{\big|\Cbuf(y_\ell)\setminus\{v_1,\ldots,v_{\ell-1}\}\big|}\le\frac{\big|\Ubuf(y_\ell)\cap\Cbuf(y_j)\big|}{\tfrac12\big|\Cbuf(y_\ell)\big|}\,.
\end{multline}

Observe that $\sum_{\ell=1}^{j-1}Z^{(j)}_\ell$ is exactly the number of those  vertices $v_k$ among $v_1$, …, $v_{\ell-1}$ which lie in $\Cbuf(y_j)$ and were chosen from a set of size at least  $\tfrac{1}{2}|\Cbuf(y_k)|$.
To obtain an upper bound on the expectation of
$\sum_{\ell=1}^{j-1}Z^{(j)}_\ell$, we sum up (<ref>) for all $\ell\in[j-1]$. We split this sum according to whether $\big|\Ubuf(y_\ell)\cap \Cbuf(y_j)\big|\le(p+\eps p)^b|\Cbuf(y_j)|$ or not.
In the former case, each summand is by <ref> and <ref> at most

\[\frac{2(p+\eps p)^b\mu (p+\eps p)^b|V_i|}{(1-\eps')\mu(dp-\eps'p)^b|V_i|}\le 4d^{-\Delta}p^b\,,\]

where the inequality is by choice of $\eps$ and $\eps'$, while <ref> bounds the sum over the remaining terms. We get

\begin{align*}
\sum_{\ell=1}^{j-1}\Exp\big[Z^{(j)}_\ell\big|\hist_{\ell-1}\big]&\le\sum_{\ell=1}^{j-1}\frac{\big|\Ubuf(y_\ell)\cap\Cbuf(y_j)\big|}{\tfrac12\big|\Cbuf(y_\ell)\big|}\\
&\le 4(j-1)d^{-\Delta} p^b+\frac{|\Cbuf(y_j)|}{10}\le \frac{|\Cbuf(y_j)|}{5}
\end{align*}

where the last inequality uses $j\le|Y|\le\rho|X_i|$, <ref> and the choice of $\rho$ and $\eps$. Using Lemma <ref> with $\delta=1$, we conclude that the probability of the event $\sum_{\ell=1}^{j-1}Z^{(j)}_\ell>\tfrac25|\Cbuf(y_j)|$ is at most $e^{-|\Cbuf(y_j)|/15}\le e^{-\mu d^b p^b|V_i|/30}$.

Observe that the event$\sum_{\ell=1}^{j-1}Z^{(j)}_\ell>\tfrac25|\Cbuf(y_j)|$ contains the event that (<ref>) fails at $j$, given that it did not fail for smaller $j$. Thus, taking a union bound over the $|Y|\le n$ values of $j$, we see that the probability that (<ref>) fails at any stage is at most

\[n\cdot  e^{-\mu d^b p^b|V_i|/30}\,,\]

which is smaller than one for all sufficiently large $n$ by choice of $p$.

We conclude that there is a positive probability of choosing $|Y|$ distinct vertices in $U$, so $|U|\ge|Y|$ as desired.

We stress that although the proof of Claim <ref> constructs an embedding, this embedding is not part of the final embedding of $H$ into $G$, and exists only to verify the claim. The same goes for the following claim.

If $|Y|>|\Xbuf_i|-\rho|X_i|$, then $|U|\ge|Y|$.

As in the proof of Lemma <ref>, the vertices $V'_i\setminus U$ are candidates only for vertices of $\Xbuf_i\setminus Y$, and since $|V'_i|=|\Xbuf_i|$, what we need to show is that $|V'_i\setminus U|\le |\Xbuf_i\setminus Y|$.

Let $v\in V_i'$ be a vertex and let $C(v)$ denote those vertices $x$ from $\Xbuf_i$
for which $v$ is a candidate, i.e. $C(v)$ denotes the neighbours of $v$ in the candidate graph between
$V'_i\setminus U$ and  $\Xbuf_i\setminus Y$.
By <ref>, for each vertex $v$ of $V'_i\setminus U$ we have
$|C(v)|\ge\mu(d^\Delta p/100)^b|X_i|$. By <ref>, for all but at most $\eps'p^\Delta|V_i|$ vertices $v$ of $V'_i\setminus U$, we have

\begin{equation}\label{eq:psr:rightVsum}
\Big|\Big\{v'\in V_i\colon \big|\{x\in\Xbuf_i:v,v'\in C(x)\}\big|> 24\mu\Delta^2\big(\tfrac{20}{\mu\zeta d^{\Delta}}\big)^b p^{2b} |X_i|\Big\}\Big|\le\eps'p^\Delta|V_i|\,.
\end{equation}

We choose an ordering $v_1,\ldots,v_{|V'_i\setminus U|}$ of $V'_i\setminus U$ which puts the vertices $v$ failing (<ref>) first. We choose, for each $j=1,\ldots,|V'_i\setminus U|$, a vertex $x_j$ uniformly at random from the vertices of $\Xbuf_i\setminus\{x_1,\ldots,x_{j-1}\}$ for which $v_j$ is a candidate if this is possible; if not, we say $x_j$ does not exist. As in the previous claim, our aim is to show that a.a.s. this does not occur.

Let $\hist_0$ be the empty history, and for each $1\le j\le |V'_i\setminus U|$, let $\hist_j$ be the history of this process up to and including choosing $x_j$. We claim that, with positive probability, at each step $i$ we choose from a set of size at least $\tfrac{1}{2}|C(v_i)|\ge \tfrac12\mu(d^\Delta p/100)^b|X_i|$.

We introduce random variables $Z^{(j)}_i$ for $j\in[|V_i'\setminus U|]$ and $\ell\in[j-1]$ as follows.
We set $Z^{(j)}_\ell=1$ if $x_\ell\in C(v_j)$ and
$|C(v_\ell)\setminus\{x_1,\ldots, x_{\ell-1}\}|\ge \tfrac{1}{2}|C(v_\ell)|$ hold, and we set
$Z^{(j)}_\ell=0$ otherwise. Observe that $\sum_{\ell=1}^{j-1}Z^{(j)}_\ell$ is exactly the number of vertices $x_k$ among $x_1$, …, $x_{\ell-1}$ which lie in
$C(v_j)$ and which were chosen from a set of size at least $\tfrac{1}{2}|C(v_k)|$.
Thus, it suffices to show that with positive probability, for every $j$ we have

\begin{equation}\label{eq:psr:numZ}
\sum_{\ell=1}^{j-1}Z^{(j)}_\ell< \tfrac12\mu(d^\Delta p/100)^b|X_i|\,.
\end{equation}

If $v_j$ is a vertex failing (<ref>), then
$j\le\eps'p^\Delta|V_i|<\tfrac{1}{4}\mu(d^\Delta p/100)^b|X_i|$,
where the second inequality is by choice of $\eps'$.
Thus, even if all vertices $x_1,\ldots,x_{j-1}$ happen to be
candidates for  $v_j$, we still have (<ref>). Next we assume that $v_j$
satisfies (<ref>). For each of the at most
$\eps'p^\Delta|X_i|$ vertices $v_\ell$ such that

\[\big|\{x\in\Xbuf_i:v_j,v_\ell\in C(x)\}\big|> 24\mu\Delta^2\big(20\mu^{-1}\zeta^{-1}d^{-\Delta}\big)^b p^{2b} |X_i|\,,\]

the conditional expectation $\Exp(\tZ^{(j)}_\ell|\hist_{\ell-1})$   can be bounded from above by $1$,
while for the remaining vertices, it is at most

\[
\frac{\big|\{x\in\Xbuf_i:v_j,v_\ell\in C(x)\}\big|}{\tfrac{1}{2}|C(v_\ell)|}\le\frac{24\mu\Delta^2\big(20\mu^{-1}\zeta^{-1}d^{-\Delta}\big)^b p^{2b}}{\tfrac12\mu(d^\Delta p/100)^b}\le 48\Delta^2\big(\tfrac{2000}{\mu\zeta d^{2\Delta}}\big)^\Delta p^b\,.
\]

This yields

\[
\sum_{\ell=1}^{j-1}\Exp\big[\tZ^{(j)}_\ell\big|\hist'_{\ell-1}\big]\le \eps'p^\Delta|X_i|+|V'_i\setminus U|\cdot 48\Delta^2\big(\tfrac{2000}{\mu\zeta d^{2\Delta}}\big)^\Delta p^b\le \tfrac{1}{4}\mu(d^\Delta p/100)^b|X_i|\,,
\]

where the last inequality is because $|V'_i\setminus U|\le \rho|X_i|$ and by choice of $\rho$ and $\eps'$. As before, we apply Lemma <ref> for each $j\in[|V'_i\setminus U|]$ with $\delta=1$ and $(\tZ^{(j)})_{\ell\in[j-1]}$. We thus may bound  the probability that $v_j$ is candidate for more than $\tfrac{1}{2}|C(v_i)|\ge\tfrac12\mu(d^\Delta p/100)^b|X_i|$ of the vertices $x_1,\ldots,x_{j-1}$ by at most $e^{-\mu(d^\Delta p/100)^b|X_i|/12}$. Taking a union bound over the at most $\rho|X_i|$ choices of $j$ we see that with probability $1-\rho|X_i|\cdot e^{-\mu(d^\Delta p/100)^b|X_i|/12}>0$ (where the inequality is by choice of $p$), at each step we choose from a set of size at least $\tfrac12\mu(d^\Delta p/100)^b|X_i|$ as claimed. In particular, we succeed in choosing $|V'_i\setminus U|$ distinct vertices of $\Xbuf_i\setminus Y$, so as desired we have $|U|\ge|Y|$.

The final case is to show that $\rho|X_i|<|Y|\le|\Xbuf_i|-\rho|X_i|=|V'_i|-\rho|V_i|$ and $|U|<|Y|$ is a contradiction. In this case, we have $|V_i'\setminus U|>\rho|V_i|$. By <ref> there are at most
$\rho|X_i|$ vertices of $\Xbuf_i$ with fewer than $\tfrac12(dp)^b|V_i'\setminus U|$
candidates in $V_i'\setminus U$, so in particular there is a vertex of $Y$ with
candidates in $V_i'\setminus U$, in contradiction to the definition of $U$.

This completes the verification of Hall's condition, so we can extend
$\psiRGA$ to an embedding $\psi$ of $H$ into $G$ as desired, completing the
proof of Lemma <ref>.

§ PROOF OF THE BIJUMBLED GRAPHS RGA LEMMA

The proof of Lemma <ref> is very similar to the proof of Lemma <ref> (RGA lemma), and indeed we can reuse the auxiliary lemmas of Section <ref>. We again use a random greedy algorithm which we show produces the desired embedding with high probability. The difference from Algorithm <ref> is that when at time $t$ we reach a vertex $x$ in the order $\tau$ (given again by Lemma <ref>) which is in the queue $Q_{t}$, we do not skip it, but instead we embed it into $\Vq$. Thus, we will always have $t=\tau(x)-1$.
The embedding will be done uniformly at random into the set $\Aq_{t}(x)\setminus B_{t}(x)$. We remind, that $B_t(x)$
is the set of bad vertices with respect to $\psi_t$ and $Q_t$, that is, the vertices $v$ such that the extension $\psi_{t}\cup\{x\to v\}$ is not a good partial embedding or there is an unembedded neighbour $y$ of $x$ not in $Q_{t}$ such that $\deg_G\big(v;\Amain_t(y)\big)<(d-\eps')p|\Amain_t(y)|$ holds (see Definition <ref>).

The embedding algorithm we use is Algorithm <ref>.
Random greedy algorithm for bijumbled graphs
$G\subseteq \Gamma$ and $H$ with partitions satisfying the General Setup; an ordering $\tau$ on $\Xmain$
$Q_0:=\{x\in V(H):|I_x|<\tfrac12\mu(d-\eps)^{|J_x|}p^{|J_x|}|\Vmain(x)|\}$
let $x\in \Xmain\setminus \dom(\psi_t)$ be the next vertex in
the order $\tau$
$x\in Q_t$ and $|\Aq_t(x)\setminus B_t(x)|<\tfrac{1}{10}\mu\zeta(dp)^{\pi^*_t(x)}|V(x)|$halt with failure
choose $v$ uniformly at random in $\begin{cases}
\Amain_t(x)\setminus B_t(x) \quad & \text{if $x\not\in Q_t$} \\
\Aq_t(x)\setminus B_t(x) & \text{if $x\in Q_t$}
\end{cases}$
$\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)|)$

Observe that there is an important difference from Algorithm <ref>. Algorithm <ref> can fail, and we will have to prove that with high probability it does not. This means proving that sets $\Aq_t(x)$ do not get small, or equivalently that sets $\Cq_t(x)$ are never substantially covered by $\im(\psi_t)$. However there is also an important similarity: provided the algorithm has not yet halted with failure, it maintains the same invariants as Algorithm <ref> (see Claim <ref>).

Observe that (in contrast to Algorithm <ref>) if Algorithm <ref> has not yet failed at time $t$, then all of the first $t$ vertices in the order $\tau$ have been embedded. Thus $\pi^*_{\tau(x)-1}(x)$ is always equal to $\pitau(x)$, where

\[\pitau(x):=\big|\{y\in N_H(x):\tau(y)<\tau(x)\}\big|+|J_x|\,.\]

Much of the work of proving Lemma <ref> is contained in the auxiliary lemmas in Section <ref> which we use again here. What remains is to justify that Algorithm <ref> with high probability does not halt with failure and does give a good partial embedding with properties <ref> and <ref>.

We require

\begin{align*}
\mu&\le\tfrac{d^\Delta}{1320\kappa\DeltaRp}\,,
&\rho&\le \tfrac{\mu^2\zeta^2 d^{2\Delta}}{2000}\,,\\
\eps'&\le\tfrac{\mu\zeta d^\Delta\rho}{1000\kappa\Delta^2 \DeltaRp 4^\Delta}2^{-4/\rho}\,,
&\eps&\le \min\big((\eps')^2,2^{-\Delta}\eps',\tfrac{\rho\mu\zeta d^\Delta}{20\kappa\Delta},\tfrac{\eps'}{\kappa\DeltaRp}\big)\,,\\
p&\ge \tfrac{1000\Delta^4\kappa r_1^2}{\mu\zeta\rho d^\Delta\eps} \big(\tfrac{\log n}{n}\big)^{1/(2\Delta)}\qquad\text{and}
&2&^{-\eps p n/(\kappa r_1)}r_1n<1\,.
\end{align*}

Recall that we assumed that $\Gamma$ possesses the three properties $\NS(\eps,r_1,\Delta+1)$, $\RI(\eps,(\eps_{a,b}),\eps',d,r_1,\Delta+1)$ and $\LNS(\eps,r_1,\Delta)$. Let $\tau$ be an order on $V(H)$ given by Lemma <ref>. We run Algorithm <ref>.

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

*  $\psi_t$ is a good partial embedding,

*  Either $|\Amain_t(x)|\ge\frac12\mu(d-\eps')^{\pi^*_t(x)}p^{\pi^*_t(x)}|\Vmain(x)|$
or $x\in Q_t$.

*  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)|$.

Algorithm <ref> maintains <ref> and <ref> by definition. Since $\tfrac12\mu(d-\eps')^bp^b-20\Delta^2\eps'p^b>\tfrac{1}{10}\mu\zeta d^bp^b$ by choice of $\eps'$ for each $0\le b\le\Delta$, by Lemma <ref> it also maintains <ref>.

As in the proof of Lemma <ref>, the conditions for Lemma <ref> are met, so we conclude that with probability at least $1-2^{-n/(\kappa r_1)}$, at each time $t$ when Algorithm <ref> is running and for each $i\in[r]$ we have $|Q_t\cap X_i|\le\rho|X_i|+|X^*_i|\le2\rho|X_i|$, where the final inequality is by <ref>. In order to show that Algorithm <ref> runs successfully, we need to show that the `halt with failure' line is a.a.s. never reached, i.e. that if $x\in Q_{\tau(x)-1}$ then $\big|\Aq_{\tau(x)-1}(x)\setminus B_{\tau(x)-1}(x)|$ is at least $\tfrac{1}{10}\mu\zeta(dp)^{\pi^*_{\tau(x)-1}(x)}|V_i|$. Since we know by Lemma <ref> that $B_{\tau(x)-1}(x)$ is small and by <ref> that $\Cq_{\tau(x)-1}(x)$ is large,
what we want is to show that $\im(\psi_{t-1})$ covers only a small fraction of $\Cq_{\tau(x)-1}(x)$.

Observe that we embed the vertices $Q_t\cap X_i$ into $\Vq_i$ in a random procedure which is very similar to the embedding strategy we used in the proof of Claim <ref> (verification of Hall's condition for small sets of buffer vertices). However here a complication is that we do not know `in advance' what $\Cq_{\tau(x)-1}(x)$ will be when embedding earlier vertices to $\Vq_i$. But we do know that it will be contained in the $\Gamma$-neighbourhood in $V_i$ of some collection of $\pitau(x)\le\Delta$ vertices, and that it will be large. Thus, it suffices to prove the following. For each $i$, each $1\le\ell\le\Delta$ and $v_1,\dots,v_\ell$ such that $\comN_\Gamma(v_1,\ldots,v_\ell;V_i)$ is large, $\im(\psi_t)$ never covers much of $\comN_\Gamma(v_1,\ldots,v_\ell;V_i)$. We can prove this statement by using the same analysis as in the proof of Lemma <ref>, given a `sum condition' similar to <ref>. Thus our next task is to show such a statement is likely to hold. We will also show that if Algorithm <ref> does not halt with failure then it is likely to have <ref>, since the arguments are similar.

Suppose that for each $i\in[r]$ and each time $t$ we have $|Q_t\cap X_i|\le2\rho|X_i|$. Then a.a.s. the following statements hold.

For any $t$, any $1\le \ell \le\Delta$, any $i\in[r]$ and any vertices $v_1,\ldots,v_\ell$ such that

\[\deg_\Gamma(v_1,\ldots,v_\ell;V_i)\ge\eps'p^\ell|V_i|\]

we have

\begin{equation}\label{eq:randmatch:sumVqLNS}
\sum_{\substack{y\in\Xmain_i\cap Q_t\colon\\ \tau(y)\le t,J_y=\emptyset}} \frac{\big|U_{\tau(y)-1}(y)\cap \comN_\Gamma(v_1,\ldots,v_\ell;V_i)\big|}{\big|\Aq_{\tau(y)-1}(y)\setminus B_{\tau(y)-1}(y)\big|}\le\frac{\mu\zeta d^\Delta \deg_\Gamma(v_1,\ldots,v_\ell;V_i)}{20}\,.
\end{equation}

For any $1\le \ell \le \Delta$, any $i\in[r]$ and any vertices $v_1,\ldots,v_\ell$ such that

\[\deg_G(v_1,\ldots,v_\ell;\Vbuf_i)\ge(dp-\eps'p)^\ell|\Vbuf_i|\,,\]

we define $X'_i$ to be the set

\[\big\{y\in\Xbuf_i: \big|\Ubuf_t(y)\cap \comN_G(v_1,\ldots,v_\ell;\Vbuf_i)\big|> (p+\eps p)^{\pi^*_t(y)}\deg_G(v_1,\ldots,v_\ell;\Vbuf_i)\big\}\]

and we have

\begin{equation}\label{eq:randmatch:sumVbufLNS}
\sum_{y\in X'_i} \frac{\big|\Ubuf_t(y)\cap \comN_G(v_1,\ldots,v_\ell;\Vbuf_i)\big|}{\big|\Cbuf_t(y)\big|}
\le\frac{\deg_G(v_1,\ldots,v_\ell;\Vbuf_i)}{20}\,.
\end{equation}

The idea of the proof of (<ref>) is as follows. The denominators on the left hand side of (<ref>) are by <ref> never much smaller than they `should' be, so the main task is to show that the numerators do not tend to be too large. To show this, we consider the evolution of $U_t(y)\cap \comN_\Gamma(v_1,\dots,v_\ell;V_i)$ for some fixed $y$ as $t$ increases. Since $J_y=\emptyset$, at first this set has the size we expect, namely it is all of $\comN_\Gamma(v_1,\dots,v_\ell;V_i)$. Each time a neighbour of $y$ is embedded, we expect that the set size shrinks by a factor roughly $p$. If this is the case for each neighbour, the size at $t=\tau(y)-1$ is roughly a $p^{\pitau(y)}$-factor times its original size, which turns out to be a good enough bound for (<ref>). If not, there is some first time when we embed a neighbour of $y$, say the $s$th neighbour, `badly', that is, the set size does not shrink by a factor roughly $p$. We say we fail at step $s$. At worst, it could be that the set size does not thereafter change, so that it stays roughly a $p^{s-1}$-factor times its original size. In this case we `lose' a $p^{\pitau(y)-s+1}$ factor. But the $\LNS$ property tells us that the probability of failing at step $s$ is less than $p^{\pitau(y)-s+1}$. Heuristically, this gets us back the lost factor; to make it rigorous, we apply Lemma <ref>.

We require

\[\rho\le \frac{\mu^2\zeta^2d^{2\Delta}}{2000}\,,\quad\eps\le\min\Big(2^{-\Delta}\eps',\frac{\rho\mu\zeta d^\Delta}{20\kappa\Delta}\Big)\quad\text{and}\quad p\ge\frac{20\Delta^4\kappa r^2_1}{\rho}\big(\tfrac{\log n}{n}\big)^{1/\Delta}\,.\]

We start with (<ref>). Given $1\le \ell\le \Delta $, let $v_1,\ldots,v_\ell$ be vertices of $\Gamma$ such that the set  $U:=\comN_\Gamma(v_1,\ldots,v_\ell;V_i)$ has size at least  $\eps'p^\ell|V_i|$. By <ref> we have the lower bound

\[\big|\Aq_{\tau(y)-1}(y)\setminus B_{\tau(y)-1}(y)\big|\ge \tfrac{1}{10}\mu\zeta(dp)^{\pitau(y)}|V_i|\]

for the denominator in each summand of (<ref>), and the difficulty is to upper bound the numerator. Consider the running of Algorithm <ref>. At any time $t\le\tau(y)-1$, the set $\Uq_t(y)\cap U$ is the $\Gamma$-neighbourhood in $U$ of the $\pi^*_t(y)$ embedded vertices from $N_H(y)$, and in a truly random set we would thus `expect' to find that

\begin{equation}\label{eq:lnssum:Uq}
|U_t(y)\cap U|\le (p+\eps p)^{\pi^*_t(y)}|U|\,.
\end{equation}

If this inequality remains true up to $t=\tau(y)-1$, then since $|J_y|=0$ by assumption, we have $\pi^*_{\tau(y)-1}(y)=\pitau(y)$, and (<ref>) gives an upper bound good enough for the
summand $\frac{\big|U_{\tau(y)-1}(y)\cap \comN_\Gamma(v_1,\ldots,v_\ell;V_i)\big|}{\big|\Aq_{\tau(y)-1}(y)\setminus B_{\tau(y)-1}(y)\big|}$.
However it is likely that some vertices will not satisfy (<ref>), and we have to estimate their contribution to (<ref>).

We say that a vertex $y\in\Xmain_i$ fails at step $s$ if the vertex $z$ is the $s$th vertex of $N_H(y)$ in $\tau$ and $y$ satisfies (<ref>) for each $t\le\tau(z)-1$ but fails (<ref>) at $t=\tau(z)$. Observe that each vertex $y$ in the sum (<ref>) satisfies (<ref>) before any neighbour of $y$ is embedded because $J_y=\emptyset$.  Thus, if $y$ does not fail at any step $s$ with $1\le s\le\Delta$ then it satisfies (<ref>) at time $t=\tau(y)-1$, but if for some $1\le s\le\Delta$ it fails at step $s$, then $|U_{\tau(y)-1}(y)\cap U|\le(p+\eps p)^{s-1}|U|$.

Suppose now that $y$ fails at step $s$. Then the reason is that the vertex $z$, which is the $s$th neighbour of $y$ in $\tau$, is embedded to a vertex of $\Gamma$ with `too many' neighbours in $U_{\tau(z)-1}(y)\cap U$. Let $W$ be a superset of $U_{\tau(z)-1}(y)\cap U$ of size $(p+\eps p)^{s-1}|U|$. By choice of $\eps$ we have $|W|\ge\eps p^{\ell+s-1}|V_i|$. Because $y$ fails at step $s$ we see that $z$ is embedded to a vertex $v$ of $\Gamma$ with $\deg_\Gamma(v;W)>(p+\eps p)^s|U|=(p+\eps p)|W|$. By $\LNS(\eps,r_1,\Delta)$ we know that the number of such vertices $v$ in $\Gamma$ is at most
$\eps p^{2\Delta-s}|V(\Gamma)|/r_1^2$ (since $\ell\le \Delta$). Therefore, by <ref>, the probability of embedding $z$ (which has at least one unembedded neighbour and hence at most $\Delta-1$ embedded neighbours) to such a vertex $v$, conditioning on the history up to but not including embedding $z$, is at most

\[\frac{\eps p^{2\Delta-s}|V(\Gamma)|/r_1^2}{\mu\zeta(dp)^{\Delta-1}|V_i|/10}\le \frac{\rho}{2\Delta} p^{\Delta-s+1}\le\frac{\rho}{2\Delta} p^{\pitau(y)-s+1}\,,\]

where the first inequality is by choice of $\eps$ and the second since $\pitau(y)\le\Delta$.

We can restate this as: the probability that $y$ fails at step $s=\pitau(y)-j+1$, conditioning on the history up to but not including the embedding of the vertex at step $s$, is at most $\tfrac{\rho}{2\Delta}p^j$ for each $1\le j\le \pitau(y)$. It follows that the expected number of vertices $y\in\Xmain_i$ which fail at step $\pitau(y)-j+1$ is at most $\tfrac{\rho}{2\Delta}p^j|X_i|$, and by Lemma <ref>, applied with $\delta=1$, the probability that more than $\tfrac{\rho}{\Delta}p^j|X_i|$ vertices $y\in\Xmain_i$ fail at step $\pitau(y)-j+1$ is at most $\exp\big(-\tfrac{\rho}{6\Delta}p^{j}|X_i|\big)$. The probability that, for each $1\le j\le\Delta$, at most $\tfrac{\rho}{\Delta}p^j|X_i|$ vertices $y$ of $\Xmain_i$ fail at step $\pitau(y)-j+1$ is thus at least

\begin{equation}\label{eq:lnssum:Vqprob}
\end{equation}

Suppose this good event occurs, i.e. for each $j$, at most $\tfrac{\rho}{\Delta}p^j|X_i|$ vertices $y\in\Xmain_i$ fail at  step $s=\pitau(y)-j+1$. Since a vertex $y$ failing at step $j$ satisfies

\[|U_{\tau(y)-1}(y)\cap U|\le (p+\eps p)^{\pitau(y)-j}|U| \]

we have

\begin{multline}\label{eq:LNS:bigY}
\sum_{\substack{y\in\Xmain_i:\\ |U_{\tau(y)-1}(y)\cap U|>(p+\eps p)^{\pitau(y)}|U|}} \frac{\big|U_{\tau(y)-1}(y)\cap U\big|}{\big|\Aq_{\tau(y)-1}(y)\setminus B_{\tau(y)-1}(y)\big|}\\
\le\sum_{\substack{y\in\Xmain_i:\\
y\text{ fails at step }s=\pitau(y)-j+1}} \frac{(p+\eps p)^{\pitau(y)-j}|U|}{\tfrac{1}{10}\mu\zeta(dp)^{\pitau(y)}|V_i|}
\le  \sum_{j=1}^{\Delta} \frac{(p+\eps p)^{\pitau(y)-j}|U|\cdot \tfrac{\rho}{\Delta}p^j|X_i|}{\tfrac{1}{10}\mu\zeta(dp)^{\pitau(y)}|V_i|}\\
\le \frac{20\rho|U|}{\mu\zeta d^{\Delta}}\le\frac{\mu\zeta d^\Delta|U|}{40}\,,
\end{multline}

where the last two inequalities are by choice of $\eps$ and $\rho$ respectively.
On the other hand, because $|\Xmain_i\cap Q_t|\le 2\rho|X_i|$, we have

\begin{equation*}\begin{split}
\sum_{\substack{y\in\Xmain_i\cap Q_t:\\ |U_{\tau(y)-1}(y)\cap U|\le(p+\eps p)^{\pitau(y)}|U|}} \frac{\big|U_{\tau(y)-1}(y)\cap U\big|}{\big|\Aq_{\tau(y)-1}(y)\setminus B_{\tau(y)-1}(y)\big|}\le\\
\sum_{y\in\Xmain_i\cap Q_t}
\frac{(p+\eps p)^{\pitau(y)}|U|}{\tfrac{1}{10}\mu\zeta(dp)^{\pitau(y)}|V_i|}
&\le  \frac{(1+\eps)^{\Delta}|U|\cdot 2\rho|X_i|}{\tfrac{1}{10}\mu\zeta d^{\Delta}|V_i|}\\
&\le \frac{40\rho|U|}{\mu\zeta d^{\Delta}}\le\frac{\mu\zeta d^\Delta|U|}{40}\,,
\end{split}\end{equation*}

and putting these together we conclude (<ref>).

It remains to bound the probability that for some vertices $v_1$, …, $v_\ell$ with
$\deg_\Gamma(v_1,\ldots,v_\ell;V_i)\ge \eps'p^\ell|V_i|$ the inequality (<ref>)
is violated, in other words that the good event mentioned above fails.
There are $r\le r_1$ choices of $i$, and at most $n+n^2+\dots+n^{\Delta}\le \Delta n^{\Delta}$ choices of $v_1,\ldots,v_\ell$, so by the union bound and (<ref>) the probability of such  a bad event occuring is at most

\[r_1\Delta n^{\Delta}\cdot 2\Delta\exp\big(-\tfrac{\rho}{6\Delta\kappa r_1}p^{\Delta}n\big)\]

which tends to zero as $n$ tends to infinity by choice of $p$.

We now come to (<ref>). This inequality looks very much like (<ref>) above, and its proof is almost identical to the proof of (<ref>). The differences are that we consider $G$-neighbourhoods in $\Vbuf_i$ not $\Gamma$-neighbourhoods in $V_i$ and that we have a lower bound on $\Cbuf_t(x)$ from <ref> rather than on $|\Aq_t(x)\setminus B_t(x)|$ from <ref>. Since this lower bound is larger, the same constant choices work. We omit the details.

We note that it is this claim which is most responsible for our eventual bijumbledness requirement on $\Gamma$. Although the proof may seem quite wasteful—we assume that if one neighbour is embedded badly then potentially all future neighbours can be embedded badly without any further penalty, which seems unreasonable—we were not able to make it work with any weaker condition than $\LNS(\eps,r_1,\Delta)$ for general graphs $H$. Our analysis is in some sense tight for vertices $y$ which fail at step $\pitau(y)$, when the final neighbour $z$ of $y$ coming before $y$ in $\tau$ is embedded. What still seems unreasonable is that all the vertices in $\Gamma$ which have exceptionally high degree to $U_{\tau(z)-1}(y)\cap U$ turn out to be in $A_{\tau(z)-1}(z)$, which is the worst case we are effectively using in our proof. We expect that a more careful analysis, possibly involving some modification to Algorithm <ref>, would allow one to improve on this and thus improve on the bijumbledness requirement of Lemma <ref>.

We can now use Lemma <ref> to complete the proof that the sets $\Cq_t(x)$ do not get covered by $\im(\psi_t)$, much as in Claim <ref> (verification of Hall's condition for small sets of buffer vertices).

A.a.s. for each $x\in\Xmain$, at each time $t\le\tau(x)-1$ and before the termination of Algorithm <ref>, we have $\big|\Cq_t(x)\cap\im(\psi_t)\big|<\tfrac12\big|\Cq_t(x)\big|$.

We require

\[\eps\le \eps'\le 2^{-2\Delta}, \qquad \rho\le \tfrac{\mu \zeta d^\Delta}{30}\qquad\text{and}\qquad p\ge \tfrac{1000r_1}{\mu\zeta d^\Delta}\big(\tfrac{\log n}{n}\big)^{1/\Delta} \,.\]

Suppose that the conclusions of Claim <ref> hold (in particular (<ref>) holds). Given $i\in[r]$ and $x\in\Xmain_i$, if $t\le\tau(x)-1$ and Algorithm <ref> has not terminated before time $t$, then by <ref> and <ref> we have $\big|\Cq_t(x)\big|\ge (1-\eps')\mu\zeta(dp-\eps'p)^{\pi^*_t(x)}|V_i|$. Since $\Cq_t(x)\subset U_t(x)= \comN_\Gamma(v_1,\ldots,v_\ell;V_i)$ for some vertices $v_1,\ldots,v_\ell$ with $\ell=\pi^*_t(x)\le\Delta$, we conclude by (<ref>) that

\[\sum_{\substack{y\in\Xmain_i\cap Q_t\colon \tau(y)\le t\\J_y=\emptyset}} \frac{\big|\Uq_{\tau(y)-1}(y)\cap \Cq_t(x)\big|}{\big|\Aq_{\tau(y)-1}(y)\setminus B_{\tau(y)-1}(y)\big|}\le\frac{\mu\zeta d^\Delta\big|U_t(x)\big|}{20}\,.\]

Observe that the summand in the above inequality is an upper bound for the probability that $y$ is embedded to $\Cq_t(x)$ for $y\in Q_t$, conditioning on the history up to but not including the embedding of $y$. Since the probability that $y$ is embedded to $\Cq_t(x)$ is zero if $y$ is not in $Q_t$, we are in a position to apply Lemma <ref>. This lemma, with $\delta=1$, tells us that the probability that more than $\tfrac1{10}\mu\zeta d^\Delta\big|U_t(x)\big|$ vertices $y$ of $\Xmain_i$ with $J_y=\emptyset$ are embedded to $\Cq_t(x)$ is at most $\exp\big(-\tfrac{1}{60}\mu\zeta d^\Delta|U_t(x)|\big)$. If this `bad' event does not occur, then by <ref>, <ref> and <ref>, and because the number of vertices in $\Xmain_i$ with $J_y\neq\emptyset$ is by <ref> at most $\rho p^\Delta|X_i|$, we have the desired statement:

\[
\big|\Cq_t(x)\cap\im(\psi_t)\big|< \tfrac{1}{10}\mu\zeta d^\Delta\big|U_t(x)\big|+\rho p^\Delta|X_i|\le\tfrac{1}{2}
\]

The probability that the conclusions of Claim <ref> fail to hold, or that any of the above `bad' events occur, is at most $o(1)+r_1 n^2\cdot\exp\big(-\tfrac{1}{60r_1}\mu\zeta d^\Delta(p-\eps'p)^\Delta n\big)$, which tends to zero as $n$ tends to infinity by choice of $p$, completing the proof.

If the conclusions of Lemma <ref>, Claim <ref> and
Claim <ref> hold (which we think of as being good events),
then by <ref> and Lemma <ref> we have

\[\big|\Aq_{\tau(x)-1}(x)\setminus B_{\tau(x)-1}(x)\big|\ge\tfrac12\mu\zeta(dp-\eps'p)^{\pitau(x)}|V_i|-20\Delta^2\eps'p^{\pitau(x)}|V_i|\]

and the right hand side is by choice of $\eps'$ at least $\tfrac{1}{10}\mu\zeta(dp)^{\pitau(x)}|V_i|$. In other words, the `halt with failure' line of Algorithm <ref> is never reached. Since each of the three good events a.a.s. occurs, the algorithm a.a.s. completes successfully. Now <ref> is guaranteed by successful completion of Algorithm <ref>, and <ref> is as <ref> in the proof of Lemma <ref> implied by the good event of Lemma <ref>, while <ref> is given by the good event of Claim <ref>, specifically taking (<ref>) with $t=t_\RGend$ and vertices $\psi_t\big(N_H(x)\big)$ for each $x\in\Xbuf_i$.

Next we establish that <ref> a.a.s. holds. We apply Lemma <ref> with $B=\Delta+1$ and $T=\tau(z)$ where $z$ is the last vertex in $N(\Xbuf)$. Since $N(\Xbuf)$ forms the initial segment of $\tau$ by Lemma <ref><ref>, we see that all vertices $y$ embedded up to time $T$ have $\pitau(y)\le\Delta-1\le B-2$, and by identical logic as in Claim <ref> none of these vertices enter the queue. Therefore, by <ref>, Lemma <ref> and choice of $\eps'$, each $y$ from $N(\Xbuf)$  is embedded uniformly at random to a set of size at least $\tfrac{1}{10}(dp)^{\pitau(y)}|V(y)|$. Finally, by <ref> we have $|N(\Xbuf)\cap X_i|\le4\kappa\DeltaRp\mu|X_i|$ for each $i\in[r]$. This justifies that the conditions of Lemma <ref> are met, so we conclude that a.a.s. the following event $\ev_{\sublem{lem:large_nbs}}$ occurs. For each $v\in V_i$ and $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;\Vmain_j)$.

We are now in a position to apply Lemma <ref>, again with $B=\Delta+1$. Observe that this time, if $\ev_{\sublem{lem:large_nbs}}$ occurs, it applies to any $x\in\Xbuf_i$ and $v\in V_i$, whether or not $x$ is in a clique buffer. The deduction that a.a.s. the embedding $\psi_{t_\RGend}$ has <ref> follows exactly as in the proof of Lemma <ref> (RGA lemma), and we do not repeat it.

It remains to establish <ref>. For this we require the following claim, which shows that if vertices $v$ and $v'$ are common candidates for too many $x\in\Xbuf_i$ for <ref>, then the reason is that they have an exceptionally large  common $\Gamma$-neighbourhood in some cluster.

Asymptotically almost surely at the termination of Algorithm <ref> the following holds. For each $i$ and pair of vertices $v,v'\in V_i$ such that $\deg_\Gamma(v,v';V_j)\le(p+\eps p)^2|V_j|$ whenever $ij\in R'$, if $b$ is such that $\Xbuf_i$ is a degree-$b$ buffer, we have

\begin{equation}\label{psr:Vsum:deseq}
\big|\{x\in\Xbuf_i:v,v'\in C(x)\}\big|\le 24\mu\Delta^2\big(20\mu^{-1}\zeta^{-1}d^{-\Delta}\big)^b p^{2b}|X_i|\,.
\end{equation}

To prove this we show that for each $x\in\Xbuf_i$, however previous vertices are embedded, it is not too likely that $N_H(x)$ is embedded to $\comN_\Gamma(v,v')$, and apply Lemma <ref> and the union bound to deduce (<ref>) for all $i$, $v$, and $v'$. In turn, to prove the desired upper bound on the probability of embedding $N_H(x)$ to $\comN_\Gamma(v,v')$, we analyse the embedding of the vertices $N_H(x)=\{y_1,\dots,y_b\}$ one by one. We would expect that in each case roughly a $p^2$-fraction of $U(y_i)$ is contained in $\comN_\Gamma(v,v')$, and if this is the case at each step we obtain the desired upper bound. If not, the reason is that a previously embedded vertex—which must be one of the $y_j$ since we have not yet embedded any other neighbouring vertices—was `badly embedded'. Using the $\LNS$ property, we show this is an unlikely event and again obtain the desired upper bound. In fact, this is a slight oversimplification: we have to separate the cases that exactly one vertex is embedded badly (which implies we still have only at worst a probability $p$ of embedding future vertices of $N_H(x)$ to $\comN_\Gamma(v,v')$) or that more than one vertex is embedded badly, in which case we might have probability $1$ of embedding future vertices of $N_H(x)$ to $\comN_\Gamma(v,v')$, but this is counterbalanced by the unlikelihood of embedding two vertices badly.

We require

\[\eps\le\min\big( 2^{-\Delta},\tfrac{\mu\zeta d^\Delta}{10\Delta\kappa}\big)\quad\text{and}\quad p\ge 20\mu^{-1}\kappa r_1\big(\tfrac{\log n}{n}\big)^{1/(2\Delta)}\,.\]

Let $v,v'\in V_i$ be such that $\deg_\Gamma(v,v';V_j)\le (p+\eps p)^2|V_j|$ for each $j$ such that $ij\in R'$. Suppose that $\Xbuf_i$ is a degree-$b$ buffer and $b\in[\Delta]$.

Since any two vertices of $\Xbuf_i$ are at distance at least ten in $H$ by <ref>, it is enough to show for any one vertex $x\in\Xbuf_i$, by considering the embedding of $N_H(x)$, that the probability of $v,v'\in C(x)$, conditioning on the history up to but not including the embedding of $N_H(x)$, is at most $3\Delta^2\big(20\mu^{-1}\zeta^{-1}d^{-\Delta}\big)^bp^{2b}$. If we show this, then, since the vertices of $N_H(x)$ are embedded consecutively, by Lemma <ref>, applied with $\delta=1$ and using $|\Xbuf_i|=4\mu|X_i|$, we see that (<ref>) holds with probability at least $1-\exp\big(-4\mu\Delta^2\big(20\mu^{-1}\zeta^{-1}d^{-\Delta}\big)^bp^{2b}|X_i|\big)$, and taking a union bound over the at most $n^2$ choices of $v,v'$ we conclude that by choice of $p$ the conclusion of the claim a.a.s. holds as desired.

We show that the probability of $v,v'\in C(x)$ is at most $3\Delta^2\big(20\mu^{-1}\zeta^{-1}d^{-\Delta}\big)^bp^{2b}$, conditioning on any $\psi_T$ where $T=\tau(x)-|N_H(x)|-1$ is the time immediately before the first vertex of $N_H(x)$ is embedded. Observe that $v,v'\in C(x)$ can occur only if $N_H(x)$ is embedded into $\comN_{\Gamma}(v,v')$. If $y\in N_H(x)\cap X_j$, then the probability that $y$ is embedded into $\comN_\Gamma(v,v')$ is, using <ref>, at most

\[\frac{\big|U_{\tau(y)-1}(y)\cap \comN_\Gamma(v,v')\big|}{\tfrac{1}{10}\mu\zeta(dp)^{\pitau(y)}|V_j|}\,.\]

Thus, we would like to show that the numerator is at most $(p+\eps p)^{2+\pitau(y)}|V(y)|$ for all  $y\in N_H(x)$, since
by multiplying conditional probabilities $10\mu^{-1}\zeta^{-1}(p+\eps p)^{2}$ we would obtain the desired upper bound. Of course, this does not always happen, since it may be the case that a neighbour $z$ of $y$ in $H$ with $\tau(z)<\tau(y)$ was embedded `badly', that is, to a vertex with more than

\begin{equation}\label{eq:badly_embed}
(p+\eps p)\left|U_{\tau(z)-1}(y)\cap \comN_\Gamma(v,v')\right|
\end{equation}

neighbours in $U_{\tau(z)-1}(y)\cap \comN_\Gamma(v,v')$.
Because $\tau$ satisfies Lemma <ref><ref>, any such $z$ is in $N(\Xbuf)$. Since $x$ is at distance at most $2$ from $z$ in $H$, and at distance at least $5$ from any other vertex of $\Xbuf$ by <ref>, we see that $z\in N_H(x)$. Thus, if exactly $s$ many neighbours $z$ of $y$ with $\tau(z)<\tau(y)$ are embedded badly then
we see that with (<ref>) the following inequality

\begin{equation}\label{eq:s_bad_vcs}
\big|U_{\tau(y)-1}(y)\cap \comN_\Gamma(v,v')\big|\le (p+\eps p)^{\pitau(y)-s}|\comN_\Gamma(v,v')|\le (p+\eps p)^{\pitau(y)+2-s}|V(y)|
\end{equation}

holds.   We separate in what follows three cases.

First, no vertices in $N_H(x)$ are embedded badly. Then the probability that all $b$ vertices in $N_H(x)$ are embedded into $\comN_\Gamma(v,v')$, conditioning on $\psi_T$, is at most $\big(20\mu^{-1}\zeta^{-1}d^{-\Delta}p^2\big)^b$ by choice of $\eps$.

Second, exactly one vertex in $N_H(x)$ is embedded badly. We let the vertices of $N_H(x)$ be $y_1,\ldots,y_b$ in order of $\tau$. Let us suppose that $y_\ell$ is the vertex embedded badly. Then the probability that the first $\ell-1$ vertices of $N_H(x)$ are embedded into $\comN_\Gamma(v,v')$, conditioning on $\psi_T$, is at most $\big(20\mu^{-1}\zeta^{-1}d^{-\Delta}p^2\big)^{\ell-1}$ by choice of $\eps$ (since these are not  badly embedded and conditional probabilities multiply).

We now estimate the probability of $y_\ell$ being embedded badly, conditioning on $\psi_T$ and on the embeddings of the previous $\ell-1$ vertices not being bad. Observe that, since there has been no previous bad embedding,  we have for each $\ell'>\ell$

\[
\big|U_{\tau(y_\ell)-1}(y_{\ell'})\cap \comN_\Gamma(v,v')\big|\le(p+\eps p)^{\pi_{\tau(y_\ell)-1}(y_{\ell'})+2}|V(y_{\ell'})|\,,
\]

and since $\pi_{\tau(y_\ell)-1}(y_{\ell'})\le\ell-1\le\Delta-2$, the right hand side is, by choice of $\eps$, at least $\eps p^{\Delta}n/r_1$. By $\LNS(\eps,r_1,\Delta)$ the number of vertices in $\Gamma$ with more than
$(p+\eps p)^{\pi_{\tau(y_\ell)-1}(y_{\ell'})+3}|V(y_{\ell'})|$ neighbours into $U_{\tau(y_\ell)-1}(y_{\ell'})\cap \comN_\Gamma(v,v')$
is at most $\eps p^{2\Delta-1}n/r_1$. Since $\pitau(y_\ell)\le\ell-1$, by <ref> the probability that $y_\ell$ is embedded to such a bad vertex is at most

\[
\frac{\Delta\eps p^{2\Delta-1}n/r_1}{\mu\zeta(dp)^{\ell-1}|V(y_\ell)|/10}\le p^{2\Delta-\ell}
\]

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

Finally, the probability that the last $b-\ell$ vertices are embedded into $\comN_\Gamma(v,v')$, conditioning on the previous embeddings, is at most $\big(20\mu^{-1}\zeta^{-1}d^{-\Delta}p\big)^{b-\ell}$ by choice of $\eps$. Indeed,
for each vertex $\ell'>\ell$ we have by (<ref>) that

\[
\big|U_{\tau(y_{\ell'})-1}(y_{\ell'})\cap \comN_\Gamma(v,v')\big|\le (p+\eps p)^{\pitau(y_{\ell'})+1}|V(y_{\ell'})|
\]

since we condition on  exactly one neighbour of $y_{\ell'}$ being embedded badly. This gives the conditional probability at most $20\mu^{-1}\zeta^{-1}d^{-\Delta}p$.   The conditional probabilities multiply, and taking the union bound over the choices of $\ell$, we see that the probability of this case occurring and all vertices of $N_H(x)$ being embedded to $\comN_\Gamma(v,v')$, conditioning on $\psi_T$, is at most

\begin{multline*}
\Delta\cdot\big(20\mu^{-1}\zeta^{-1}d^{-\Delta}p^2\big)^{\ell-1}\cdot p^{2\Delta-\ell}\cdot
\big(20\mu^{-1}\zeta^{-1}d^{-\Delta}p\big)^{b-\ell}
\le\\ \Delta\big(20\mu^{-1}\zeta^{-1}d^{-\Delta}\big)^{b-1}p^{2\Delta+b-2}\le \Delta^2\big(20\mu^{-1}\zeta^{-1}d^{-\Delta}\big)^bp^{2b},
\end{multline*}

where the last inequality follows since $\Delta\ge 2$ and $b\le\Delta$.

In the third case, at least two vertices in $N_H(x)$ are embedded badly. Suppose that the first two badly embedded vertices are the $j$th and $k$th vertices. Then the same logic as above, in particular the inequality (<ref>),  tells us that the probability that this case occurs and all vertices of $N_H(x)$ are embedded to $\comN_\Gamma(v,v')$ is at most

\begin{multline*}
\Delta^2\cdot \big(20\mu^{-1}\zeta^{-1}d^{-\Delta}p^2\big)^{j-1}\cdot
p^{2\Delta-j}\cdot \big(20\mu^{-1}\zeta^{-1}d^{-\Delta}p\big)^{k-j-1}\cdot p^{2\Delta-k}\le
\\
\Delta^2\big(20\mu^{-1}\zeta^{-1}d^{-\Delta}\big)^{b-2}p^{4\Delta-3}.
\end{multline*}

Putting these three cases together, and using the fact that $4\Delta-3\ge 2b$ since $\Delta\ge 2$ and $b\le\Delta$, we conclude that the probability that $v,v'\in C(x)$ is at most $3\Delta^2\big(20\mu^{-1}\zeta^{-1}d^{-\Delta}\big)^bp^{2b}$ as desired.

Suppose now that the good event of Claim <ref> holds. For each $i\in[r]$, there may be `exceptional' vertices $v\in V_i$ which have more than $(p+\eps p)|V_j|$ neighbours in $V_j$ for some $j$ such that $ij\in R'$, but by $\NS(\eps,r_1,\Delta+1)$ there are at most $\DeltaRp\eps p^\Delta n/r_1\le\eps'p^\Delta|V_i|$ such vertices. If $v$ is not exceptional—that is, it has at most $(p+\eps)|V_j|$ neighbours in each $V_j$ with $ij\in R'$—then again there may be `exceptional' vertices $v'\in V_i$ such that $v'$ has more than $(p+\eps p)^2|V_j|$ common neighbours with $v$ in $V_j$ for some $j$ such that $ij\in R'$, but again by $\NS(\eps,r_1,\Delta+1)$ there are at most $\DeltaRp\eps p^\Delta n/r_1\le\eps'p^\Delta|V_i|$ such. Because the good event of Claim <ref> holds, for non-exceptional pairs of vertices $v,v'$ we have the bound given in <ref>. Because the good event of Claim <ref> holds a.a.s., property <ref> is a.a.s. obtained. This completes the proof of Lemma <ref>.

CHAPTER: IMPROVED BOUNDS FOR DEGENERATE GRAPHS

§ THE RGA LEMMA AND THE PROOF OF THE BLOW-UP LEMMA

In this section we prove Lemma <ref>. We have already seen most of the ideas in the proofs of Lemmas <ref> and <ref>. We use the same General Setup, and we continue to obtain it using Lemma <ref>. However, rather than defining an order $\tau$ putting the buffer vertices $\Xbuf$ at the end and their neighbours at the front, as we did in the proofs of Lemmas <ref> and <ref>, we are supplied with an order $\tau$ which we will modify only in that we move $\Xbuf$ to the end of the order. In particular, the neighbours of buffer vertices need not appear early in $\tau$. The reason for this is that moving vertices in the order could result in substantially increasing $\pitau(x)$ for some vertices $x$. It is easy to check that moving $\Xbuf$ to the end of the order only increases $\pitau(x)$ for $x\in\Xbuf$, thus preserves conditions <ref>–<ref> for non-buffer vertices.

We will use a modification of Algorithm <ref> to perform this embedding. The modification consists of handling the exceptional vertices $X^e$ differently, which allows us to deal with a few vertices $x$ with $\pitau(x)$ significantly larger than normal; such vertices appear in applications. We can show that this algorithm succeeds in embedding all the vertices of $\Xmain$, in the order $\tau$, and that it returns a good partial embedding with the properties detailed in the lemma below with positive probability. Since we will have $\Xmain=V(H)\setminus \Xbuf$, we can complete the proof using Lemma <ref> to embed the buffer vertices in much the same way as in the proof of Lemma <ref>.

Note that property $\LCON$ which appears in the following lemma plays the same rôle as $\LNS$ in the proof of Lemma <ref>. It is easier to work with, and allows for linearly many image restrictions (but it is not in general true in bijumbled graphs).

We assume the General Setup. Suppose that an (exceptional) set $X^e$ with $|X^e|\le\tfrac12\eps p^{\max_{x\in X^e}\pitau(x)}n/r_1$ is given. Suppose that $D\ge 1$, and $\tau$ is a $\big(D,p,\tfrac12\eps n/r_1\big)$-bounded order for $H$, $\tcX$, $\cI$ and $\cJ$ with this exceptional set $X^e$. Suppose furthermore that the vertices $\Xbuf$ form the final segment of $\tau$. Suppose that $\Gamma$ has  properties $\NS(\eps,r_1,D)$, $\RI(\eps,(\eps_{a,b}),\eps',d,r_1,D)$ and $\LCON(\eps,r_1,D)$. Then there is a good partial embedding $\psiRGA$ of $H$ into $G$ with the following
properties for each $i\in[r]$. Let $b$ be such that $\Xbuf_i$ is a degree-$b$

*  Every vertex in
$\Xmain_i$ is embedded to
$\Vmain_i\cup \Vq_i\cup \Vc_i$ by $\psiRGA$, and no vertex in $\Xbuf_i$ is embedded.

*  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$.

*  Every vertex in $V_i$ is a
candidate for at least
\[4^{-10\Delta^3} 2^{-1000D^2\mu^{-1}\zeta^{-1}d^{-D}} d^{2D^2} \Delta^{-3}\mu p^b|X_i|\]

vertices of $\Xbuf_i$.

We will prove this lemma in Section <ref>. Assuming Lemma <ref>, we are in a position to prove Lemma <ref>. This amounts to a verification that the conditions of Lemma <ref> suffice to apply Lemmas <ref>, <ref>, <ref> and <ref>.

First we choose constants as follows. Given $\Delta$, $\DeltaRpbl$, $\Delta_J$ and $D$ 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

\begin{multline*}
\mu=\tfrac{\alpha}{20000\kappa\DeltaRp^4\Delta^{10}(\Delta+2)}\,,\quad\rho= \tfrac{\mu^2\zeta^2d^{3D^2}}{10000\kappa(\Delta+1)}4^{-2000\Delta^3\mu^{-1}\zeta^{-1}d^{-D}}\\
\text{and}\quad\eps'= \tfrac{\mu\zeta d^{\Delta+1}}{1000\Delta^4\kappa4^\Delta}2^{-280(D+1)\mu^{-1}\zeta^{-1}d^{-D}}\,.\\
\end{multline*}

Now for input $D$ and $d,\eps'$, Lemma <ref> returns constants $(\eps_{a,b})$ and $\eps_{\sublem{det_gnp:randri}}>0$. We set

\[\eps=\min\big(\eps_{\sublem{det_gnp:randri}},\tfrac{d\eps'}{\kappa}\big)\,.\]

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 $D$, $d$, $\eps'$, $r_1$ and $\rho$, and such that

\[C\ge\tfrac{10^8\cdot 4^{10\Delta^3}(\Delta+\Delta_J)^4\kappa r_1^2}{\eps^2\mu\zeta d^{\Delta+1}}2^{280(D+1)\mu^{-1}\zeta^{-1}d^{-D}}\,.\]

Given $p\ge C\big(\tfrac{\log n}{n}\big)^{1/D}$, Lemma <ref> (items <ref>, <ref>, <ref> and <ref>) states that a.a.s. $\Gamma=G(n,p)$ has the properties $\NS\big(\eps,r_1,D\big)$, $\RI\big(\eps,(\eps_{a,b}),\eps',d,r_1,D\big)$, $\CON(\rho,r_1,D)$ and $\LCON\big(\eps,r_1,D\big)$ respectively. From now on we will assume $\Gamma$ is an $n$-vertex graph which satisfies these four 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$, a family of potential buffer vertices $\tcXbl$, and an exceptional set $X^e$, suppose that the conditions of Lemma <ref> are satisfied. Then Lemma <ref> gives 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.

We now modify the provided order $\taubl$ on $V(H)$ by moving the set $\Xbuf$ to the end of the order, obtaining a new order $\tau$. Since $\epsbl n/\ronebl=\tfrac12\eps n/r_1$, the order $\tau$, which is
$(D,p,\epsbl n/\ronebl)$-bounded for $H$, $\tcXbl$, $\cIbl$ and $\cJ$ with the exceptional set $X^e$ of size at most $\epsbl p^{\max_{x\in X^e}\pitau(x)}n/\ronebl=\tfrac12\eps p^{\max_{x\in X^e}\pitau(x)}n/r_1$, is also  $\big(D,p,\tfrac12\eps n/r_1\big)$-bounded for $H$, $\tcX$, $\cI$ and $\cJ$.

We let $\Xmain=V(H)\setminus\Xbuf$. We now begin the embedding of $H$ into $G$.
By Lemma <ref>, there is a good partial embedding $\psiRGA$ with the properties stated in that lemma.
By <ref>, condition <ref> of Lemma <ref> is satisfied, while
condition <ref> holds by <ref> and <ref> follows from <ref>  with

\[\delta=4^{-10\Delta^3} 2^{-1000D^2\mu^{-1}\zeta^{-1}d^{-D}} d^{2D^2} \Delta^{-3}\mu\,.\]

Therefore, we can find  an embedding $\psi'$ extending $\psiRGA$ which embeds $\Xbuf_i$ to $V_i\setminus\im(\psiRGA)$. Repeating this for each $i\in[r]$, which we may do since $\Xbuf$ is an independent set in $H$, we obtain the desired embedding of $H$ into $G$.

§ PROOF OF THE DEGENERATE GRAPH RGA LEMMA

We prove Lemma <ref> by analysing Algorithm <ref>. The analysis is quite similar to what we saw before in the proofs of Lemmas <ref> and <ref> (indeed, the main difference is that we are more careful to bound powers of $p$ using $D$ rather than just $\Delta$), so we will be brief and highlight the differences. The only difference between Algorithm <ref> and Algorithm <ref> is that vertices of $X^e$ are embedded into $\Vc$ rather than $\Vmain$ or $\Vq$.

Random greedy algorithm for degenerate graphs
$G\subseteq \Gamma$ and $H$ with partitions satisfying the General Setup; an ordering $\tau$ on $\Xmain$
$Q_0:=\{x\in V(H):|I_x|<\tfrac12\mu(d-\eps)^{|J_x|}p^{|J_x|}|\Vmain(x)|\}$
let $x\in \Xmain\setminus \dom(\psi_t)$ be the next vertex in
the order $\tau$
$x\in Q_t\setminus X^e$ and $|\Aq_t(x)\setminus B_t(x)|<\tfrac{1}{10}\mu\zeta(dp)^{\pi^*_t(x)}|V(x)|$halt with failure
$x\in Q_t\cap X^e$ and $|\Ac_t(x)\setminus B_t(x)|<\tfrac{1}{10}\mu\zeta(dp)^{\pi^*_t(x)}|V(x)|$halt with failure
choose $v$ uniformly at random in $\begin{cases}
\Amain_t(x)\setminus B_t(x) \quad & \text{if $x\not\in (Q_t\cup X^e)$} \\
\Aq_t(x)\setminus B_t(x) & \text{if $x\in Q_t\setminus X^e$} \\
\Ac_t(x)\setminus B_t(x) & \text{if $x\in X^e$}
\end{cases}$
$\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)|)$

We will see that <ref> (see Definition <ref>
of $(D,p,m)$-bounded order) is precisely what we need to make
Lemma <ref> work with properties $\NS(\eps,r_1,D)$ and
$\RI(\eps,(\eps_{a,b}),\eps',d,r_1,D)$, so allowing us to prove that
$B_t(x)$ is always much smaller than $A_t(x)$. As in the proof of
Lemma <ref>, our first task is to show that the algorithm
a.a.s. completes successfully. Again by
Lemma <ref> we can show that the queue remains
small. We can also show, using <ref>, that all vertices
$x\in X_i\setminus X^e$ which enter the queue have
$\pitau(x)\le D/2$. We embed the vertices of $X^e\cap X_i$ which
enter the queue greedily into $\Vc_i$, and there are so few such
vertices that this is guaranteed to succeed.  Property
$\LCON(\eps,r_1,D)$ turns out to be what we need to verify that the
queue embedding of the remaining vertices a.a.s. is successful,
using the same strategy as in the proof of Lemma <ref>.

At this stage we have <ref> simply because the
algorithm completes, while <ref> follows from
Lemma <ref>. It remains to
prove <ref>, which is where we need to
use <ref>. Here we deviate from the strategy we saw
previously. We can no longer assume that neighbours of buffer
vertices appear early in $\tau$, and thus we have to prove that for
any $v\in V(G)$, even towards the end of the embedding, it is still
reasonably likely that neighbours of buffer vertices are embedded to
$N_G(v)$. We will see (Claim <ref> below) that
properties $\NS(\eps,r_1,D)$, $\RI(\eps,(\eps_{a,b}),\eps',d,r_1,D)$
and $\LCON(\eps,r_1,D)$ allow us to show that a.a.s. given any
$\ell\le D-\max_{x\in\Xmain\setminus X^e}\pitau(x)$ vertices
$v_1,\ldots,v_\ell$ of $G$ such that
$\comN_G(v_1,\ldots,v_\ell;\Vmain_i)$ is not small, the set
$\comN_G(v_1,\ldots,v_\ell;\Vmain_i)$ is never completely filled by
$\im(\psi_t)$. The idea of the proof remains similar to that of
Lemma <ref>. We show, as there, that when the first
small fraction of the vertices in the order $\tau$ are embedded, only
at most half of $\comN_G(v_1,\ldots,v_\ell;\Vmain_i)$ is covered. But
then we repeat this, showing that the next small fraction of $\tau$
covers only at most half of what remains, and so on, so that when all
vertices are embedded what remains is an exponentially small, but
bounded away from zero, fraction of the original
$\comN_G(v_1,\ldots,v_\ell;\Vmain_i)$. Once we have shown this,
completing the proof that $N_H(x)$ is not too unlikely to be embedded
to $N_G(v)$ for any $x\in\Xbuf$ and $v\in V(x)$ can be done along
similar lines to the proof of Lemma <ref>.

We require

\begin{align*}
\mu\le\tfrac{1}{8}\,,\,\, \rho\le \frac{\mu^2\zeta^2d^{2D}}{10000(\Delta+1)}\,,\,\, \eps'\le \frac{\mu\zeta d^{\Delta+1}}{1000\Delta^2\kappa4^\Delta}2^{-280(D+1)\mu^{-1}\zeta^{-1}d^{-D}}\,,\,\, \eps\le\tfrac{d\eps'}{\kappa}\\
\text{and}\quad p\ge \tfrac{10000\cdot 4^{10\Delta^3}\Delta^3\kappa r_1^2}{\eps\mu\zeta d^{\Delta+1}}2^{280(D+1)\mu^{-1}\zeta^{-1}d^{-D}}\big(\tfrac{\log n}{n}\big)^{1/D}\,.
\end{align*}

We run Algorithm <ref>, using the order $\tau$ supplied to Lemma <ref>. We claim that we can apply Lemma <ref> to bound $B_{\tau(x)-1}(x)$. To see this, we consider three cases.

If $x$ has no neighbours after $\tau(x)$ in $\tau$, then Lemma <ref> states that $B_{\tau(x)-1}(x)=\emptyset$ without requiring any property of $\Gamma$.

If $x$ has a neighbour $y$ with $\tau(x)<\tau(y)$, then <ref> states that $\pitau(x)\le D-1$, so in particular $\pi^*_{\tau(x)-1}(x)\le D-1$, satisfying <ref>. Furthermore, <ref> states that $\pitau(y)\le D$, so $\pi^*_{\tau(x)-1}(y)\le D-1$ since $x$ is not embedded, satisfying <ref>.

Now suppose that $xy,yz\in E(H)$ for some unembedded $y$ and $z$. There are two cases to consider. First, if $\tau(y)<\tau(z)$ then <ref> states that $\pitau(y)\le D-1$ and $\pitau(z)\le D$. Since $x$ and $y$ are unembedded at time ${\tau(x)-1}$, we thus have $\pi^*_{\tau(x)-1}(y)\le D-2$ and $\pi^*_{\tau(x)-1}(z)\le D-1$, as required by <ref>. Second, if $\tau(y)>\tau(z)$, then $\pi^*_{\tau(x)-1}(z)\le\pitau(z)\le D-1$ by <ref>, while since $\pitau(y)\le D$ and both the vertices $x$ and $z$ are unembedded, we have $\pi^*_{\tau(x)-1}(y)\le D-2$, again as required by <ref>.

Lastly, if there are unembedded vertices $y$ and $z$ such that $xy,yz,xz$ are all edges of $H$, then we claim $\pi_{\tau(x)-1}^*(x),\pi_{\tau(x)-1}^*(y),\pi_{\tau(x)-1}^*(z)\le D-2$. To see this, suppose $\tau(y)<\tau(z)$. By <ref> we have $\pitau(x)\le D-2$, $\pitau(y)\le D-1$ and $\pitau(z)\le D$. Since $x$ and $y$ are unembedded, we have $\pi^*_{\tau(x)-1}(y)\le D-1-1=D-2$, and $\pi^*_{\tau(x)-1}(z)\le D-2$. Thus condition <ref> is satisfied.

We conclude that $\big|B_{\tau(x)-1}(x)\big|\le 20\Delta^2\eps' p^{\pitau(x)}|V(x)|$ for each $x\in\Xmain$.

As before, the first task is to show that certain invariants are maintained. These are identical to the invariants seen in the previous two RGA lemmas, but are repeated here for the reader's convenience.

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

*  $\psi_t$ is a good partial embedding,

*  Either $|\Amain_t(x)|\ge\frac12\mu(d-\eps')^{\pi^*_t(x)}p^{\pi^*_t(x)}|\Vmain(x)|$
or $x\in Q_t$.

*  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)|$.

Algorithm <ref> maintains <ref> and <ref> by definition. Since $\tfrac12\mu(d-\eps')^{\pitau(x)}p^{\pitau(x)}-20\Delta^2\eps'p^{\pitau(x)}>\tfrac{1}{10}\mu\zeta d^{\pitau(x)}p^{\pitau(x)}$ by choice of $\eps'$ for each $x\in\Xmain$, by Lemma <ref> it also maintains <ref>.

As in the previous proofs, the conditions of Lemma <ref> are met, so we conclude that with probability at least $1-2^{-n/(\kappa r_1)}$, for each $i\in[r]$ and time $t$ when Algorithm <ref> is running, we have $\big|Q_t\cap X_i\big|<\rho|X_i|+|X^*_i|\le 2\rho|X_i|$ by <ref>.

We now want to show that Algorithm <ref> a.a.s. does not halt with failure. Since we know that $\big|B_{\tau(x)-1}(x)\big|<20\Delta^2\eps' p^{\pitau(x)}|V(x)|$, by <ref> and <ref> it is enough to show that a.a.s. we have

\begin{align*}
\big|\Aq_{\tau(x)-1}(x)\big|&\ge\tfrac12\big|\Cq_{\tau(x)-1}(x)\big|\quad\text{ for }\quad x\in\Xmain\cap Q_{\tau(x)-1}\setminus X^e\,,\quad\text{ and}\\
\big|\Ac_{\tau(x)-1}(x)\big|&\ge\tfrac12\big|\Cc_{\tau(x)-1}(x)\big|\quad\text{ for }\quad x\in \Xmain\cap Q_{\tau(x)-1}\cap X^e\,.
\end{align*}

The latter of these is easy, since we embed only vertices of $X^e$ into $\Vc$, and $|X^e|\le \tfrac12\eps p^{\max_{x\in X^e}\pitau(x)}n/r_1$, which by <ref> and choice of $\eps$ is smaller than $\tfrac12\big|\Cc_{\tau(x)-1}(x)\big|$. We now establish the former inequality.

First, we show that we need only concern ourselves with $x$ such that $\pitau(x)\le D/2$.

For each $x\in\Xmain\setminus X^e$, if $\pitau(x)>D/2$ then there is no time $t$ such that $x\in Q_t$.

We require $\eps'\le \tfrac14d^D\mu$ and $\eps\le\kappa^{-1}\eps'$.

Suppose $\pitau(x)>D/2$ and $x\not\in X^e$. Let $i$ be such that $x\in X_i$. By <ref>, $x$ is not image restricted, and all $\pitau(x)$ neighbours of $x$ which precede $x$ in $\tau$ occur in the
$\tfrac12\eps p^{\pitau(x)} n/r_1\le \eps'p^{\pitau(x)}|X_i|$ places of $\tau$ before $x$. Because $x$ is not image restricted, at time $t\le\tau(x)-\eps'p^{\pitau(x)}|X_i|$ we have $\Cmain_{t}(x)=\Vmain_i$, and hence $\Amain_{t}(x)=\Vmain_i\setminus\im(\psi_{t})$. Because $|\Xmain_i|=|\Vmain_i|-\mu|V_i|$, it follows that $|\Amain_{t}(x)|\ge \mu|V_i|$, and in particular $x$ does not enter $Q_{t}$ at time $t$.

Now suppose $t=\tau(x)-\eps'p^{\pitau(x)}|X_i|+s$ for some $0\le s\le \eps'p^{\pitau(x)}|X_i|-1$. We claim that

\[|\Amain_t(x)|\ge (dp-\eps'p)^{\pi^*_{t}(x)}\mu|V_i|-s\,.\]

Indeed, for $s=0$ we have $\pi^*_t(x)=0$ and the statement $|\Amain_t(x)\ge\mu|V_i|$ was established above. Now suppose the statement holds for some $s\ge 0$. At time $t=\tau(x)-\eps'p^{\pitau(x)}|X_i|+s$ we embed a vertex $y$ to obtain $\psi_{t+1}$. If $y$ is neither a neighbour of $x$ nor in $X_i$, then $\Amain_t(x)=\Amain_{t+1}(x)$ and the statement holds for $s+1$. If $y$ is a neighbour of $x$, then we embed $y$ to a vertex of $A_t(y)\setminus B_t(y)$, and in particular to a vertex $v$ such that $\deg_G\big(v;\Amain_t(x)\big)\ge(d-\eps')p|\Amain_t(x)|$. We conclude that

\[|\Amain_{t+1}(x)|\ge (d-\eps')p\big((dp-\eps'p)^{\pi^*_{t}(x)}\mu|V_i|-s\big)> (dp-\eps'p)^{\pi^*_{t+1}(x)}\mu|V_i|-s-1\,.\]

as desired. Finally, if $y\in X_i$ then we have $\Amain_{t+1}(x)=\Amain_t(x)\setminus\{y\}$, and again

\[|\Amain_{t+1}(x)|\ge (dp-\eps'p)^{\pi^*_{t+1}(x)}\mu|V_i|-s-1\,.\]

Thus for each $\tau(x)-\eps'p^{\pitau(x)}|X_i|\le t\le\tau(x)-1$ we have

\[|\Amain_{t}(x)|\ge (dp-\eps'p)^{\pi^*_{t}(x)}\mu|V_i|-\eps'p^{\pitau(x)}|X_i|\ge\tfrac12(dp-\eps'p)^{\pi^*_{t}(x)}\mu|V_i|\,,\]

where the final inequality is by choice of $\eps'$. It follows that $x$ does not satisfy the condition to enter $Q_t$. Since we embed $x$ at time $\tau(x)-1$, we conclude that as desired there is no time $t$ such that $x\in Q_t$.

As in the proof of Lemma <ref> the next step is to establish a `sum condition'. In fact, we establish almost the same inequality as (<ref>) in Claim <ref> (the right hand side is identical, while the left hand side sum runs over all vertices outside $X^e$, including those $y$ with $J_y\neq\emptyset$), though we use a different analysis to do so.

Suppose that $\Gamma$ has $\LCON(\eps,r_1,D)$. Then the following statement holds.

For any $t$, any $1\le \ell \le D/2$, any $i\in[r]$ and any vertices $v_1,\ldots,v_\ell$ such that

\[\deg_\Gamma(v_1,\ldots,v_\ell;V_i)\ge\eps'p^\ell|V_i|\]

we have

\begin{equation}\label{eq:sumVqLCON}
\sum_{\substack{y\in\Xmain_i\cap Q_t\setminus X^e\colon\\ \tau(y)\le t}}\hspace{-1em} \frac{\big|U_{\tau(y)-1}(y)\cap \comN_\Gamma(v_1,\ldots,v_\ell;V_i)\big|}{\big|\Aq_{\tau(y)-1}(y)\setminus B_{\tau(y)-1}(y)\big|}\le\frac{\mu\zeta d^\Delta \deg_\Gamma(v_1,\ldots,v_\ell;V_i)}{20}\,.
\end{equation}

The proof of this amounts to checking that the images under our embedding of the $N_H(y)$ for $y\in\Xmain_i\cap Q_t\setminus X^e$ form a family of sets to which we can apply the $\LCON$ property. This property gives us the desired inequality.

We require $\rho\le \tfrac{\mu^2\zeta^2 d^{D+\Delta}}{10000(\Delta+1)}$, $\eps'\le \mu\zeta(d/4)^D$ and $\eps\le\tfrac{\eps'}{\kappa}$. Since the left hand side of (<ref>) is increasing in $t$, we may assume $t$ is the time at which Algorithm <ref> ends.

Given $1\le\ell\le D/2$ and $i\in[r]$, let $v_1,\ldots,v_\ell$ be vertices such that $U:=\comN_\Gamma(v_1,\ldots,v_\ell;V_i)$ has size at least $\eps'p^\ell|V_i|$. By choice of $\eps$ and $\eps'$, we have $|U|\ge\eps p^\ell n/r_1$. It follows that we can apply $\LCON(\eps,r_1,D)$ to bound the number of edges in $\AG(\Gamma,U,\mathcal{F})$ for any $1\le j\le D/2$ and family $\cF$ of pairwise disjoint $j$-sets in $V(\Gamma)\setminus U$. We set

\[\mathcal{F}_j:=\big\{\Pi_{\tau(x)-1}(x)\cup J_x:x\in \Xmain_i\cap Q_t\setminus X^e, \pitau(x)=j,\tau(x)\le t\big\}\,.\]

Observe that $\mathcal{F}_j$ is indeed a family of $j$-sets by definition of $\pitau(x)$, that these $j$-sets are pairwise disjoint because no vertex of $H$ has more than one neighbour in $X_i$ by <ref>, and element $F$ of $\cF_j$ intersects  $U\subset V_i$ because these sets $F$ are images  under $\psi$ of neighbours of vertices in $X_i$. Because $\eps|U|,|\Xmain_i\cap Q_t|\le 2\rho|X_i|$, by choice of $\eps$ and by $\LCON(\eps,r_1,D)$ we have

\[e\big(\AG(\Gamma,U,\mathcal{F}_j)\big)\le 7p^j |U|(2\rho |X_i|)=14\rho p^j |U| |X_i|\,.\]

By definition of $U_t(x)$ (see Section <ref>) we have the following equality

\[e\big(\AG(\Gamma,U,\mathcal{F}_j)\big)=\sum_{x\in\Xmain_i\cap Q_t\setminus X^e:\pitau(x)=j,\tau(x)\le t} |U_{\tau(x)-1}(x)\cap U|\]

and hence

\[\sum_{x\in\Xmain_i\cap Q_t\setminus X^e:\pitau(x)=j,\tau(x)\le t}|U_{\tau(x)-1}(x)\cap U|\le 14\rho p^j|U||X_i|\]

for each $1\le j\le D/2$. Observe that the $j=0$ case of the same inequality is trivially true (indeed with $14$ replaced by $2$, though we will not use this): each vertex of $\Xmain_i\cap Q_t$ contributes at most $|U|$ to the sum. Now by <ref> we have

\[
\big|\Aq_{\tau(x)}(x)\setminus B_{\tau(x)}(x)\big|\ge\tfrac{1}{10}\mu\zeta(dp)^{\pitau(x)}|V_i|\]

for each $x\in\Xmain_i\cap Q_t$ with $\tau(x)\le t$. Finally, since any vertex $x$ in $\Xmain_i\cap Q_t$ satisfies
$\pitau(x)\le D/2$ by Claim <ref>, we conclude that

\begin{align*}
\sum_{\substack{x\in\Xmain_i\cap Q_t\setminus X^e:\\ \tau(x)\le t}}\frac{|\Uq_{\tau(x)}(x)\cap U|}{|\Aq_{\tau(x)}(x)\setminus B_{\tau(x)}(x)\big|}&\le \sum_{j=0}^{D/2}\sum_{\substack{x\in\Xmain_i\cap Q_t\setminus X^e:\\
\pitau(x)=j,\tau(x)\le t}}\frac{14\rho p^j|U||X_i|}{\tfrac{1}{10}\mu\zeta(dp)^{\pitau(x)}|V_i|}
\\ &\le\frac{14(1+D/2)\rho|U||X_i|}{\tfrac{1}{10}\mu\zeta d^{D/2}|V_i|}\le \tfrac{\mu\zeta d^\Delta}{20}|U|,
\end{align*}

where the final inequality is by choice of $\rho$, as desired.

Now we have
A.a.s. for each $x\in\Xmain\setminus X^e$, at each time $t\le\tau(x)-1$ and before the termination of Algorithm <ref>, we have $\big|\Cq_t(x)\cap\im(\psi_t)\big|<\tfrac12\big|\Cq_t(x)\big|$.

The proof of Claim <ref>, if we  replace $\Xmain$ with $\Xmain\setminus X^e$, and replace (<ref>) with (<ref>), without handling image restricted vertices specially (since  condition (<ref>) deals with them), gives this claim verbatim.

As in the proof of Lemma <ref>, the conclusion of Claim <ref> holds a.a.s., which implies that Algorithm <ref> completes successfully. Again, the successful running implies <ref>, and the good event of Lemma <ref> holding implies <ref>.

We would like to emphasise at this point that we have established all
the desired conclusions of Lemma <ref>
except <ref>, and we have so far not used
condition <ref>, and not used the second part of <ref>
(which states $\pitau(x)\le D_x-1$ for $x\in N(\tX)$ ). It follows
that one can establish a version of Lemma <ref>
omitting <ref> given an order $\tau$ which need only
satisfy the first part of <ref> (which states
$\pitau(x)\le D_x$ for all $x\in V(H)$ ) and <ref>. We will
return to this point in Section <ref>.

We now turn to proving <ref>. First, we show that $G$-common neighbourhoods of at most $D-\max_{x\in\Xmain\setminus X^e}\pitau(x)$
vertices which are large do not get completely filled at any time in the running of Algorithm <ref>. Note that the strange-looking number of vertices whose $G$-neighbourhoods we control comes from <ref>. When we use this condition, we will want to control a $G$-common neighbourhood of a vertex $v\in V_i$ (which we eventually want to show is likely to be candidate for many vertices of $\Xbuf$) together with the embedded images of some neighbours of a vertex $x\in N(\Xbuf)$. What this condition says is that we have the desired control for all the neighbours of $x$ which are embedded before $\tau(x)-\tfrac12\eps p^Dn/r_1$; we will see that neighbours embedded after this time can be dealt with easily.
This lemma replaces Lemma <ref> which we used in the proofs of the previous two RGA lemmas.

Suppose that $\Gamma$ has $\LCON(\eps,r_1,D)$. Then a.a.s. the following holds at each time $t$. Given any $i\in[r]$, any $1\le \ell\le D-\max_{x\in\Xmain\setminus X^e}\pitau(x)$, and any vertices $v_1,\ldots,v_{\ell}$ of $G$, the following hold. If $\deg_G(v_1,\ldots,v_\ell;\Vmain_i)\ge (dp/2)^\ell|\Vmain_i|$, then

\begin{equation}\label{eq:degenrga:bufnofill}\begin{split}
\big|\comN_G(v_1,\ldots,v_\ell;\Vmain_i)&\setminus\im(\psi_t)\big|\ge\\
(1-4\mu)&2^{-280(D+1)\mu^{-1}\zeta^{-1} d^{-D}}\deg_G(v_1,\ldots,v_\ell;\Vmain_i)\,.
\end{split}\end{equation}

If $\deg_G(v_1,\ldots,v_\ell;\Vq_i)\ge (dp/2)^\ell|\Vq_i|$, then

\begin{equation}\label{eq:degenrga:queuenofill}
\big|\comN_G(v_1,\ldots,v_\ell;\Vq_i)\setminus\im(\psi_t)\big|\ge\tfrac12\deg_G(v_1,\ldots,v_\ell;\Vq_i)\,.
\end{equation}

The proof of (<ref>), as discussed at the beginning of this section, roughly amounts to repeating the argument of Lemma <ref> several times. We show that, for some small constant $\eta$, each successive interval consisting of an $\eta$-fraction of the vertices $\Xmain_i$ is likely to cover less than half of whatever of $\comN_G(v_1,\dots,V_\ell;\Vmain_i)$ was uncovered before embedding that interval. The argument for each given interval is morally similar to that seen in Lemma <ref>, though here we take a short-cut by using property $\LCON$ rather than $\NS$, which simplifies the calculations.

Let $h=\max_{x\in\Xmain\setminus X^e}\pitau(x)$.
We require

\begin{align*}
\mu&\le\tfrac18\,,\quad &\rho&\le\frac{\mu^2\zeta d^D}{1000(D+1)}\,,\\
\eps&<\tfrac12 2^{-280(D+1)\mu^{-1}\zeta^{-1} d^{-D}}\big(\tfrac{d}{2}\big)^{D+1}\quad\text{and}\quad &p&\ge \tfrac{1000\Delta^2}{\eps\mu\zeta d^D}\big(\tfrac{\log n}{n}\big)^{1/D}\,.
\end{align*}

We first prove inequality (<ref>). Set $\eta=\frac{\mu\zeta d^D}{280(D+1)}$.
Given $i\in[r]$ and $1\le\ell\le D-h$, suppose that $v_1,\ldots,v_\ell\in V(\Gamma)$ are such that $\comN_G(v_1,\ldots,v_\ell;\Vmain_i)\ge(dp/2)^\ell|\Vmain_i|$. We split the vertices of $\Xmain_i\setminus X^e$ into intervals $\Int_1,\ldots,\Int_{1/\eta}$ of equal size, with the first being the first $\eta |\Xmain_i\setminus X^e|$ vertices in the order $\tau$, and so on.

We now aim to show that for any fixed set $U\subseteq V_i$ of size at least $\eps p^\ell |V_i|$ and any $1\le j\le 1/\eta$, conditioning on the embedding up to the last vertex of $\Int_{j-1}$, with high probability at most $\tfrac12|U|$ vertices of $\Int_j$ are embedded to $U$. To that end, for each $x\in\Int_j$ let $\hist_{x,j}$ denote the history up to but not including the embedding of $x$. By definition of $h$, all vertices $x\in\Int_j$ have $\pitau(x)\le h$, so we split the vertices $x$ of $\Int_j$ up into $h+1$ classes according to $\pitau(x)$. We apply $\LCON(\eps,r_1,D)$ with the set $U$ and the family $\cF_s$ of $s$-sets given by the embedded images of $N_H(x)$ for $x\in\Int_j$ with $\pitau(x)=s$. Since $\eps|U|,|\cF_s|\le\eta|\Xmain_i|$, we  obtain the inequality

\[\sum_{x\in\Int_j:\pitau(x)=s}\big|U_{\tau(x)-1}(x)\cap U\big|
\le 7p^s |U| \eta |\Xmain_i|\,.\]

Now each $x\in\Int_j$ with $\pitau(x)=s$ is by <ref> embedded uniformly at random into a set of size at least $\tfrac{1}{10}\mu\zeta(dp)^s|V_i|$. We thus have

\[\sum_{x\in\Int_j}\Pr\big(x\text{ is embedded to }U\big|\hist_{x,j}\big)
\le (h+1)\frac{70\eta |U|}{\mu\zeta d^{h}}\le(D+1)\frac{70\eta |U|}{\mu\zeta d^{D}}\]

and by Lemma <ref> with $\delta=1$ we see that the probability that more than

\[140(D+1)\eta\mu^{-1}\zeta^{-1}d^{-D}|U|\le\tfrac12|U|\]

of the vertices in $\Int_j$ are embedded to $U$ is at most

\[\exp\left(-(D+1)\tfrac{70\eta |U|}{3\mu\zeta d^D}\right)\le n^{-D-1}\,,\]

where the inequality is because $|U|\ge \eps p^{D-h}|V_i|$ and by choice of $p$. This is what we wanted to show about $U$, and we will now proceed to use it for various choices of $U$.

Let $U_0=\comN_G(v_1,\ldots,v_\ell;\Vmain_i)$, and $U_j=U_{j-1}\setminus\psi_{t_{j+1}}(\Int_j)$ for each $j\ge 1$. In the event that $|U_j|\ge\tfrac12|U_{j-1}|$ for each $j$, we have

\[|U_j|\ge 2^{-1/\eta}(d/2)^\ell p^\ell |\Vmain_i|\ge\eps p^\ell |V_i|\]

for each $j$, where the final inequality is by choice of $\eps$. In other words, each $U_{j-1}$ is large enough for the above probabilistic calculation to be valid, so taking a union bound over the $1/\eta$ choices of $j$, we see that with probability at least $1-\eta^{-1}n^{-D-1}$ we have

\[\big|\comN_G(v_1,\ldots,v_\ell;\Vmain_i)\setminus\im(\psi_{t_j})\big|\ge(1-4\mu)2^{1-j}\deg_G(v_1,\ldots,v_\ell;\Vmain_i)\]

for each $1\le j\le 1/\eta+1$. Taking a union bound over the at most $r_1$ choices of $i\in[r]$ and $n+n^2+\dots+n^{D}$ choices of $v_1,\ldots,v_\ell$ we see that the desired event of the lemma holds with probability at least $1-r_1D\eta^{-1}n^{-1}$, which tends to one as $n$ tends to infinity.

The proof of (<ref>) is simpler. Observe that $|\Xq_i|\le2\rho|X_i|<\eta|\Xmain_i|$, and $\deg_G(v_1,\ldots,v_\ell;\Vq_i)\ge(dp/2)^\ell|\Vq_i|\ge\eps p^\ell |V_i|$ so that the analysis above, with only one `interval' $\Xq_i\setminus X^e$, gives the desired result.

Finally, we are in a position to prove <ref>, which we do in the following claim. The proof is quite similar to that of Lemma <ref>, which amounts to show that any vertex $v\in V_i$ is likely to be a candidate vertex for `reasonably' many of the buffer vertices $\Xbuf_i$. More precisely, our strategy is to fix a vertex $v\in V_i$ and show that the inequality (<ref>) below, which encapsulates these reasonable bounds, holds with sufficiently high probability to apply the union bound over all $v\in V(G)$.
To do this, we introduce the concept of an $(x\to v)$-buffer partial embedding for $x\in\Xbuf_i$. As in the proof of Lemma <ref>, this is a good partial embedding which has a few extra properties that let us show that it is not too unlikely that $N_H(x)$ is embedded to $N_G(v)$. As there, the proof that it is not too unlikely that at each step Algorithm <ref> maintains an $(x\to v)$-buffer partial embedding is mainly `bookkeeping' and long but not very hard. However, there is an important difference. It is no longer useful to simply multiply the conditional probabilities of maintaining an $(x\to v)$-buffer partial embedding in order to estimate the conditional probability that $N_H(x)$ is embedded to $N_G(v)$. This is because the vertices $N_H(x)$ are no longer embedded as a segment of $\tau$, so that Lemma <ref> is not applicable directly to these products of conditional probabilities. Nevertheless we show below that we can still apply Lemma <ref>, several times and with some extra care, to obtain the desired bounds.

The following holds a.a.s. for each $i\in[r]$. Let $b$ be such that $\Xbuf_i$ is a degree-$b$ buffer. Then for each $v\in V_i$ we have

\begin{equation}\label{eq:rga:bufdeg}
\big|\{x\in\Xbuf_i:v\in C_{t_\RGend}(x)\}\big|\ge 4^{-10\Delta^3}2^{-1000D^2\mu^{-1}\zeta^{-1}d^{-D}} d^{2D^2} \Delta^{-3}\mu p^b|X_i|\,.
\end{equation}

We require

\begin{align*}
&\mu\le\tfrac18\,,\quad &\eps'&<\tfrac{\mu\zeta d^\Delta}{1000\Delta^2\kappa4^\Delta}\cdot 2^{-280(D+1)\mu^{-1}\zeta^{-1}d^{-D}}\,,\qquad\eps\le\eps'\,,\\
&\text{and}\quad &p&>10000\cdot 4^{10\Delta^3}\Delta^3\kappa r_1\mu^{-1}d^{-\Delta-1}\cdot 2^{280(D+1)\mu^{-1}\zeta^{-1}d^{-D}}\big(\tfrac{\log n}{n}\big)^{1/D}\,.
\end{align*}

Let $\beta=(1-4\mu)2^{-280(D+1)\mu^{-1}\zeta^{-1}d^{-D}}$. It is convenient to consider only vertices of $\Xbuf_i$ which are far from $X^e$; since $X^e$ is very small, doing so does not exclude many vertices of $\Xbuf_i$.

Given $x\in\Xbuf_i$ which is at distance greater than three from any vertex of $X^e$, and $v\in V_i$, we say that a good partial embedding $\psi$ is an $(x\to v)$-buffer partial embedding if the following hold.

*  For each $y\in\dom(\psi)\cap N_H(x)$ we have $\psi(y)\in N_G(v)$.

*  For each unembedded $y\in N_H(x)$ we have

\begin{align*}
U(y)\cap N_\Gamma(v)&=(p\pm\eps'p)^{\pi^*(y)}\deg_\Gamma\big(v;V(y)\big)\,,\\
\Umain(y)\cap N_\Gamma(v)&=(p\pm\eps'p)^{\pi^*(y)}\deg_\Gamma\big(v;\Vmain(y)\big)\quad\text{and}\\
\Uq(y)\cap N_\Gamma(v)&=(p\pm\eps'p)^{\pi^*(y)}\deg_\Gamma\big(v;\Vq(y)\big)
\end{align*}

*  For each unembedded $y\in N_H(x)$ we have

\begin{align*}
\Cq(y)\cap N_G(v)&\ge(dp-\eps'p)^{\pi^*(y)}\deg_G\big(v;\Vq(y)\big)\quad\text{and}\\
\Cmain(y)\cap N_G(v)&\ge (dp-\eps'p)^{\pi^*(y)}\deg_G\big(v;\Vmain(y)\big)
\end{align*}

*  For each unembedded $y,z\in N_H(x)$ with $yz\in E(H)$, the pair $\big(U(y)\cap N_\Gamma(v),U(z)\cap N_\Gamma(v)\big)$ is $(\eps_{\pi^*(y),\pi^*(z)},d,p)$-regular in $G$.

*  For each unembedded $y\in N_H(x)$ and $z\in N_H(y)$, the pair $\big(U(y)\cap N_\Gamma(v),U(z)\big)$ is $(\eps_{\pi^*(y),\pi^*(z)},d,p)$-regular in $G$.

Much as in the proof of Lemma <ref>, the empty partial embedding $\psi_0$ is an $(x\to v)$-buffer partial embedding. Indeed, <ref>–<ref> are trivially true since by <ref> neighbours of buffer vertices are not image restricted. For <ref> and <ref>, since buffer vertices are by <ref> at distance at least three from image restricted vertices the sets $U(y)$ and $U(z)$ are equal to $V(y)$ and $V(z)$ respectively, and the required regularity is thus given by <ref>, since $\Xbuf_i\subset\tX_i$.

Given an $(x\to v)$-buffer partial embedding $\psi$ and an unembedded vertex $y$, we let $P(y)$ be the set of poor vertices for $y$, namely those vertices $u\in C(y)$ such that either $\psi\cup\{y\to u\}$ is not an $(x\to v)$-buffer partial embedding, or such that there is an unembedded $z\in N_H(y)\cap N_H(x)$ such that either of the following conditions hold:

\begin{equation}\label{eq:BPE_Py}
\begin{split}
\deg_G\big(u;\Amain(z)\cap N_G(v)\big)\le&(d-\eps')p\big|\Amain(z)\cap N_G(v)\big| \quad\text{or}\\
\deg_G\big(u;\Aq(z)\cap N_G(v)\big)\le&(d-\eps')p\big|\Aq(z)\cap N_G(v)\big|\,.
\end{split}
\end{equation}

Observe that if $y$ is at distance four or greater from $x$ in $H$, then $P(y)$ is always empty. This has two important consequences. First, we are about to talk about the probability of no vertices being embedded to poor vertices: this is really a condition on at most $3\Delta^3$ vertex embeddings. Second, it means that if $x,x'\in\Xbuf_i$, by <ref> the distance between $x$ and $x'$ is at least ten, so that any given vertex embedding affects at most one of whether we have an $(x\to v)$-buffer partial embedding or an $(x'\to v)$-buffer partial embedding.

Before we try to estimate the probability of maintaining an $(x\to v)$-buffer partial embedding, we strengthen the conclusion of Claim <ref> to cover the `last few vertices' before embedding $y\in N_H(x)$.

For a given $x\in\Xbuf_i$ at distance greater than three from $X^e$ and a fixed $v\in V(x)$, provided that up to time $t$ no vertex has been embedded to a poor vertex (with respect to an $(x\to v)$-buffer partial embedding), for each $y\in N_H(x)$ with $\tau(y)>t$, the following a.a.s. hold.

\begin{equation}\label{eq:degen:sizeAs}
\begin{split}
\big|\Amain_t(y)\cap N_G(v)\big|&\ge\tfrac\beta2(dp/2)^{\pi^*_t(y)}\deg_G\big(v;\Vmain(y)\big)\quad\text{and}\\
\big|\Aq_t(y)\cap N_G(v)\big|&\ge\tfrac14(dp/2)^{\pi^*_t(y)}\deg_G\big(v;\Vq(y)\big)\,.
\end{split}
\end{equation}

We will see that Claim <ref>, together with <ref>, show that this fact holds provided $t\le\tau(y)-\tfrac12\eps p^D n/r_1$. The number of vertices embedded in the remaining $\tfrac12\eps p^D n/r_1$ is too small to significantly fill up either of these sets, so we need only show that embedding neighbours of $y$ does not adversely affect (<ref>). This is guaranteed by condition (<ref>) in the definition of poor vertices.

Let $h=\max_{z\in\Xmain\setminus X^e}\pitau(z)$.
Since $\Xbuf_i\subseteq \tX$ and $y\in N_H(x)$ we infer by <ref> that all
but at most $s$ neighbours $z$ of $y$
satisfy $\tau(y)-\tau(z)\le p^D \cdot\tfrac12\eps n/r_1$ for some $s\le D-1-h$
(recall that $\tau$ is a $(D,p,\tfrac12\eps n/r_1)$-bounded order).
Therefore, if $t\le \tau(y)-\tfrac12\eps p^{D} n/r_1$ then  $\pi^*_t(y)\le s\le  D-1-h$,
so that $\Pi^*_t(y)\cup\{v\}$ is by <ref>, <ref> and <ref> a set of $s+1\le D-h$ vertices in $G$ with at least $(dp/2)^{s+1}|\Vq(y)|$ common neighbours in $\Vq(y)$ and at least $(dp/2)^{s+1}|\Vmain(y)|$ common neighbours in $\Vmain(y)$.

Therefore, by Claim <ref>, we have

\begin{align*}
\big|\Amain_t(y)\cap N_G(v)\big|&\ge\beta(dp/2)^{\pi^*_t(y)}\deg_G\big(v;\Vmain(y)\big)\quad\text{and}\\
\big|\Aq_t(y)\cap N_G(v)\big|&\ge\tfrac12(dp/2)^{\pi^*_t(y)}\deg_G\big(v;\Vq(y)\big)\,,
\end{align*}

which gives (<ref>) for this range of $t$. Now suppose that

\[
t=\tau(y)-\eps p^{D} \cdot\tfrac12 n/r_1+\ell
\]

for some $0\le \ell<\tfrac12\eps p^{D} n/r_1$. We claim that

\begin{equation}\label{eq:nosmall}\begin{split}
\big|\Amain_t(y)\cap N_G(v)\big|&\ge\beta(dp/2)^{\pi^*_t(y)}\deg_G\big(v;\Vmain(y)\big)-\ell\quad\text{and}\\
\big|\Aq_t(y)\cap N_G(v)\big|&\ge\tfrac12(dp/2)^{\pi^*_t(y)}\deg_G\big(v;\Vq(y)\big)-\ell\,.
\end{split}\end{equation}

Indeed, we have just established that (<ref>) holds for $\ell=0$. Given $\ell\ge 1$, suppose that (<ref>) holds for $\ell-1$, and consider the vertex $z$ embedded at time $\tau(z)=\tau(y)-\eps p^{D} \cdot\tfrac12 n/r_1+\ell$.

If $z$ is not a neighbour of $y$, then its embedding decreases either of the sets on the left hand side of (<ref>) by at most one, so the inequality continues to hold. If $z$ is a neighbour of $y$, then by (<ref>) in the definition of $P(z)$ we have

\begin{align*}
\big|\Aq_{\tau(z)}(y)\cap N_G(v)\big|&\ge(d-\eps')p\big|\Aq_{\tau(z)-1}(y)\cap N_G(v)\big|\\
\end{align*}

where the second inequality is by choice of $\eps'$ and (<ref>). A similar inequality holds for $\big|\Amain_{\tau(z)}(y)\cap N_G(v)\big|$. Thus again (<ref>) continues to hold. We conclude that (<ref>) holds for all $0\le \ell<\tfrac12\eps p^{D} n/r_1$.

Now since $x\in\Xbuf$, we have $\tau(x)>\tau(y)$, so that by <ref> we have $\pi^*_t(y)\le\pitau(y)\le D-1$. By <ref> and choice of $\eps$, we conclude that (<ref>) holds for all $t<\tau(y)$ as desired.

We now continue with the proof of Claim <ref> by estimating the probability of not choosing a poor vertex at a given step in Algorithm <ref>.

Suppose that $\psi$ is a good partial embedding generated together with a queue set $Q$ by Algorithm <ref> which is also an $(x\to v)$-buffer partial embedding, where $x$ is at distance greater than three from any vertex of $X^e$, and (<ref>) holds for $\psi$ and all unembedded $y$. Given an unembedded $y$, suppose that $u$ is a vertex chosen uniformly at random in $\Amain(y)\setminus B(y)$ (if $y\not\in Q\cup X^e$), in $\Aq(y)\setminus B(y)$ (if $y\in Q\setminus X^e$) or in $\Ac(y)\setminus B(y)$ (if $y\in X^e$).
Then the following hold.

* If $\dist_H(x,y)>3$ then $\Pr\big(u\not\in P(y)\big)=1$,

* If $\dist_H(x,y)\in\{2,3\}$ then $\Pr\big(u\not\in P(y)\big)\ge\tfrac12$, and

* If $\dist_H(x,y)=1$ then $\Pr\big(u\not\in P(y)\big)\ge \beta d^{D-1} 4^{-D}p$.

The proof of this fact is quite similar to the analysis in Lemma <ref>. Note that the use we make of $\psi$ and $Q$ being generated by Algorithm <ref> is that the invariants of Claim <ref> hold; we do not in the following proof perform any analysis of the probabilistic process generating $\psi$ and $Q$.

If $\dist_H(x,y)>3$ then $P(y)=\emptyset$ and the claim is trivial.

By <ref> we embed $y$ uniformly at random into a set whose size is at least $\tfrac{1}{10}\mu\zeta(dp)^{\pitau(y)}|V(y)|$. Thus in order to show the second item we simply need to establish that $P(y)\cup B(y)$ is small compared to this set; this can be established using $\NS(\eps,r_1,D)$, $\RI(\eps,(\eps_{a,b}),\eps',d,r_1,D)$ and the buffer and good partial embedding properties, as in the proof of Lemma <ref>. Note that to do this we need to use the fact, given by <ref>, that $\pitau(z)\le D_z-1$ for each $z\in N(\tX)$, in other words that $\pitau(z)\le D-2$ for all $z\in N_H(x)$ and $\pitau(z)\le D-3$ if there is a triangle $zww'$ in $H$ with $\tau(w),\tau(w')>\tau(z)$. Note further that in order to establish that few vertices fail (<ref>), we need to know that $\Amain(z)\cap N_G(v)$ and $\Aq(z)\cap N_G(v)$ are not small in comparison to $U(z)\cap N_\Gamma(v)$. This follows from (<ref>) since $z\in N_H(x)$.

Finally, we embed $y$ uniformly at random into a subset of $U(y)$, which by <ref> has size at most $2p^{\pitau(y)}|V(y)|$. If $xy\in H$, we need to show that it is not too unlikely that $y$ is embedded to $N_G(v)$. By (<ref>), <ref> and choice of $\beta$, we see that

\[\big|\Amain(y)\cap N_G(v)\big|,\big|\Aq(y)\cap N_G(v)\big|\ge\tfrac{\beta}{4}(dp/2)^{\pitau(y)}|V(y)|\,.\]

It is thus enough to show that at most half of these vertices are in $P(y)\cup B(y)$, which again we can do using $\NS(\eps,r_1,D)$, $\RI(\eps,(\eps_{a,b}),\eps',d,r_1,D)$ and the buffer and good partial embedding properties, as in the proof of Lemma <ref>. Again, we use the fact $\pitau(z)\le D_z-1$ for $z\in N_H(x)$ in this verification.

We now continue with the proof of Claim <ref>. We fix $i$ and $v\in V_i$. We have established that for any given vertex $x$ of $\Xbuf_i$ far from $X^e$, the probability that $N_H(x)$ is embedded to $N_G(v)$ is not too small. Furthermore, this probability is more or less given by the embeddings of vertices at distance at most three from $x$: and distinct vertices of $\Xbuf_i$ are at distance at least ten by <ref>, so that no vertex is within distance three of two distinct $x,x'\in\Xbuf_i$. It should not be surprising that this is enough to show that indeed with very high probability a reasonable fraction of the $x\in\Xbuf_i$ have $N_H(x)$ embedded to $N_G(v)$: this is what we ultimately want. However, because the sets $N_H(x)$ interleave each other in the order $\tau$, we cannot simply apply Lemma <ref>. We now embark on taking the `extra care' mentioned before the Claim to complete the proof.

For each $x\in\Xbuf_i$, let $M_x$ be the set of vertices of $H$ at distance one, two or three from $x$. We say $x$ survives at step $j$ if after the embedding of the $j$th vertex of $M_x$ in the order $\tau$, we still have an $(x\to v)$-buffer partial embedding. We will use Lemma <ref> to show that a reasonable fraction of $x\in\Xbuf_i$ survive at step $1$. We would like then to use Lemma <ref> again to show that (because a reasonable fraction of vertices survive at step $1$) a reasonable fraction of vertices survive at step $2$, and so on.

In order to carry this out, it is convenient not in fact to look at all $x\in\Xbuf_i$, but only at a subset $Y$ in which the probability of surviving at each step $j$ (as given by Claim <ref>) does not depend on the particular vertex in $Y$ but only on $j$. We now construct such a set $Y$. For any $x\in\Xbuf_i$ at distance greater than three from $X^e$, there are at most $\Delta^3+\Delta^2+\Delta<3\Delta^3$ vertices of $H$ at distance at most $3$ from $x$ in $H$. We can therefore associate to each $x\in\Xbuf_i$ at distance greater than three from $X^e$ a $0$–$1$ vector of length at most $3\Delta^3$, taking the value $0$ at place $j$ if the $j$th vertex $y$ of $M_x$ (in the order $\tau$) is not a neighbour of $x$, and $1$ if $y$ is a neighbour of $x$. There are at most $3\Delta^3 2^{3\Delta^3}$ choices for this vector; we fix a most common choice $\mathbf{c}=(c_i)$ of length $|\mathbf{c}|$, and let $Y$ be the subset of vertices of $\Xbuf_i$ at distance at least three from $X^e$ associated to this most common choice. By construction, by <ref>, by choice of $\eps$ and since $|X^e|\le\tfrac12\eps p^D n/r_1$ and $|X_i|\ge n/\kappa r_1$, we have

\begin{equation}\label{eq:degen:sizeY}
|Y|\ge\tfrac16 \Delta^{-3} 2^{-3\Delta^3}|\Xbuf_i|\,.
\end{equation}

For each $x\in Y$ and $1\le j\le|\mathbf{c}|$, let $\hist_{x,j}$ be the history of Algorithm <ref> up to the point immediately before embedding the $j$th vertex of $M_x$. For each $x\in Y$, we create a collection of Bernoulli random variables $A_{x,1}$ for $x\in Y$, which are set equal to one if either $x$ survives at step $1$ or (<ref>) has failed before embedding the first element of $M_x$, and zero otherwise. These random variables have a natural order given by the order $\tau$ on the first elements (in $\tau$) of the $M_x$ for $x\in Y$, and they are in this order sequentially dependent. We define

\[s_1=\begin{cases}\tfrac12\beta d^{D+1}4^{-D}p|Y| & \text{if}\quad c_1=1\\ \tfrac14|Y| &\text{if}\quad c_1=0\end{cases}\,.\]

Now for each $A_{x,1}$, either Fact <ref> gives us a lower bound on $\Exp[A_{x,1}|\hist_{x,1}]$, or (<ref>) has failed before we embed the first vertex of $M_x$, in which case $\Exp[A_{x,1}|\hist_{x,1}]=1$. We conclude, by definition of $s_1$, that

\[\sum_{x\in Y}\Exp[A_{x,1}|\hist_{x,1}]\ge 2s_1\,.\]

Thus we can use Lemma <ref>, with $\delta=1/4$, to show that with very high probability we have $\sum_{x\in Y}A_{x,1}\ge s_1+1$ (We will fill in the missing quantitative details later). We denote this good event by $\cA_1$. Observe that if (<ref>) does not fail for any $y$ or $t$ (which is a.a.s. the case) then $\cA_1$ holding says that at least $s_1+1$ vertices survive at step $1$.

There remains a small technical difficulty in continuing the programme outlined above. We would like to count vertices surviving at step $2$, and use Lemma <ref> and a lower bound on the sum of conditional expectations given by the product of $s_1$ and the probability bound from Fact <ref> to show that the result is likely to be large. But it is possible that less than $s_1$ vertices survive at step $1$, so that this bound on the sum of conditional expectations does not hold almost surely (it only holds with very high probability).

To get around this problem, we use the following trick. We say $x$ is dangerous at step $1$ if the following holds. Immediately after embedding the first vertex of $M_x$ in Algorithm <ref>, the number of vertices  $x'$ in $Y$ such that $A_{x,1}$ is certainly equal to one (i.e. such that the first vertex of $M_{x'}$ was embedded to a vertex which is neither poor nor bad, so $x'$ survives at step $1$), plus the number of vertices $x'$ in $Y$ such that the first vertex of $M_{x'}$ has not yet been embedded, is at most $s_1$. In other words, we say $x$ is dangerous at step $1$ if after embedding the first vertex of $M_x$ we already know that $\cA_1$ does not occur.

We now define Bernoulli random variables $A_{x,2}$ for $x\in Y$, set equal to one if either $x$ survives at step $2$, or $x$ is dangerous at step $1$, or (<ref>) has failed for some $y$ prior to embedding the second vertex of $M_x$, and zero otherwise. The point of this definition is that it gives us an a priori lower bound on the sum of conditional expectations of the $A_{x,2}$, as we require to apply Lemma <ref>, but nevertheless with very high probability the sum of the $A_{x,2}$ does simply count the number of vertices in $Y$ which survive at step $2$, because with very high probability (<ref>) does not fail and $\cA_1$ does occur, so no vertex is dangerous at step $1$. Again, this collection of random variables has a natural order given by the order $\tau$ on the second vertices of the $M_x$, and again in this order the random variables are sequentially dependent. Note that (as required for this last to be true) we do know whether $x$ is dangerous at step $1$ before we embed the second vertex of $M_x$. This justifies that we can apply Lemma <ref> to estimate the sum of the $A_{x,2}$.

We now complete this programme. We need to give integers $s_j$ for $2\le j\le |\mathbf{c}|$, which are our desired lower bounds on the number of vertices in $Y$ surviving at step $j$, to define the events $\cA_j$ and the concept of dangerous at step $j$ for $j\ge 2$, and define the random variables $A_{x,j}$ for $3\le j\le\mathbf{|c|}$. We also need to say explicitly what `very high probability' is in our applications of Lemma <ref>.

For each $2\le j\le|\mathbf{c}|$, we set

\[
s_j=\begin{cases}\tfrac12\beta d^{D+1}4^{-D}ps_{j-1} & \text{if}\quad c_j=1\\ \tfrac14s_{j-1} &\text{if}\quad c_j=0\end{cases}\,.
\]

We let the event $\sum_{x\in Y}A_{x,j}\ge s_j+1$ be $\cA_j$. We say $x\in Y$ is dangerous at step $j$ if immediately after embedding the $j$th vertex of $M_x$, the number of $x'\in Y$ such that $A_{x',j}$ is certainly equal to one, plus the number of $x'\in Y$ such that the $j$th vertex of $M_{x'}$ has not yet been embedded, is at most $s_j$. Again, this means that after embedding the $j$th vertex of $M_x$, we already know $\cA_j$ does not occur. Finally, for each $j\ge 3$ we define the Bernoulli random variables $A_{x,j}$ for $x\in Y$, set equal to one if $x$ survives at step $j$, or is dangerous at step $j-1$, or (<ref>) has failed before embedding the $j$th vertex of $M_x$, and zero otherwise.

Before we continue, we observe that

\begin{equation}\label{eq:degen:lowsc}
s_1\ge s_2\ge\dots\ge s_{|\mathbf{c}|}\ge \big(\tfrac14\big)^{\Delta^2+\Delta^3}\big(\tfrac12\beta d^{D+1}4^{-D}p\big)^b|Y|
\end{equation}

where $b$ is the degree of the buffer $\Xbuf_i$, i.e. $\deg_H(x)=b$ for each $x\in\Xbuf_i$; this number exists by <ref>. The reason is simply that there are at most $\Delta^2+\Delta^3$ vertices of $H$ at distance two or three in $H$ from any given $x\in Y$, and $b$ neighbours of $x$. In particular, by choice of $p$, by our lower bound on $|Y|$ and since $n$ is sufficiently large, we have $3s_j/2>s_j+1$ for each $1\le j\le|\mathbf{c}|$.

We now show that with very high probability $\cA_j$ occurs for each $1\le j\le|\mathbf{c}|$. Recall that by Fact <ref>, we have the lower bound $\sum_{x\in Y}\Exp[A_{x,1}|\hist_{x,1}]\ge 2s_1$. By Lemma <ref> with $\delta=1/4$, and the observation $3s_1/2>s_1+1$, the probability that $\cA_1$ fails is thus at most $e^{-s_1/24}$.

Now for $j\ge 2$, for each $x\in Y$, either $x$ survived at step $j-1$ and (<ref>) has not failed before embedding the $j$th vertex of $M_x$, in which case the expectation of $A_{x,j}$ conditioned on $\hist_{x,j}$ is at least the quantity given in Fact <ref>, or $x$ was dangerous at step $j-1$ or (<ref>) failed before embedding the $j$th vertex of $M_x$, in which case we have $\Exp[A_{x,h}|\hist_{x,j}]=1$, or none of these occur, in which case we have $\Exp[A_{x,h}|\hist_{x,j}]\ge 0$. Furthermore, by definition of the $A_{x,j}$ we know (a priori, before beginning the embedding) that one of the first three cases occurs for at least $s_{j-1}$ of the vertices $Y$, so that we have $\sum_{x\in Y}\Exp[A_{x,j}|\hist_{x,j}]\ge 2s_j$ by definition of $s_j$. Applying Lemma <ref>, with $\delta=1/4$, and since $3s_j/2>s_j+1$, we conclude that the probability that $\cA_j$ fails is at most $e^{-s_j/24}$.

By definition, if (<ref>) never fails and each event $\cA_1,\dots,\cA_{|\mathbf{c}|}$ occurs, then no vertex is dangerous at any step. Thus the number of vertices of $Y$ surviving at step $|\mathbf{c}|$ is at least $s_{|\mathbf{c}|}$. By definition, if $x$ survives at step $|\mathbf{c}|$ then $N_H(x)$ is embedded to $N_G(v)$, so that $v$ is a candidate for $x$. Since $s_{|\mathbf{c}|}$ is by (<ref>), (<ref>) and <ref> at least

\[ \big(\tfrac14\big)^{\Delta^2+\Delta^3}\big(\tfrac12\beta d^{D+1}4^{-D}p\big)^b\cdot \tfrac16 \Delta^{-3} 2^{-3\Delta^3}\cdot 4\mu|X_i|\]

we conclude that (<ref>) holds for $v$, as desired.
The probability that any given one of the events $\cA_1,\dots,\cA_{|\mathbf{c}|}$ fails is at most $e^{-s_{|\mathbf{c}|}/24}<n^{-D-1}$ by (<ref>), (<ref>), <ref>, since $|X_i|\ge n/\kappa r_1$ and by choice of $p$. Taking the union bound over the at most $3\Delta^3$ events $\cA_j$, and the at most $n$ choices of $v$, and since a.a.s. (<ref>) never fails by Fact <ref>, we conclude that a.a.s. (<ref>) holds for all $v\in V_i$ for each $i\in [r]$, completing the proof of Claim <ref>.

The good event of Claim <ref> holding gives <ref>. Since a.a.s. the good events of each of the above claims and lemmas hold, this completes the proof of Lemma <ref>.

CHAPTER: PROOFS OF APPLICATIONS

In this chapter we prove the various theorems listed in Section <ref>. Where a stronger result is proved elsewhere, we only sketch the proofs.

§ UNIVERSAL GRAPHS

We begin by showing that $G(n,p)$ is universal for spanning bounded-degree graphs with degeneracy $d$ when $p\ge C\big(\tfrac{\log n}{n}\big)^{1/(2d+1)}$.

We first show <ref>.
Observe that any $d$-degenerate $n$-vertex graph has at most $dn$ edges
and so contains at least $\tfrac{n}{2d+1}$ vertices of degree at most
$2d$. We will apply Lemma <ref> with input $\Delta$, with
$\DeltaRp=8\Delta$, $D=2d+1$, $\alpha=\tfrac{\gamma}{10d}$, $\zeta=1$,
density $\tfrac12$, and $\kappa=2$. Lemma <ref> returns
$\eps>0$, and for input $r_1=8\Delta$ also $C$. Choose $\eps^*\ll\eps$
and suppose $C$ is also large enough for
Lemma <ref><ref> with input $\eps^*$,
$8\Delta$ and $2$. Let $p\ge C\big(\tfrac{\log
n}{n}\big)^{1/(2d+1)}$. Fix an equipartition $V_1,\ldots,V_{8\Delta}$
of $[n]$. Now $G(n,p)$ a.a.s. satisfies the good event of
Lemma <ref>. By Lemma <ref><ref>
it a.a.s. has property $\NS(\eps^*,8\Delta,D)$. Finally, using
Theorem <ref> and the union bound it is easy to check that
a.a.s. for each $i$ and $v\in V_i$, the vertex $v$ has
$(1\pm\eps)p|V_j|$ neighbours in $V_j$ for each $j\neq i$. Fix a graph
$\Gamma$ with each of these properties. Property
$\NS(\eps^*,8\Delta,D)$ implies that any pair of disjoint subsets of
$V(\Gamma)$, each of size at least $\tfrac{p n}{16\Delta}$, is
$(\eps,\tfrac12,p)$-regular, so letting $R=R'=K_{8\Delta}$ we have an
$(\eps,\tfrac12,p)$-regular $R$-partition which has super-regularity
and one- and two-sided inheritance on $R'$.

Given $H$ on $n$ vertices with degeneracy $d$ and maximum degree
$\Delta$, let $X_1,\ldots,X_{8\Delta}$ be an equipartition of $V(H)$
into independent sets, with each $X_i$ containing at least
$\tfrac{1}{8\Delta(2d+1)}|X_i|$ vertices of degree at most $2d$. This
equipartition exists by Lemma <ref>. We designate the
vertices of degree at most $2d$ as potential buffer vertices. We do not
image restrict any vertices. Then (perhaps after reordering) the $X_i$
form an $R$-partition of $V(H)$ which is size-compatible with the
$V_i$. We let $\tau$ be a degeneracy order on $V(H)$. We move all
buffer vertices to the end of the ordering $\tau$. Observe that this
slightly changed ordering satisfies
conditions <ref>–<ref> and thus is
$(D,p,\eps^*n/r_1)$-bounded.  Then the conditions of
Lemma <ref> are satisfied, so $H\subseteq\Gamma$ as desired.

To obtain <ref>, we work identically except that we add to each part of $V(H)$ isolated vertices to obtain a size-compatible $R$-partition, and we designate these isolated vertices as potential buffer vertices instead of the low-degree vertices in $H$. Then Lemma <ref>, applied with $D=2d$, $p=C(\frac{\log n}{n})^{1/D}$ and all other parameters staying as before, gives the desired conclusion.

It is quite easy to use Lemma <ref> to show that sufficiently pseudorandom graphs are universal for bounded-degree graphs.

Given $G$, we take a random equipartition of $V(G)$ into $\Delta+1$ clusters $V_1,\ldots,V_{\Delta+1}$. For each $v\in V(G)$ and $i$, the quantity $\deg(v;V_i)$ is hypergeometrically distributed with mean at least $\tfrac14p|V_i|$, so by Theorem <ref> and the union bound we see that with positive probability we have $\deg(v;V_i)\ge\tfrac18p|V_i|$ for each $v$ and $i$. We fix such a partition, and let $R=R'=K_{\Delta+1}$. Using Theorem <ref> we can for any $n$-vertex graph $H$ with $\Delta(H)\le\Delta$ find a size-compatible $R$-partition of $V(H)$, and applying Lemma <ref> with all vertices designated as potential buffer vertices, with $d=\tfrac{1}{16}$ and with no vertices image restricted, we see that $H\subseteq G$ as desired.

§ PARTITION UNIVERSALITY

We now prove that $G(n,p)$ is a.a.s. $r$-partition universal for $\cH(n,d,\Delta)$ provided $p\ge C\big(\tfrac{\log n}{n}\big)^{1/(2d)}$, which improves on the result of Kohayakawa, Rödl, Schacht and Szemerédi [47] for graphs with $d\le\Delta/2$. A proof of the result of [47] can be obtained along very similar lines.

We need two by now classical results of extremal combinatorics: Ramsey's Theorem and Turán's Theorem.
The Ramsey number $r_k(K_t)$ is the smallest integer $n$ such that no matter how one colors the edges of $K_n$ with $k$ colors, there is a monochromatic copy of $K_t$. Ramsey [61] proved these numbers exist, while the following quantative statement is due to Erdős and Szekeres [31].

For any $k$ and $t$ we have $r_k(K_t)\le k^{kt}$.

Turán, generalising a result of Mantel [59], proved the following.

For any $r\ge 3$ the unique $K_r$-free graph with most edges is the complete balanced $(r-1)$-partite graph on $n$ vertices.