Y_{i}^{good}:=Y_{i}^{H}\setminus Y_{i}^{bad}.\quad\quad\leavevmode\nobreak\
\leavevmode\nobreak\ \hphantom{Y_{i}^{bad}}$

Claim 4.  Suppose $G^{\circ}\subseteq G_{B}$, $H\in\mathcal{H}$, and
$Y_{i}^{H}\subseteq X_{i}^{H}$ for all $i\in[r]$ such that the following hold
for all $i\in[r]$, where
$W_{i}^{H}:=V_{i}\setminus\phi_{r}(\widehat{X}_{i}^{H}\setminus Y_{i}^{H})$:

  1. (A)C6.1

$X_{i}^{H}\setminus\widehat{X}_{i}^{H}\subseteq Y_{i}^{H}\subseteq X_{i}^{H}$
and $|Y_{i}^{H}|=|W_{i}^{H}|=(1\pm{\varepsilon}_{T}^{1/2})\mu n$;

  2. (B)C6.1

$|E{r}^{bad}|\leq\mu^{3/2}n$ for all $\mathscrs{r}\in E(R)$;

  3. (C)C6.1

$|N_{B_{i}^{H}}(v)\cap Y_{i}^{bad}|\leq\mu^{3/2}d_{i}n$ for all $i\in[r]$,
$v\in W_{i}^{H}$;

  4. (D)C6.1

$(B_{i}^{H})^{G^{\circ}}$ is $(\mu^{1/5},d_{i})$-super-regular for all
$i\in[r]$;

  5. (E)C6.1

$(B_{i}^{H})^{G^{\circ}}[Y_{i}^{H},W_{i}^{H}]$ is $(\mu^{1/6},d_{i})$-super-
regular for all $i\in[r]$;

  6. (F)C6.1

$G_{B}-G^{\circ}$ is $(\mu^{1/2},t,d_{B})$-typical with respect to $R$;

  7. (G)C6.1

for all $\mathcal{S}\subseteq\bigcup_{\mathscrs{r}\in E(R)\colon
i\in\mathscrs{r}}V_{\sqcup\mathscrs{r}\setminus\\{i\\}}$ with
$|\mathcal{S}|\leq t$, we have

$\big{|}W_{i}^{H}\cap
N_{G_{B}-G^{\circ}}(\mathcal{S})\big{|}=(1\pm{\varepsilon}_{T}^{1/2})\mu\big{|}V_{i}\cap
N_{G_{B}-G^{\circ}}(\mathcal{S})\big{|}.$

Then there exists a probability distribution of the embeddings
$\phi^{\widetilde{H}}$ of $\widetilde{H}:=H[Y^{H}_{\cup[r]}]$ into
$\widetilde{G}:=G_{B}[W^{H}_{\cup[r]}]-G^{\circ}$ with
$\phi^{H}:=\phi^{\widetilde{H}}\cup\phi_{r}|_{V(H)\setminus V(\widetilde{H})}$
such that

  1. (H)C6.1

$\phi^{H}$ is an embedding of $H$ into $G$ where $\phi^{H}(X_{i}^{H})=V_{i}$
for all $i\in[r]$;

  2. (J)C6.1

$\phi^{H}$ embeds all $H$-edges that contain a vertex in $Y_{\cup[r]}^{H}$
onto an edge in $G_{B}-G^{\circ}$;

  3. (K)C6.1

$\displaystyle\mathrm{\mathbb{P}}\left[\phi^{H}(\mathscrs{e}\cap X_{\cup
I}^{H})=\\{v_{i}\\}_{i\in I}\right]\leq{\prod_{i\in I\colon\mathscrs{e}\cap
Y_{i}^{H}\neq\emptyset}2(\mu d_{i}n)^{-1}}$
for all $m\in[k]$, index sets $I\in\binom{[r]}{m}$, $\\{v_{i}\\}_{i\in I}\in
V_{\sqcup I}$, and $H$-edges $\mathscrs{e}$ that contain a vertex in $Y_{\cup
I}^{H}$.

Proof of claim: We split the proof of Claim 6.1 into two parts, Step 6.1 and
6.1. In Step 6.1, we greedily embed all the $H$-edges of $\mathcal{E}^{bad}$
into $G_{B}-G^{\circ}$ by considering the clusters in turn. Afterwards, in
Step 6.1, we are left with the $H$-edges in $\mathcal{E}^{good}$; that is,
where only a single vertex is not yet embedded. The assumptions (B)C6.1 and
(C)C6.1 will guarantee that we only used few edges in $G_{B}-G^{\circ}$ in
Step 6.1, such that we merely have to modify our candidacy graphs. Hence, we
can easily find a perfect matching in each of these candidacy graphs to embed
the $H$-edges of $\mathcal{E}^{good}$, which will complete the embedding of
$H$. This matching procedure can be performed independently for each cluster
as the $H$-edges in $\mathcal{E}^{good}$ only contain a single vertex that is
not yet embedded. Clearly, this approach will establish (H)C6.1 and (J)C6.1.

In both steps, we will embed the vertices of $H$ by a random procedure in
order to establish (K)C6.1. We will do so by making several random choices
sequentially which naturally yields a probability distribution. Since some of
these choices lead to instances that do not yield a valid or good embedding,
we will discard some of these instances and say the random procedure
terminates with failure in these cases. We will show that the proportion of
choices with failure instances is exponentially small, that is, the
probability that the random procedure terminates with failure is exponentially
small in $n$. This allows us to discard some of these choices / instances and
to restrict our probability space to the remaining ‘nice’ outcomes. Since the
failure probability is exponentially small in $n$, this does not have a
significant effect on the probability in (K)C6.1.

_Step 5.4. _ Proof of Claim 6.1 – Embedding the $H$-edges in
$\mathcal{E}^{bad}$

Suppose $\phi_{q}^{bad}\colon Y_{\cup[q]}^{bad}\to W^{H}_{\cup[q]}$ is an
injective function. Similarly as we defined candidacy graphs in Definition
4.1, we will also define updated candidacy graphs of $B_{i}^{H}$ with respect
to $\phi_{q}^{bad}$ for $i\in[r]\setminus[q]$. To that end, for all
$i\in[r]\setminus[q]$ and $B\subseteq B_{i}^{H}$, let $B(\phi_{q}^{bad})$ be
the spanning subgraph of $B$, where we keep the edge $xv$ of $B$ in
$B(\phi_{q}^{bad})$ if all $\mathscrs{e}\in\mathcal{E}^{bad}$ with
$\mathscrs{e}\cap Y_{\cup([r]\setminus[q])}^{bad}=\\{x\\}$ satisfy that

(6.32) $\displaystyle\phi_{r}|_{V(H)\setminus
V(\widetilde{H})}(\mathscrs{e}\setminus
V(\widetilde{H}))\cup\phi_{q}^{bad}(\mathscrs{e}\cap
Y_{\cup[q]}^{bad})\cup\\{v\\}\in E(G_{B}-G^{\circ}).$

Observe that (6.32) is very similar to (4.1) in Definition 4.1. For all
$q\in[r]$, $i\in[r]\setminus[q]$, $y\in Y_{i}^{bad}$, let

$\displaystyle
b_{q}(y):=\left|\left\\{\mathscrs{e}\in\mathcal{E}^{bad}\colon\mathscrs{e}\cap
Y_{\cup([r]\setminus[q])}^{bad}=\\{y\\}\right\\}\right|.$

That is, $b_{q}(y)$ is the number of edges $\mathscrs{e}$ in
$\mathcal{E}^{bad}$ containing $y$ whose $(k-1)$-set
$\mathscrs{e}\setminus\\{y\\}$ has already been embedded by
$\phi_{r}|_{V(H)\setminus V(\widetilde{H})}\cup\phi_{q}^{bad}$.

We make one more observation and fix $y\in Y_{q+1}^{bad}$. Since $B_{q+1}^{H}$
is $({\varepsilon}_{T},d_{B}^{\deg_{R}(q+1)})$-super-regular and
$({\varepsilon}_{T},t^{2/3})$-well-intersecting by $\mathbf{S}(r)$(a), we have
that for all $\mathscrs{r}\in E(R)$ and $\mathscrs{e}\in E{r}^{bad}$ with
$\mathscrs{e}\cap Y_{\cup([r]\setminus[q])}^{bad}=\\{y\\}$, there exists a
$(k-1)$-set $S{r}=\phi_{r}^{+}(\mathscrs{e}\setminus\\{y\\})\in
V_{\sqcup(\mathscrs{r}\setminus\\{q+1\\})}$, as well as there exists a set
$\mathcal{S}_{y}$ of $(k-1)$-sets with $S{r}\in\mathcal{S}_{y}$ and
$|\mathcal{S}_{y}|=\operatorname{deg}_{R}(q+1)$ such that
$N_{B_{q+1}^{H}}(y)=V_{q+1}\cap N_{G_{B}}(\mathcal{S}_{y})$ and
$|N_{B_{q+1}^{H}}(y)|=(1\pm{\varepsilon}_{T})d_{B}^{|\mathcal{S}_{y}|}n$. (See
(4.2) for the definition of well-intersecting.) Note that $\phi_{r}^{+}$
embeds $\mathscrs{e}\setminus\\{y\\}$ onto $S{r}$ but
$\phi_{r}|_{V(H)\setminus V(\widetilde{H})}$ does not. Hence, $S{r}$ only
serves as a ‘dummy’ $(k-1)$-set for updating the candidacy graph $B_{q+1}^{H}$
conveniently and to artificially restrict the candidates for $y$. That is,
$V_{q+1}\cap N_{G_{B}}(\mathcal{S}_{y}\setminus\\{S{r}\\})$ are also suitable
candidates where we could embed $y$, assuming that
$\mathscrs{e}\setminus\\{y\\}$ has not been embedded yet. Let
$\mathcal{S}_{y}^{dummy}$ be the set of all these $(k-1)$-sets $S{r}$ for $y$,
and note that $|\mathcal{S}_{y}^{dummy}|=b_{q}(y)$.

During our process of embedding the $H$-edges in $\mathcal{E}^{bad}$, we will
have to drop this artificial restriction of the candidate sets. To that end,
suppose we are given a spanning subgraph $B\subseteq B_{q+1}^{H}$, $y\in
Y_{q+1}^{bad}$, and there exists a set $\mathcal{S}^{\prime}_{y}$ of
$(k-1)$-sets such that we can write

$\displaystyle N_{B}(y)=V_{q+1}\cap
N_{G_{B}-G^{\circ}}(\mathcal{S}_{y}^{\prime}).$

Then let $B^{\ominus dummy}$ be the spanning supergraph of $B$ where the
neighbourhood of each vertex $y\in Y_{q+1}^{bad}$ is given by

(6.33) $\displaystyle N_{B^{\ominus dummy}}(y)=V_{q+1}\cap
N_{G_{B}-G^{\circ}}(\mathcal{S}_{y}^{\prime}\setminus\mathcal{S}_{y}^{dummy}).$

We inductively prove that the following statement $\mathbf{C1}(q)$ holds for
all $q\in[r]_{0}$, which will extend $\phi_{r}|_{V(H)\setminus
V(\widetilde{H})}$ by embedding the edges in $\mathcal{E}^{bad}$ into
$G_{B}-G^{\circ}$. To that end, we define a set of good pairs of vertices.

(6.34)

We note for future reference that

(6.35) $\displaystyle\bigg{|}\binom{Y_{i}^{good}}{2}\setminus
Y_{i}^{good\leavevmode\nobreak\ pairs}\bigg{|}\leq 2n\cdot
n^{1/4+{\varepsilon}_{T}}\leq n^{4/3},$

since $B_{i}^{H}$ is $({\varepsilon}_{T},t^{2/3})$-well-intersecting as
defined in (4.2).

  * $\mathbf{C1}(q)$.

There exists a probability distribution of the injective functions
$\phi_{q}^{bad}\colon Y^{bad}_{\cup[q]}\to W^{H}_{\cup[q]}$ with
$\phi^{\prime}_{q}:=\phi_{q}^{bad}\cup\phi_{r}|_{V(H)\setminus
V(\widetilde{H})}$ such that

    1. (I)C6.1

$\phi^{\prime}_{q}$ is an embedding of
$H^{\prime}_{q}:=H[Y_{\cup[q]}^{bad}\cup(V(H)\setminus V(\widetilde{H}))]$
into $G$;

    2. (II)C6.1

all edges in $H[Y_{\cup[q]}^{bad}\cup(V(H)\setminus V(\widetilde{H}))]$ that
contain a vertex in $Y_{\cup[q]}^{bad}$ are embedded on an edge in
$G_{B}-G^{\circ}$;

    3. (III)C6.1

for every vertex $x\in Y_{i}^{good}$ and $i\in[q]$, there are at most
$\mu^{4/3}d_{i}n$ vertices $y\in Y_{i}^{bad}$ with $\phi_{q}^{bad}(y)\in
N_{B_{i}^{H}}(x)$;

    4. (IV)C6.1

$\displaystyle\mathrm{\mathbb{P}}\left[\phi_{q}^{\prime}(\mathscrs{e}\cap
X_{\cup I}^{H})=\\{v_{i}\\}_{i\in I}\right]\leq{\prod_{i\in
I\colon\mathscrs{e}\cap Y_{i}^{H}\neq\emptyset}2(\mu d_{i}n)^{-1}}$
for all $\mathscrs{r}\in E(R)$, $m\in[k]$,
$I\in\binom{\mathscrs{r}\cap[q]}{m}$, $\\{v_{i}\\}_{i\in I}\in V_{\sqcup I}$
and $\mathscrs{e}\in E{r}^{bad}$.

The statement $\mathbf{C1}(0)$ clearly holds for $\phi_{0}^{bad}$ being the
empty function. Hence, we assume the truth of $\mathbf{C1}(q)$ for some
$q\in[r-1]_{0}$. Our strategy to establish $\mathbf{C1}(q+1)$ is as follows.
We extend the probability space given in $\mathbf{C1}(q)$ by making further
random choices. For $\phi_{q}^{bad}$ as in $\mathbf{C1}(q)$, we aim to find a
matching $\sigma_{q+1}^{bad}\colon Y_{q+1}^{bad}\to W^{H}_{q+1}$ in a suitable
candidacy graph between $Y_{q+1}^{bad}$ and $W^{H}_{q+1}$ that extends
$\phi_{q}^{bad}$ to $\phi_{q+1}^{bad}:=\phi_{q}^{bad}\cup\sigma_{q+1}^{bad}$.
If we can find such a matching $\sigma_{q+1}^{bad}$, then
$\mathbf{C1}(q+1)$(I)C6.1 and (II)C6.1 will hold by the definition of this
suitable candidacy graph. In particular, we will find $\sigma_{q+1}^{bad}$ by
a random procedure to also ensure (IV)C6.1. We will discard an exponentially
small proportion of random choices during this procedure in order to satisfy
(III)C6.1 and to obtain a suitable embedding $\sigma_{q+1}^{bad}$.

Let us describe this suitable candidacy graph. We will choose
$\sigma_{q+1}^{bad}$ randomly in

$\displaystyle\widetilde{B}:=(B_{q+1}^{H})^{G^{\circ}}(\phi_{q}^{bad})^{\ominus
dummy}[Y_{q+1}^{bad},W^{H}_{q+1}].$

That is, $\widetilde{B}$ arises from $B_{q+1}^{H}$ as follows.

  * •

First, we restrict the candidate sets in $B_{q+1}^{H}$ to those edges whose
corresponding edges in $G_{B}$ have not been used in $G^{\circ}$ for packing
graphs $H_{1},\ldots,H_{h}$ in previous rounds.

  * •

Second, we restrict the candidate sets with respect to the packing
$\phi_{q}^{bad}$ of the vertices in $Y_{\cup[q]}^{bad}$ according to (6.32).

  * •

Third, we drop the restriction of the candidate sets to the dummy $(k-1)$-sets
as in (6.33).

  * •

In the end, we consider the induced subgraph of this candidacy graph on the
bad vertices $Y_{q+1}^{bad}$ and the vertices $W_{q+1}^{H}$ that can be used
for the completion.

For the sake of a better readability, let $B:=(B_{q+1}^{H})^{G^{\circ}}$.

To guarantee the existence of $\sigma_{q+1}^{bad}$, we will show that the
degree of every vertex $y\in Y_{q+1}^{bad}$ is sufficiently large in $B$ and
also in $\widetilde{B}$. Let $y\in Y_{q+1}^{bad}$ be fixed. Since
$B_{q+1}^{H}$ is $({\varepsilon}_{T},t^{2/3})$-well-intersecting by
$\mathbf{S}(r)$(a), there exists a set
$\mathcal{S}_{y}\subseteq\bigcup_{\mathscrs{r}\in E(R)\colon
q+1\in\mathscrs{r}}V_{\sqcup\mathscrs{r}\setminus\\{q+1\\}}$ of $(k-1)$-sets
with $|\mathcal{S}_{y}|\leq t^{2/3}$ such that $N_{B_{q+1}^{H}}(y)=V_{q+1}\cap
N_{G_{B}}(\mathcal{S}_{y})$. Hence, by the definition of
$B=(B_{q+1}^{H})^{G^{\circ}}$ in (6.25), we have

(6.36) $\displaystyle N_{B}(y)=V_{q+1}\cap
N_{G_{B}-G^{\circ}}(\mathcal{S}_{y}),\quad\text{ and
}\quad\operatorname{deg}_{B}(y)=(1\pm 2\mu^{1/5})d_{q+1}n,$

because $B$ is $(\mu^{1/5},d_{q+1})$-super-regular by (D)C6.1. Of course we
have to restrict the potential images of $y$ according to the vertices we
already embedded by $\phi_{q}^{bad}$. To this end, let

$\displaystyle\mathcal{S}_{y}^{bad}:=\left\\{\phi_{q}^{bad}(\mathscrs{e}\cap
Y_{\cup[q]}^{bad})\cup\phi_{r}|_{V(H)\setminus
V(\widetilde{H})}(\mathscrs{e}\setminus
V(\widetilde{H}))\colon\mathscrs{e}\in\mathcal{E}^{bad},\mathscrs{e}\cap
Y_{\cup([r]\setminus[q])}^{bad}=\\{y\\}\right\\}$

and note that $|\mathcal{S}_{y}^{bad}|=b_{q}(y)$. By the definition of the
candidacy graph $B(\phi_{q}^{bad})$ in (6.32) and by (6.36), we obtain

$\displaystyle N_{B(\phi_{q}^{bad})}(y)=V_{q+1}\cap
N_{G_{B}-G^{\circ}}(\mathcal{S}_{y}\cup\mathcal{S}_{y}^{bad}),$

and thus, together with (F)C6.1 and (6.36), we have that

$\displaystyle\operatorname{deg}_{B(\phi_{q}^{bad})}(y)=(1\pm\mu^{1/6})d_{q+1}d_{B}^{b_{q}(y)}n.$

Since $|\mathcal{S}_{y}^{dummy}|=b_{q}(y)$, this implies

(6.37) $\displaystyle\operatorname{deg}_{B(\phi_{q}^{bad})^{\ominus
dummy}}(y)=\Big{|}V_{q+1}\cap
N_{G_{B}-G^{\circ}}\big{(}(\mathcal{S}_{y}\setminus\mathcal{S}_{y}^{dummy})\cup\mathcal{S}_{y}^{bad}\big{)}\Big{|}=(1\pm\mu^{1/6})d_{q+1}n.$

Now, we obtain

(6.38) $\displaystyle N_{\widetilde{B}}(y)=W^{H}_{q+1}\cap
N_{G_{B}-G^{\circ}}\big{(}(\mathcal{S}_{y}\setminus\mathcal{S}_{y}^{dummy})\cup\mathcal{S}_{y}^{bad}\big{)}$

and thus, by (G)C6.1 and (6.37), we have that

(6.39)
$\displaystyle\operatorname{deg}_{\widetilde{B}}(y)=(1\pm\mu^{1/7})d_{q+1}\mu
n.$

In order to guarantee (IV)C6.1, we find $\sigma_{q+1}^{bad}$ via the following
random procedure:

  * •

for every vertex $y\in Y_{q+1}^{bad}$ in turn, we choose a neighbour in
$N_{\widetilde{B}}(y)$ uniformly at random among all neighbours that have not
been chosen in previous turns;

  * •

we terminate the random procedure with failure at some step of the procedure,
say at the turn of some vertex $y\in Y_{q+1}^{bad}$,

    * –

if we have less than $2(\mu d_{q+1}n)/3$ choices to select an image for $y$ in
$N_{\widetilde{B}}(y)$, or

    * –

if there is a vertex $x\in Y_{q+1}^{good}$ such that (III)C6.1 is violated,
that is, we mapped in previous turns already more than $\mu^{4/3}d_{q+1}n$
vertices of $Y_{q+1}^{bad}$ into $N_{B_{q+1}^{H}}(x)$.

We show in the following claim that this random procedure terminates with
failure only with exponentially small probability. If the procedure does not
terminate with failure, we obtain a random $Y_{q+1}^{bad}$-saturating matching
$\sigma_{q+1}^{bad}\colon Y_{q+1}^{bad}\to W^{H}_{q+1}$ in $\widetilde{B}$,
which by definition of the candidacy graph $B_{q+1}^{H}$ and $\widetilde{B}$
implies $\mathbf{C1}(q+1)$(I)C6.1–(III)C6.1. Further, $\sigma_{q+1}^{bad}$
satisfies the following.

(6.40)

Hence, the following claim together with $\mathbf{C1}(q)$(IV)C6.1 establishes
$\mathbf{C1}(q+1)$(IV)C6.1.

Claim 5.  The random procedure for computing $\sigma^{bad}_{q+1}$ terminates
with failure with probability at most ${\rm e}^{-n^{1/2}}$.

Proof of claim: Let $Y_{q+1}^{bad}=\\{y_{1},\ldots,y_{m}\\}$ and we consider
every vertex in turn, that is, $y_{\ell+1}$ will be treated after $y_{\ell}$.
For all $x\in Y_{q+1}^{H}$ and $\ell\in[m]$, let $\xi_{\ell}(x)$ be the random
variable that counts the number of covered neighbours so far, that is, the
number of vertices $v\in N_{B_{q+1}^{H}}(x)$ such that
$\sigma_{q+1}^{bad}(y)=v$ for some $y\in\\{y_{i}\\}_{i\in[\ell]}$. We say the
random procedure fails at step $\ell\in[m]$, if $\ell$ is the smallest integer
such that

  * •

$\xi_{\ell}(z)>\mu^{2/5}d_{q+1}\mu n$ for some vertex $z\in
Y_{q+1}^{good}\cup\\{y_{i}\\}_{i\in[m]\setminus[\ell]}$.

We show that the random procedure fails at some step $\ell\in[m]$ with
probability at most ${\rm e}^{-n^{2/3}}$. A union bound then establishes Claim
6.1.

We fix $\ell\in[m]$ and a vertex $z\in
Y_{q+1}^{good}\cup\\{y_{i}\\}_{i\in[m]\setminus[\ell]}$. By employing (6.38),
(6.39) and that $B_{q+1}^{H}$ is $({\varepsilon}_{T},t^{2/3})$-well-
intersecting, we obtain

(6.41) $\displaystyle|N_{\widetilde{B}}(y\land
z)|=(1\pm\mu^{1/7})d_{q+1}^{2}\mu n\text{ for all but at most $n^{1/3}$
vertices $y\in\\{y_{i}\\}_{i\in[\ell]}$.}$

Further, at the turn of each $y_{i}$, $i\in[\ell]$, we have at least

(6.42) $\displaystyle|N_{\widetilde{B}}(y_{i})|-\mu^{2/5}d_{q+1}\mu
n\stackrel{{\scriptstyle\eqref{eq:B'-degree
y}}}{{\geq}}(1-2\mu^{1/7})d_{q+1}\mu n$

choices for the embedding of $y_{i}$. Hence, by (6.41) and (6.42), the
probability that a vertex $y_{i}$, $i\in[\ell]$ which satisfies (6.41) is
mapped into $N_{\widetilde{B}}(z)$ is at most

$\displaystyle\frac{(1+\mu^{1/7})d_{q+1}^{2}\mu n}{(1-2\mu^{1/7})d_{q+1}\mu
n}\leq 2d_{q+1}.$

This implies that

$\displaystyle\mathrm{\mathbb{E}}\left[\xi_{\ell}(z)\right]\leq
2d_{q+1}\ell+n^{1/3}\leq 2d_{q+1}|Y_{q+1}^{bad}|+n^{1/3}\leq
3d_{q+1}\alpha^{-1}\mu^{3/2}n,$

where we used that $|Y_{q+1}^{bad}|\leq\alpha^{-1}\mu^{3/2}n$ by (B)C6.1.
Hence, Theorem 3.1 implies that $\xi_{\ell}(z)>\mu^{2/5}d_{q+1}\mu n$ with
probability, say, at most ${\rm e}^{-n^{2/3}}$ for some $z\in
Y_{q+1}^{good}\cup\\{y_{i}\\}_{i\in[m]\setminus[\ell]}$. Thus, the random
procedure fails at step $\ell$ with probability at most ${\rm e}^{-n^{2/3}}$.
A simple union bound completes the proof of Claim 6.1.  $-$

_Step 5.5. _ Proof of Claim 6.1 – Embedding the $H$-edges in
$\mathcal{E}^{good}$

Let $\phi_{r}^{bad}\colon Y^{bad}_{\cup[r]}\to W^{H}_{\cup[r]}$ and
$\phi_{r}^{\prime}=\phi_{r}^{bad}\cup\phi_{r}|_{V(H)\setminus
V(\widetilde{H})}$ be as in $\mathbf{C1}(r)$ obtained in Step 6.1. Recall that
for all $i\in[r]$, we have $Y_{i}^{good}=Y_{i}^{H}\setminus Y_{i}^{bad}$ and
let $W_{i}^{good}:=W_{i}^{H}\setminus\phi_{r}^{bad}(Y_{i}^{bad})$, and thus
clearly, $|Y_{i}^{good}|=|W_{i}^{good}|$. For every $i\in[r]$, we aim to embed
the vertices $Y_{i}^{good}$ onto $W_{i}^{good}$ by finding a perfect matching
in $(B_{i}^{H})^{G^{\circ}}$.

Let $i\in[r]$ be fixed. By (E)C6.1, we have that
$\widehat{B}_{i}:=(B_{i}^{H})^{G^{\circ}}[Y_{i}^{H},W_{i}^{H}]$ is
$(\mu^{1/6},d_{i})$-super-regular. We show that for every vertex in
$Y_{i}^{good}\cup W_{i}^{good}$, we only removed few incident edges when take
the subgraph $B_{i}^{good}:=\widehat{B}_{i}[Y_{i}^{good},W_{i}^{good}]$ of
$\widehat{B}_{i}$. For a vertex $v\in W_{i}^{good}$, we removed at most
$\mu^{3/2}d_{i}n$ incident edges by (C)C6.1. For a vertex $x\in Y_{i}^{good}$,
we removed at most $\mu^{4/3}d_{i}n$ incident edges by (III)C6.1. Hence, by
employing Fact 3.4, we obtain that $B_{i}^{good}$ is
$(\mu^{1/19},d_{i})$-super-regular for every $i\in[r]$.

Our strategy is to apply Lemma 3.7 that allows us to find a regular spanning
subgraph of $B_{i}^{good}$ from which we can easily take a random perfect
matching. In order to satisfy the assumptions of Lemma 3.7, we show that the
common neighbourhood of most of the pairs in $Y_{i}^{good}$ is also not too
large in $B_{i}^{good}$. To that end, we fix a pair of vertices
$\\{y,y^{\prime}\\}\in Y_{i}^{good\leavevmode\nobreak\ pairs}$ as defined in
(6.34) and let $\mathcal{S}_{y},\mathcal{S}_{y^{\prime}}$ be the sets of
$(k-1)$-sets such that $N_{B_{i}^{H}}(x)=V_{i}\cap N_{G_{B}}(\mathcal{S}_{x})$
for each $x\in\\{y,y^{\prime}\\}$. We have that

(6.43) $\displaystyle N_{\widehat{B}_{i}}(y\land y^{\prime})=W_{i}^{H}\cap
N_{(B_{i}^{H})^{G^{\circ}}}(y\land y^{\prime})=W_{i}^{H}\cap
N_{G_{B}-G^{\circ}}(\mathcal{S}_{y}\cup\mathcal{S}_{y^{\prime}}).$

Hence, we obtain

$\displaystyle|N_{B_{i}^{good}}(y\land y^{\prime})|$
$\displaystyle\stackrel{{\scriptstyle\hphantom{\eqref{eq:common neighbourhood
tB_i},\ref{item:mu well-intersecting}}}}{{\leq}}|N_{\widehat{B}_{i}}(y\land
y^{\prime})|$ $\displaystyle\stackrel{{\scriptstyle\eqref{eq:common
neighbourhood tB_i},\ref{item:mu well-
intersecting}}}{{\leq}}(1+{\varepsilon}_{T}^{1/2})\mu\big{|}V_{i}\cap
N_{G_{B}-G^{\circ}}(\mathcal{S}_{y}\cup\mathcal{S}_{y^{\prime}})\big{|}$
(6.44) $\displaystyle\stackrel{{\scriptstyle\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \ref{item:G_B-
Gcirc typical}\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
}}{{\leq}}(1+2\mu^{1/2})\mu d_{i}^{2}n,$

where we used for the last equality that
$\mathcal{S}_{y}\cap\mathcal{S}_{y^{\prime}}=\emptyset$ since
$\\{y,y^{\prime}\\}\in Y_{i}^{good\leavevmode\nobreak\ pairs}$, and thus,
$d_{B}^{|\mathcal{S}_{y}\cup\mathcal{S}_{y^{\prime}}|}=d_{i}^{2}$. Hence,
(6.35) implies that all but at most $n^{4/3}$ pairs of vertices in
$Y_{i}^{good}$ satisfy (6.44).

Finally, we can apply Lemma 3.7 and obtain a spanning $\mu d_{i}n/2$-regular
subgraph of $B_{i}^{good}$. In particular, $B_{i}^{good}$ contains $\mu
d_{i}n/2$ edge-disjoint perfect matchings, from which we choose one perfect
matching $\sigma_{i}^{good}\colon Y_{i}^{good}\to W_{i}^{good}$ for each
$i\in[r]$ uniformly and independently at random. We crucially observe:

(6.45)

Further, since all the vertices in $H_{\ast}[Y_{\cup[r]}^{good}]$ are
isolated, we have that $\phi^{good}:=\bigcup_{i\in[r]}\sigma_{i}^{good}$ is an
injective function $\phi^{good}\colon Y_{\cup[r]}^{good}\to
W_{\cup[r]}^{good}$ such that $\phi_{r}|_{V(H)\setminus
V(\widetilde{H})}\cup\phi^{good}$ is a random packing of
$H[Y_{\cup[q]}^{good}\cup(V(H)\setminus V(\widetilde{H}))]$ into $G$ that
embeds all edges in $H[Y_{\cup[r]}^{good}\cup(V(H)\setminus
V(\widetilde{H}))]$ that contain a vertex in $Y_{\cup[r]}^{good}$ on an edge
in $G_{B}-G^{\circ}$. In particular, since we find the perfect matchings in
the candidacy graphs $(B_{i}^{H})^{G^{\circ}}$ induced on $Y_{i}^{good}\cup
W_{i}^{good}$ for each $i\in[r]$, we have for
$\phi^{H}:=\phi_{r}|_{V(H)\setminus
V(\widetilde{H})}\cup\phi_{r}^{bad}\cup\phi^{good}$ that

  * •

$\phi^{H}$ is an embedding of $H$ into $G$ where $\phi^{H}(X_{i}^{H})=V_{i}$
for all $i\in[r]$, which establishes (H)C6.1;

  * •

all $H$-edges that contain a vertex in $Y_{\cup[r]}^{H}$ are embedded on an
edge in $G_{B}-G^{\circ}$, which establishes (J)C6.1;

  * •

for all $m\in[k]$, index sets $I\in\binom{[r]}{m}$, $\\{v_{i}\\}_{i\in I}\in
V_{\sqcup I}$, and $H$-edges $\mathscrs{e}$ that contain a vertex in $Y_{\cup
I}^{H}$, we have that $\phi^{H}(\mathscrs{e}\cap X_{\cup
I}^{H})=\\{v_{i}\\}_{i\in I}$ with probability at most ${\prod_{i\in
I\colon\mathscrs{e}\cap Y_{i}^{H}\neq\emptyset}2(\mu d_{i}n)^{-1}}$ by
$\mathbf{C1}(r)$(IV)C6.1 and (6.45), which establishes (K)C6.1.

This completes the proof of Claim 6.1.  $-$

_Step 5.6. _ The random packing procedure – Claim 6.1

We now proceed to our Random Packing Procedure (RPP). Let $G_{0}^{\circ}$ be
the edgeless graph on $V(G)$ and let $\phi^{0}$ be the empty function. We
perform the following random procedure.

Random Packing Procedure (RPP) For $h=1,\ldots,|\mathcal{H}|$ do: • Set
$H:=H_{h}$. For all $i\in[r]$, independently activate every vertex in
$\widehat{X}_{i}^{H}$ with probability $\mu$ and let $Y_{i}^{H}$ be the union
of $X_{i}^{H}\setminus\widehat{X}_{i}^{H}$ and all activated vertices in
$\widehat{X}_{i}^{H}$. • If the assumptions of Claim 6.1 are satisfied, apply
Claim 6.1 and obtain a random packing $\phi^{H}$ that satisfies
(H)C6.1–(K)C6.1; otherwise terminate with failure. • Set
$\phi^{h}:=\phi^{h-1}\cup\phi^{H}$ and
$G_{h}^{\circ}:=G_{h-1}^{\circ}\cup(\phi^{H}(H)\cap G_{B})$.

Claim 6.  With probability at least $1-1/n$, the RPP terminates without
failure and satisfies conclusion (iii) of Lemma 6.1.  Proof of claim: We prove
Claim 6.1 in Steps 6.1–6.1. Our general strategy is to guarantee that we can
apply Claim 6.1 in each turn of the procedure. To that end, we will introduce
a collection of random variables that we call _identifiers_. Such an
identifier indicates an unlikely event and if this event happens, we say the
identifier _detects alarm_ and we simply terminate the RPP with failure. This
means, if an identifier detects alarm at some turn $h\in[|\mathcal{H}|]$, we
terminate the RPP and deactivate all further identifiers; that is, the
probability that they detect alarm is set to $0$. We show that the probability
that an individual identifier detects alarm is exponentially small in $n$. In
the end, a union bound over all identifiers will imply that with probability
at least $1-1/n$, none of the identifiers will detect alarm and thus, the RPP
terminates without failure.

For most of the identifiers, it follows by a standard application of Theorem
3.1 that the probability to detect alarm is exponentially small (in fact,
often Chernoff’s inequality suffices). To that end, in the subsequent Steps
6.1–6.1, we often describe only the random variables to which we apply Theorem
3.1.

First, let us observe that $\mathbf{S}(r)$ implies that

(6.46)
$\displaystyle\big{|}X_{i}^{H}\setminus\widehat{X}_{i}^{H}\big{|}=\big{|}V_{i}\setminus\phi_{r}(\widehat{X}_{i}^{H})\big{|}\leq
2{\varepsilon}_{T}n\text{ for all $H\in\mathcal{H}$, $i\in[r]$.}$

Further, for $Y_{i}^{H}$ as in the RPP, let
$W_{i}^{H}:=V_{i}\setminus\phi_{r}(\widehat{X}_{i}^{H}\setminus Y_{i}^{H})$.
For convenience, we also call a vertex $w\in
W_{i}^{H}\cap\phi_{r}(\widehat{X}_{i}^{H})$ _activated_ by $H\in\mathcal{H}$.
(Recall that we only activate vertices in $\widehat{X}_{i}^{H}$.)

_Step 5.7. _ Proof of Claim 6.1 – Establishing (A)C6.1–(G)C6.1

In this step, in order to establish (A)C6.1–(G)C6.1 at each turn of the RPP,
we consider several random variables for which we individually introduce an
identifier that detects alarm if the considered random variable is not within
a factor of $(1\pm{\varepsilon})$ of its expectation. As mentioned above, for
each identifier a standard application of Theorem 3.1 implies that the
probability to detect alarm is exponentially small, say, ${\rm e}^{-n^{1/2}}$.
Let us only describe the random variables that we consider for establishing
(A)C6.1–(G)C6.1.

To establish (A)C6.1, for each $H\in\mathcal{H}$, $i\in[r]$, we consider the
sum of indicator variables which indicate whether a vertex is activated in
$X_{i}^{H}$. Together with (6.46), this implies (A)C6.1.

To establish (B)C6.1, for each $H\in\mathcal{H}$ and $\mathscrs{r}\in E(R)$,
we consider the random variable that counts how many $H$-edges $\mathscrs{e}$
lie in $X_{\cup\mathscrs{r}}^{H}$ where at least two vertices of
$\mathscrs{e}$ are activated; in view of the statement, we may assume that
$e_{H}(X_{\cup\mathscrs{r}}^{H})\geq\mu^{3/2}n$. Note that the probability for
an edge $\mathscrs{e}$ that at least two vertices are activated is at most
$k^{2}\mu^{2}$. Together with (6.46), this implies (B)C6.1.

To establish (C)C6.1, for all $H\in\mathcal{H}$, $i\in[r]$, and $v\in V_{i}$,
we consider the random variable $\xi$ that counts how many
$B_{i}^{H}$-neighbours of $v$ in $X_{i}^{H}$ are activated and lie in an
$H$-edge $\mathscrs{e}$ where a second vertex in $\mathscrs{e}$ is either
activated or left unembedded. With Claim 6.1 we have that
$\mathrm{\mathbb{E}}\left[\xi\right]\leq
2k^{2}\mu^{2}\alpha^{-1}d_{i}n+2\mu{\varepsilon}_{T}^{1/2}d_{i}n\leq\mu^{5/3}d_{i}n$.
Together with Claim 6.1, this implies (C)C6.1.

To establish (G)C6.1, for all $i\in[r]$,
$\mathcal{S}\subseteq\bigcup_{\mathscrs{r}\in E(R)\colon
i\in\mathscrs{r}}V_{\sqcup\mathscrs{r}\setminus\\{i\\}}$, $|\mathcal{S}|\leq
t$, we consider the sum of indicator variables which each indicates whether a
vertex in $\phi_{r}(\widehat{X}_{i}^{H})\cap
N_{G_{B}-G_{h}^{\circ}}(\mathcal{S})$ is activated. By $\mathbf{S}(r)$(e), we
further have that

(6.47) $\displaystyle\big{|}(V_{i}\setminus\phi_{r}(\widehat{X}_{i}^{H}))\cap
N_{G_{B}}(\mathcal{S})\big{|}\leq{\varepsilon}_{T}\big{|}V_{i}\cap
N_{G_{B}}(\mathcal{S})\big{|}.$

Altogether, this implies (G)C6.1.

In order to establish (D)C6.1–(F)C6.1, we claim that if no identifier detected
alarm until turn $h\in[|\mathcal{H}|]$, then for all $i\in[r]$

(6.48) $\displaystyle\left|\textstyle\bigcup_{S\in\mathcal{S}}\left(V_{i}\cap
N_{G^{\circ}_{h}}(S)\cap N_{G_{B}}(\mathcal{S})\right)\right|$
$\displaystyle\leq\mu^{2/3}d_{B}^{|\mathcal{S}|}n\text{ for all
$\mathcal{S}\subseteq\textstyle\bigcup_{\mathscrs{r}\in E(R)\colon
i\in\mathscrs{r}}V_{\sqcup\mathscrs{r}\setminus\\{i\\}}$, $|\mathcal{S}|\leq
t$;}$ (6.49) $\displaystyle\rho^{H}_{G^{\circ}_{h}}(v)$
$\displaystyle\leq\mu^{2/3}d_{i}n\text{ for all $H\in\mathcal{H}$, $v\in
V_{i}$,}$

where $\rho^{H}_{G^{\circ}_{h}}(v)$ is defined as in (6.26). We verify (6.48)
and (6.49) in the subsequent Steps 6.1 and 6.1, respectively, and first
establish (D)C6.1–(F)C6.1 assuming (6.48) and (6.49).

To establish (F)C6.1, recall that $G_{B}$ is
$(2{\varepsilon}_{0},t,d_{B})$-typical with respect to $R$ by (6.4). Hence, we
obtain from (6.48) and the definition of typicality that $G_{B}-G^{\circ}_{h}$
is $(\mu^{1/2},t,d_{B})$-typical with respect to $R$, which implies (F)C6.1.

To establish (D)C6.1 for $H=H_{h+1}$, recall that $B_{i}^{H}$ is
$({\varepsilon}_{T},d_{i})$-super-regular and
$({\varepsilon}_{T},t^{2/3})$-well-intersecting with respect to $G_{B}$ for
all $i\in[r]$. Observe that there exists a set $\mathcal{S}_{x}$ for every
$x\in X_{i}^{H}$ with $|\mathcal{S}_{x}|\leq t^{2/3}$ and
$N_{B_{i}^{H}}(x)=V_{i}\cap N_{G_{B}}(\mathcal{S}_{x})$. By the definition of
$(B_{i}^{H})^{G_{h}^{\circ}}$ in (6.25), we have that
$N_{(B_{i}^{H})^{G^{\circ}_{h}}}(x)=V_{i}\cap
N_{G_{B}-G^{\circ}_{h}}(\mathcal{S}_{x})$. This together with (6.48), and
(6.49) together with (6.27), implies that we removed at most $\mu^{2/3}d_{i}n$
edges incident to every vertex to obtain $(B_{i}^{H})^{G_{h}^{\circ}}$ from
$B_{i}^{H}$. Now Fact 3.4 yields that $(B_{i}^{H})^{G_{h}^{\circ}}$ is
$(\mu^{1/5},d_{i})$-super-regular. This implies (D)C6.1.

To establish (E)C6.1 for $H=H_{h+1}$, we exploit that
$(B_{i}^{H})^{G_{h}^{\circ}}$ is $(\mu^{1/5},d_{i})$-super-regular and only
have to show that every vertex in
$(B_{i}^{H})^{G_{h}^{\circ}}[Y_{i}^{H},W_{i}^{H}]$ has the appropriate degree.
To that end, we consider the following random variables for all $x\in
X_{i}^{H}$, $v\in V_{i}$, $i\in[r]$. For $x$, we consider the random variable
that counts the number of activated vertices by $H$ in
$N_{(B_{i}^{H})^{G_{h}^{\circ}}}(x)$, and by employing (6.47) and that
$B_{i}^{H}$ is $({\varepsilon}_{T},t)$-well-intersecting with respect to
$G_{B}$, we expect that $N_{(B_{i}^{H})^{G_{h}^{\circ}}}(x)\cap W_{i}^{H}$ has
size $\mu|N_{(B_{i}^{H})^{G_{h}^{\circ}}}(x)|\pm 2{\varepsilon}_{T}d_{i}n$.
This yields the appropriate degree for $x$. For $v$, we consider the random
variable that counts the number of activated vertices in
$N_{(B_{i}^{H})^{G_{h}^{\circ}}}(v)$, and by employing Claim 6.1, we expect
that $N_{(B_{i}^{H})^{G_{h}^{\circ}}}(v)\cap Y_{i}^{H}$ has size
$\mu|N_{(B_{i}^{H})^{G_{h}^{\circ}}}(v)|\pm 2{\varepsilon}_{T}d_{i}n$. This
yields the appropriate degree for $v$. Altogether this implies (E)C6.1.

_Step 5.8. _ Probability to use a $G_{B}$-edge during the completion

We say an edge $\mathscrs{g}\in E(G_{B})$ is _used_ during the RPP if there
exists a graph $H_{h}\in\mathcal{H}$ and an edge $\mathscrs{e}\in H_{h}$ such
that $\phi^{h}(\mathscrs{e})=\mathscrs{g}$. In this step we show the following
claim that we will apply to establish (6.48) and (6.49) in Steps 6.1 and 6.1.

Claim 7.  For every edge $\mathscrs{g}\in E(G_{B})$, the probability that
$\mathscrs{g}$ is used during the RPP is at most $\mu^{3/4}$.  Proof of claim:
Let $\mathscrs{g}\in E(G_{B})$ and $\mathscrs{r}\in E(R)$ with
$\mathscrs{g}=\\{v_{i}\\}_{i\in\mathscrs{r}}\in
E(G_{B}[V_{\cup\mathscrs{r}}])$ be fixed. We consider different cases and sets
of $\mathcal{H}$-edges that could potentially be embedded onto $\mathscrs{g}$,
say in each case with probability at must $\mu^{4/5}$. In the end, a union
bound will establish Claim 6.1. Therefore, for all $m\in[k]$,
$J\in\binom{\mathscrs{r}}{m}$, we consider different sets of edges in
$\mathcal{H}[\mathscr{X}_{\cup{\mathscrs{r}}}]$ where the $m$ vertices
corresponding to the clusters in $J$ are either unembedded or activated and
can potentially be mapped onto $\\{v_{i}\\}_{i\in J}$, and where the remaining
$k-m$ vertices corresponding to the clusters in $\mathscrs{r}\setminus J$ have
already been embedded onto $\\{v_{i}\\}_{i\in\mathscrs{r}\setminus J}$. Let
$m\in[k]$ and $J\in\binom{\mathscrs{r}}{m}$ be fixed.

We first consider the set of $H$-edges
$\mathscrs{e}=\\{x_{i}\\}_{i\in\mathscrs{r}}$ for all $H\in\mathcal{H}$ where
no vertex of $\mathscrs{e}$ is left unembedded by $\phi_{r}$ and for every
vertex of $\mathscrs{g}$, there is an $H$-vertex that is mapped onto
$\mathscrs{g}$. That is, the $m$ vertices $\\{x_{i}\\}_{i\in J}$ as well as
the $m$ vertices $\\{v_{i}\\}_{i\in J}$ are activated, the vertices
$\\{x_{i}\\}_{i\in J}$ can potentially be mapped onto $\\{v_{i}\\}_{i\in J}$,
and $\phi_{r}(\\{x_{i}\\}_{i\in\mathscrs{r}\setminus
J})=\\{v_{i}\\}_{i\in\mathscrs{r}\setminus J}$. To that end, we first consider
the set
$\widetilde{E}:=E_{\phi_{r}}(\mathscrs{g},J,J_{X}=\emptyset,J_{V}=\emptyset)\setminus
E_{\phi_{r}}(\mathscrs{g},J,J_{X}=\emptyset,J_{V}\neq\emptyset)$ as defined in
(6.28). (Note that we defined this set in (6.28) only in the more convenient
way that $\mathscrs{g}\cap V_{\cup
J_{V}}\subseteq\mathscrs{g}\setminus\phi_{r}(X_{\cup\mathscrs{r}}^{H})$, which
is the reason why we remove the set
$E_{\phi_{r}}(\mathscrs{g},J,J_{X}=\emptyset,J_{V}\neq\emptyset)$ from the
current consideration.) For an edge
$\mathscrs{e}=\\{x_{i}\\}_{i\in\mathscrs{r}}\in\widetilde{E}$, in order that
$\\{x_{i}\\}_{i\in J}$ can be mapped onto $\\{v_{i}\\}_{i\in J}$ during the
completion, it must hold that the vertices $\\{x_{i}\\}_{i\in J}$ and the
vertices $\\{v_{i}\\}_{i\in J}$ must become activated. Since
$\phi_{r}(\mathscrs{x})\neq\mathscrs{g}$ and
$\phi_{r}(\\{x_{i}\\}_{i\in\mathscrs{r}\setminus
J})=\\{v_{i}\\}_{i\in\mathscrs{r}\setminus J}$, it holds that
$\phi_{r}(\\{x_{i}\\}_{i\in J})\neq\\{v_{i}\\}_{i\in J}$. Hence, the
probability that $\\{x_{i}\\}_{i\in J}$ and $\\{v_{i}\\}_{i\in J}$ become
activated is at most $\mu^{m+1}$ because every vertex in $\widehat{X}_{i}^{H}$
for all $i\in[r]$, $H\in\mathcal{H}$ is activated independently with
probability $\mu$. Further, by (K)C6.1, activated vertices $\\{x_{i}\\}_{i\in
J}$ are mapped onto $\\{v_{i}\\}_{i\in J}$ with probability at most
$2^{m}\prod_{i\in J}(\mu d_{i}n)^{-1}$. Altogether, this implies that that the
probability that some edge in $\widetilde{E}$ is mapped onto $\mathscrs{g}$ is
at most

$\displaystyle\mu^{m+1}2^{m}\prod_{i\in J}(\mu
d_{i}n)^{-1}\big{|}E_{\phi_{r}}\left(\mathscrs{g},J,J_{X}=\emptyset,J_{V}=\emptyset\right)\big{|}$
(6.50) $\displaystyle\stackrel{{\scriptstyle\text{Claim\leavevmode\nobreak\
\ref{claim:leftover for g}}}}{{\leq}}$
$\displaystyle\mu^{m+1}2^{m+1}\prod_{i\in J}(\mu
d_{i}n)^{-1}\cdot\gamma^{-1}n^{m}\prod_{i\in J}d_{i}\leq\mu^{4/5},$

where we used for the last inequality that $\mu\ll\gamma$.

Next, we consider the sets $E_{\phi_{r}}(\mathscrs{g},J,J_{X},J_{V})$ where
$J_{XV}=J_{X}\cup J_{V}$ is non-empty for disjoint $J_{X},J_{V}\subseteq J$.
For an edge $\mathscrs{e}=\\{x_{i}\\}_{i\in\mathscrs{r}}\in
E_{\phi_{r}}(\mathscrs{g},J,J_{X},J_{V})$, the vertices $\\{x_{i}\\}_{i\in J}$
are mapped onto $\\{v_{i}\\}_{i\in J}$ with probability at most
$2^{m}\prod_{i\in J}(\mu d_{i}n)^{-1}$ by (K)C6.1. This implies that the
probability that some edge in
$E_{\phi_{r}}(\mathscrs{g},J,J_{X}=\emptyset,J_{V})$ is mapped onto
$\mathscrs{g}$ is at most

$\displaystyle 2^{m}\prod_{i\in J}(\mu
d_{i}n)^{-1}\big{|}E_{\phi_{r}}\left(\mathscrs{g},J,J_{X},J_{V}\right)\big{|}$
(6.51) $\displaystyle\stackrel{{\scriptstyle\text{Claim\leavevmode\nobreak\
\ref{claim:leftover for g}}}}{{\leq}}$ $\displaystyle 2^{m}\prod_{i\in J}(\mu
d_{i}n)^{-1}\cdot{\varepsilon}_{T}^{1/2}n^{m}\prod_{i\in
J}d_{i}\leq{\varepsilon}_{T}^{1/3}.$

Now, Claim 6.1 is established by a union bound over all $m\in[k]$,
$J\in\binom{\mathscrs{r}}{m}$, and all possible sets $J_{X},J_{V}$ that we
considered to be fixed in (6.50) and (6.51).  $-$

_Step 5.9. _ Proof of Claim 6.1 – Bound in (6.48)

We use Claim 6.1 to verify the claimed bound in (6.48). We fix $i\in[r]$,
$\mathcal{S}\subseteq\bigcup_{\mathscrs{r}\in E(R)\colon
i\in\mathscrs{r}}V_{\sqcup\mathscrs{r}\setminus\\{i\\}}$ with
$|\mathcal{S}|\leq t$ and $S\in\mathcal{S}$. By Claim 6.1, each $G_{B}$-edge
is used with probability at most $\mu^{3/4}$ during the RPP, and thus, by an
application of Lemma 3.2, we have that $|V_{i}\cap N_{G^{\circ}_{h}}(S)\cap
N_{G_{B}}(\mathcal{S})|\leq\mu^{7/10}d_{B}^{|\mathcal{S}|}n$ with probability
at least, say, $1-{\rm e}^{-n^{3/4}}$. Otherwise we detect alarm. Together
with a union bound this implies the claimed bound in (6.48) because
$t\cdot\mu^{7/10}d_{B}^{|\mathcal{S}|}n\leq\mu^{2/3}d_{B}^{|\mathcal{S}|}n$.

_Step 5.10. _ Proof of Claim 6.1 – Bound for $\rho^{H}_{G^{\circ}_{h}}(v)$

We also use Claim 6.1 to verify the claimed bound for
$\rho^{H}_{G^{\circ}_{h}}(v)$ in (6.49). (Recall the definition of
$\rho_{G^{\circ}_{h}}^{H}(v)$ in (6.26).) For all $H\in\mathcal{H}$, $i\in[r]$
and $v\in V_{i}$, we have that $v$ has at most $(1+2{\varepsilon}_{T})d_{i}n$
neighbours in $B_{i}^{H}$. For each such neighbour $x\in N_{B_{i}^{H}}(v)$,
there exists a set $\mathcal{S}_{x}\subseteq\binom{V(G)}{k-1}$ with
$|\mathcal{S}_{x}|\leq t^{2/3}$ such that
$N_{B_{i}^{H}}(x)=N_{G_{B}}(\mathcal{S}_{x})$. Hence, there exist at most
$2t^{2/3}d_{i}n$ edges $\mathscrs{g}=S\cup\\{v\\}$ in $G_{B}$ for some
$S\in\bigcup_{x\in N_{B_{i}^{H}}(v)}\mathcal{S}_{x}$. By Claim 6.1, each such
$G_{B}$-edge $\mathscrs{g}$ is used with probability at most $\mu^{3/4}$
during the entire RPP. We therefore expect that for each $h\in[|\mathcal{H}|]$
at most $\mu^{3/4}2t^{2/3}d_{i}n$ edges incident to $v$ in $B_{i}^{H}$ have to
be removed when we obtain $(B_{i}^{H})^{G^{\circ}_{h}}$. Hence, by an
application of Lemma 3.2 and a union bound, we obtain that
$\rho_{G^{\circ}_{h}}^{H}(v)\leq\mu^{2/3}d_{i}n$ for all
$h\in[|\mathcal{H}|]$, $H\in\mathcal{H}$, $i\in[r]$, $v\in V_{i}$ with
probability at least, say, $1-{\rm e}^{-n^{3/4}}$. Otherwise we detect alarm.
This implies the claimed bound in (6.49).

_Step 5.11. _ Proof of Claim 6.1 – Establishing (iii) of Lemma 6.1

In order to establish conclusion (iii) of Lemma 6.1, let
$(\omega,\mathscrs{c})\in\mathcal{W}_{ver}$ with centres
$\mathscrs{c}=\\{c_{i}\\}_{i\in I}$ in $I$ be fixed. We split the proof into
two parts, depending on whether we activate a vertex of a tuple
$\mathscrs{x}\in\mathscr{X}_{\sqcup{I}}$ that $\phi_{r}$ already mapped onto
$\mathscrs{c}$, or whether a tuple $\mathscrs{x}\in\mathscr{X}_{\sqcup{I}}$
contains vertices in $\mathcal{X}_{r}\setminus\mathcal{X}_{r}^{\phi_{r}}$ and
$\mathscrs{x}$ is mapped onto $\mathscrs{c}$ during the completion.

Let us first consider tuples $\mathscrs{x}\in\mathscr{X}_{\sqcup{I}}$ that we
have already embedded onto $\mathscrs{c}$, that is,
$\phi_{r}(\mathscrs{x})=\mathscrs{c}$, and where some vertices of
$\mathscrs{x}$ become activated. We claim that during the entire RPP not too
many such tuples become activated. That is, we claim that

(6.52)
$\displaystyle\omega\left(\bigcup_{H\in\mathcal{H}}\left\\{\mathscrs{x}\in
X_{\sqcup I}^{H}\colon\phi_{r}(\mathscrs{x})=\mathscrs{c},\mathscrs{x}\cap
Y_{\cup
I}^{H}\neq\emptyset\right\\}\right)\leq\mu^{1/2}\omega(\phi_{r}^{-1}(\mathscrs{c}))+n^{{\varepsilon}_{T}},$

with high probability. To see (6.52), note that for every
$\mathscrs{x}\in\mathscr{X}_{\sqcup I}$, the probability that $\mathscrs{x}$
contains an activated vertex is at most $|I|\mu$. Hence, an application of
Theorem 3.1 and a union bound yield (6.52) with probability, say, at least
$1-{\rm e}^{-n^{{\varepsilon}}}$.

Next, we consider tuples $\mathscrs{x}\in\mathscr{X}_{\sqcup{I}}$ that have
not been embedded onto $\mathscrs{c}$ by $\phi_{r}$. To that end, we fix
$m\in[|I|]$ and $J\in\binom{I}{m}$, and a pair of disjoint sets
$J_{X},J_{V}\subseteq J$. We aim to control the $\omega$-weight on the tuples
in $E_{\phi_{r}}(\mathscrs{c},J,J_{X},J_{V})$ as defined in (6.28).
Analogously as in Claim 6.1, we can employ $\mathbf{S}(r)$(b) and (d) for the
edge testers that we defined for $(\omega,\mathscrs{c})$ in (6.5). Proceeding
as in Claim 6.1 yields that

(6.53)
$\displaystyle\omega\left(E_{\phi_{r}}(\mathscrs{c},J,J_{X},J_{V})\right)\leq\left(\mathbbm{1}\\{J_{XV}=\emptyset\\}+2{\varepsilon}_{T}\right)\prod_{i\in
J}d_{i}\frac{\omega(\mathscr{X}_{\sqcup{I}})}{n^{|I|-|J|}}+n^{2{\varepsilon}_{T}}.$

We can now proceed similarly as in the proof of Claim 6.1 in Step 6.1; that
is, we consider different cases and sets of tuples
$\mathscrs{x}\in\mathscr{X}_{\sqcup{I}}$ that could potentially be embedded
onto $\mathscrs{c}$, and derive an upper bound on the expected $\omega$-weight
used in such a case. In the end, a union bound over all these cases gives us
an upper bound on the total expected $\omega$-weight of tuples that are
embedded onto $\mathscrs{c}$ during the completion. Therefore, we consider
different choices for $J_{X},J_{V}\subseteq J$.

For $\mathscrs{x}=\\{x_{i}\\}_{i\in I}\in
E_{\phi_{r}}(\mathscrs{c},J,J_{X}=\emptyset,J_{V}=\emptyset)\setminus
E_{\phi_{r}}(\mathscrs{c},J,J_{X}=\emptyset,J_{V}\neq\emptyset)$, in order
that $\\{x_{i}\\}_{i\in J}$ can be mapped onto $\\{c_{i}\\}_{i\in J}$ during
the RPP, it must hold that the vertices $\\{x_{i}\\}_{i\in J}$ and
$\\{c_{i}\\}_{i\in J}$ become activated because $J_{V}=\emptyset$. Since
$\phi_{r}(\\{x_{i}\\}_{i\in J})\neq\\{c_{i}\\}_{i\in J}$, this happens with
probability at most $\mu^{m+1}$. Further, by (K)C6.1, the activated vertices
$\\{x_{i}\\}_{i\in J}$ are mapped onto $\\{c_{i}\\}_{i\in J}$ with probability
at most $2^{m}\prod_{i\in J}(\mu d_{i}n)^{-1}$. Altogether, this implies that
the expected weight of edges in
$E_{\phi_{r}}(\mathscrs{c},J,J_{X}=\emptyset,J_{V}=\emptyset)\setminus
E_{\phi_{r}}(\mathscrs{c},J,J_{X}=\emptyset,J_{V}\neq\emptyset)$ that are
mapped onto $\mathscrs{c}$ during the RPP is at most

$\displaystyle\mu^{m+1}2^{m}\prod_{i\in J}(\mu
d_{i}n)^{-1}\omega\left(E_{\phi_{r}}\left(\mathscrs{c},J,J_{X}=\emptyset,J_{V}=\emptyset\right)\right)$
(6.54) $\displaystyle\stackrel{{\scriptstyle\eqref{eq:weight leftover for
g}}}{{\leq}}$ $\displaystyle\mu^{m+1}2^{m}\prod_{i\in J}(\mu
d_{i}n)^{-1}\left(2\prod_{i\in
J}d_{i}\frac{\omega(\mathscr{X}_{\sqcup{I}})}{n^{|I|-|J|}}+n^{2{\varepsilon}_{T}}\right)\leq\mu^{4/5}\frac{\omega(\mathscr{X}_{\sqcup{I}})}{n^{|I|}}+n^{3{\varepsilon}_{T}}.$

Next, we consider the set $E_{\phi_{r}}(\mathscrs{c},J,J_{X},J_{V})$ for
disjoint but fixed $J_{X},J_{V}\subseteq J$ such that $J_{XV}=J_{X}\cup
J_{V}\neq\emptyset$. The vertices $\\{x_{i}\\}_{i\in J}$ are mapped onto
$\\{c_{i}\\}_{i\in J}$ with probability at most $2^{m}\prod_{i\in J}(\mu
d_{i}n)^{-1}$ by (K)C6.1. Hence, the expected weight of edges in
$E_{\phi_{r}}(\mathscrs{c},J,J_{X},J_{V})$ that are mapped onto $\mathscrs{c}$
during the RPP is at most

(6.55) $\displaystyle 2^{m}\prod_{i\in J}(\mu
d_{i}n)^{-1}\omega\left(E_{\phi_{r}}\left(\mathscrs{c},J,J_{X},J_{V}\right)\right)\stackrel{{\scriptstyle\eqref{eq:weight
leftover for
g}}}{{\leq}}{\varepsilon}_{T}^{1/2}\frac{\omega(\mathscr{X}_{\sqcup{I}})}{n^{|I|}}+n^{3{\varepsilon}_{T}}.$

Altogether, a union bound over all $m\in[|I|]$, $J\in\binom{I}{m}$, and all
sets $J_{X},J_{V}\subseteq J$ that we considered to be fixed in (6.54) and
(6.55) together with an application of Lemma 3.2 yields that

$\displaystyle\omega\left(\left\\{\mathscrs{x}\in\mathscr{X}_{\sqcup
I}\colon\phi_{r}(\mathscrs{x})\neq\mathscrs{c},\phi^{|\mathcal{H}|}(\mathscrs{x})=\mathscrs{c}\right\\}\right)\leq\mu^{1/2}\frac{\omega(\mathscr{X}_{\sqcup{I}})}{n^{|I|}}+n^{4{\varepsilon}_{T}}$

with probability at least, say, $1-{\rm e}^{-n^{2{\varepsilon}_{T}}}$.

Combining this with (6.52) yields

$\displaystyle\omega((\phi^{|\mathcal{H}|})^{-1}(\mathscrs{c}))$
$\displaystyle\stackrel{{\scriptstyle\hphantom{\text{$\mathbf{S}(r)$\ref{vertex
tester}}}}}{{=}}(1\pm\mu^{1/2})\omega(\phi_{r}^{-1}(\mathscrs{c}))\pm\mu^{1/2}\frac{\omega(\mathscr{X}_{\sqcup{I}})}{n^{|I|}}\pm
2n^{4{\varepsilon}_{T}}$
$\displaystyle\stackrel{{\scriptstyle\text{$\mathbf{S}(r)$\ref{vertex
tester}}}}{{=}}(1\pm\alpha)\frac{\omega(\mathscr{X}_{\sqcup{I}})}{n^{|I|}}\pm
n^{\alpha}.$

This establishes conclusion (iii) of Lemma 6.1 and completes the proof of
Claim 6.1.  $-$

_Step 5.12. _ Finishing the completion

As the RPP outputs $\phi^{|\mathcal{H}|}$ with positive probability by Claim
6.1, we obtain a packing $\phi:=\phi^{|\mathcal{H}|}$ of $\mathcal{H}$ into
$G$ which clearly satisfies conclusions (i) and (iii) of Lemma 6.1. Note that
by the construction of $\phi^{|\mathcal{H}|}$, we have that
$\phi|_{X_{i}^{H}}=\phi_{r}|_{X_{i}^{H}\setminus
Y_{i}^{H}}\cup\phi^{H}|_{Y_{i}^{H}}$ for all $H\in\mathcal{H}$, $i\in[r]$.
Since $|Y_{i}^{H}|=(1\pm{\varepsilon}_{T}^{1/2})\mu n$, we therefore merely
modified $\phi_{r}$ to obtain $\phi$ and thus, $\mathbf{S}(r)$(f) easily
implies conclusion (ii) of Lemma 6.1. This completes the proof of Lemma 6.1.
$\square$

##  7\. Proof of the main results

In this section we prove Theorem 1.5 and Theorem 1.6.

Proof of Theorem 1.5.  Our general approach is as follows. Given a blow-up
instance $(\mathcal{H},G,R,\mathcal{X},\mathcal{V})$, we refine the vertex
partition $\mathcal{X}$ of the graphs in $\mathcal{H}$ using Lemma 3.9 and we
randomly refine the vertex partition $\mathcal{V}$ of $G$ accordingly.
Afterwards we can apply Lemma 6.1 to obtain the required packing of
$\mathcal{H}$ into $G$.

Suppose $1/n\ll{\varepsilon}\ll 1/t\ll\beta\ll\alpha,1/k$ for a new parameter
$\beta$. For each $(W,Y_{1},\ldots,Y_{m})\in\mathcal{W}_{set}$ with
$W\subseteq V_{i}$, $i\in[r]$, and each $\ell\in[m]$, let
$\omega_{Y_{\ell}}\colon\bigcup_{H\in\mathcal{H}}X_{i}^{H}\to\\{0,1\\}$ be
such that $\omega_{Y_{\ell}}(x)=\mathbbm{1}{\\{x\in Y_{\ell}\\}}$, and let
$\mathcal{W}_{Y}$ be the set containing all those weight functions. Further,
for all $\mathscrs{r}\in E(R)$, let
$\omega{r}\colon\mathscr{X}_{\sqcup{\mathscrs{r}}}\to\\{0,1\\}$ be defined by
$\omega{r}(\mathscrs{x}):=\mathbbm{1}\\{\mathscrs{x}\in E(\mathcal{H})\\}$,
and let $\mathcal{W}_{\mathcal{H}}$ be the set containing all those weight
functions. We apply Lemma 3.9 to $\mathcal{H}$ with weight functions
$\\{\omega\colon(\omega,\mathscrs{c})\in\mathcal{W}_{ver}\\}\cup\mathcal{W}_{Y}\cup\mathcal{W}_{\mathcal{H}}$.
This yields a refined partition
$\mathcal{X}^{\prime}=(X_{i,j}^{H})_{H\in\mathcal{H},i\in[r],j\in[\beta^{-1}]}$
of $\mathcal{H}$ such that for all $H\in\mathcal{H}$ and $i\in[r]$, the
partitions $(X_{i,j}^{H})_{j\in[\beta^{-1}]}$ of $X_{i}^{H}$ satisfy the
conclusions (i)–(iv) of Lemma 3.9.

Let $R^{\prime}$ be the $k$-graph with vertex set $[r]\times[\beta^{-1}]$ and
edge set

$\left\\{\\{(i_{\ell},j_{\ell})\\}_{\ell\in[k]}\colon\\{i_{\ell}\\}_{\ell\in[k]}\in
E(R),j_{\ell}\in[\beta^{-1}]\right\\}.$

Note that $\Delta(R^{\prime})\leq\alpha^{-1}\beta^{-(k-1)}$ because
$\Delta(R)\leq\alpha^{-1}$. Let $n^{\prime}:=\beta n$.

Employing conclusion (iv) of Lemma 3.9 for the weight functions in
$\mathcal{W}_{\mathcal{H}}$ implies for all
$\\{(i_{\ell},j_{\ell})\\}_{\ell\in[k]}\in E(R^{\prime})$ with
$\mathscrs{r}:=\\{i_{\ell}\\}_{\ell\in[k]}\in E(R)$ that

$\displaystyle\sum_{H\in\mathcal{H}}e_{H}(X_{i_{1},j_{1}}^{H},\ldots,X_{i_{k},j_{k}}^{H})$
$\displaystyle\leq(1+{\varepsilon})\beta^{k}\omega{r}(\mathscr{X}_{\sqcup{\mathscrs{r}}})+n^{1+{\varepsilon}}$
$\displaystyle=(1+{\varepsilon})\beta^{k}e_{\mathcal{H}}(\mathscr{X}_{\sqcup{\mathscrs{r}}})+n^{1+{\varepsilon}}\leq(1-\alpha/2)dn^{\prime
k},$

because by assumption,
$e_{\mathcal{H}}(\mathscr{X}_{\sqcup{\mathscrs{r}}})\leq(1-\alpha)dn^{k}$ and
$d\geq n^{-{\varepsilon}}$.

Further, note that Lemma 3.9(i) implies for each $H\in\mathcal{H}$ that
$H[X_{\cup\mathscrs{r}}^{H}]$ is a matching if $\mathscrs{r}\in E(R^{\prime})$
and empty if $\mathscrs{r}\in\binom{[r]\times[\beta^{-1}]}{k}\setminus
E(R^{\prime})$.

According to the refinement $\mathcal{X}^{\prime}$ of $\mathcal{X}$, we claim
that there exists a refined partition
$\mathcal{V}^{\prime}=(V_{i,j})_{i\in[r],j\in[\beta^{-1}]}$ of $\mathcal{V}$,
where $(V_{i,j})_{j\in[\beta^{-1}]}$ is a partition of $V_{i}$ for every
$i\in[r]$ such that

  1. (a)

$|W\cap V_{i,j}|=\beta|W|\pm\beta^{3/2}n$ for all
$(W,Y_{1},\ldots,Y_{m})\in\mathcal{W}_{set}$ and $j\in[\beta^{-1}]$ with
$W\subseteq V_{i}$;

  2. (b)

$\mathscr{B}^{\prime}:=(\mathcal{H},G,R^{\prime},\mathcal{X}^{\prime},\mathcal{V}^{\prime})$
is an $({\varepsilon}^{1/2},t,d)$-typical, $\beta^{-k}$-bounded blow-up
instance of size $(n^{\prime},k,\beta^{-1}r)$ with $n^{\prime}=\beta n$.

The existence of such a partition $\mathcal{V}^{\prime}$ can be seen by a
probabilistic argument. For all $i\in[r]$ and $j\in[\beta^{-1}]$, we take
disjoint subset $V_{i,j}$ of $V_{i}$ of size exactly $|X_{i,j}^{H}|$ uniformly
and independently at random. We analyse the probability that (a) or (b) are
not satisfied. To that end, we consider the slightly different random
experiment where we assign for all $i\in[r]$, every vertex in $V_{i}$
uniformly and independently at random to some $V_{i,j}$ for
$j\in[\beta^{-1}]$. For this experiment and a fixed $i\in[r]$, we consider the
bad events that (a) or (b) are not satisfied; in such a case, we say the
experiment _fails_ (in step $i$). Standard properties of the multinomial
distribution yield that $|V_{i,j}|=|X_{i,j}^{H}|$ for all $j\in[\beta^{-1}]$,
$H\in\mathcal{H}$ with probability at least $\Omega(n^{-\beta^{-1}})$. Hence,
together with Theorem 3.1 and a union bound, this yields that the original
experiment fails in step $i$ with probability, say, at most ${\rm
e}^{-n^{1/2}}$. Since in fact we take $V_{i,j}$ of size exactly
$|X_{i,j}^{H}|$, this altogether implies the existence of a refined partition
$\mathcal{V}^{\prime}$ of $\mathcal{V}$ satisfying (a) and (b) with positive
probability.

We show how to adapt the vertex and set testers from the original blow-up
instance to the blow-up instance $\mathscr{B}^{\prime}$. For each
$(W,Y_{1},\ldots,Y_{m})\in\mathcal{W}_{set}$ and distinct
$H_{1},\ldots,H_{m}\in\mathcal{H}$ such that $W\subseteq V_{i}$ for some
$i\in[r]$ and $Y_{\ell}\subseteq X_{i}^{H_{\ell}}$ for all $\ell\in[m]$, we
define $(W_{j},Y_{1,j},\ldots,Y_{m,j})$ by setting $W_{j}:=W\cap V_{i,j}$ and
$Y_{\ell,j}:=Y_{\ell}\cap X_{i,j}^{H_{\ell}}$ for all
$j\in[\beta^{-1}],\ell\in[m]$. By (a), we conclude that
$|W_{j}|=\beta|W|\pm\beta^{3/2}n$. Employing conclusion (iii) of Lemma 3.9 for
the weight function $\omega_{Y_{\ell}}\in\mathcal{W}_{Y}$, we have that

(7.1)
$\displaystyle|Y_{\ell,j}|=\omega_{Y_{\ell}}(X_{i,j}^{H_{\ell}})=\beta\omega_{Y_{\ell}}(X_{i}^{H_{\ell}})\pm\beta^{3/2}n=\beta|Y_{\ell}|\pm\beta^{3/2}n.$

Let $\mathcal{W}_{set}^{\prime}:=\\{(W_{j},Y_{1,j},\ldots,Y_{m,j})\colon
j\in[\beta^{-1}],(W,Y_{1},\ldots,Y_{m})\in\mathcal{W}_{set}\\}$. For each
$(\omega,\mathscrs{c})\in\mathcal{W}_{ver}$ with centres
$\mathscrs{c}=\\{c_{i}\\}_{i\in I}$ in $I\subseteq[r]$ and multiset
$\\{j_{i}\\}_{i\in I}\subseteq[\beta^{-1}]$ such that $c_{i}\in V_{i,j_{i}}$
for each $i\in I$, let
$\omega^{\prime}:=\omega|_{\bigcup_{H\in\mathcal{H},i\in I}X_{i,j_{i}}^{H}}$
and
$\mathcal{W}_{ver}^{\prime}:=\\{(\omega^{\prime},\mathscrs{c})\colon(\omega,\mathscrs{c})\in\mathcal{W}_{ver}\\}$.

Hence, we can apply Lemma 6.1 to $\mathscr{B}^{\prime}$ with set testers
$\mathcal{W}_{set}^{\prime}$ and vertex testers $\mathcal{W}_{ver}^{\prime}$
as follows:

parameter | $n^{\prime}$ | ${\varepsilon}^{1/2}$ | $t$ | $\beta^{k}$ | $d$ | $r\beta^{-1}$
---|---|---|---|---|---|---
plays the role of | $n$ | ${\varepsilon}$ | $t$ | $\alpha$ | $d$ |  $r$ (

This yields a packing of $\mathcal{H}$ into $G$ such that

  1. (I)

$\phi(X_{i,j}^{H})=V_{i,j}$ for all $i\in[r]$, $j\in[\beta^{-1}]$,
$H\in\mathcal{H}$;

  2. (II)

$|W_{j}\cap\bigcap_{\ell\in[m]}\phi(Y_{\ell,j})|=|W_{j}||Y_{1,j}|\cdots|Y_{m,j}|/n^{\prime
m}\pm{\beta^{k}}n^{\prime}$ for all
$(W_{j},Y_{1,j},\ldots,Y_{\ell,j})\in\mathcal{W}_{set}^{\prime}$;

  3. (III)

$\omega^{\prime}(\phi^{-1}(\mathscrs{c})))=(1\pm\beta^{k})\omega^{\prime}(\bigcup_{H\in\mathcal{H}}(\bigsqcup_{i\in
I}X_{i,j_{i}}^{H}))/n^{\prime|I|}\pm n^{\prime\beta^{k}}$ for all
$(\omega^{\prime},\mathscrs{c})\in\mathcal{W}_{ver}^{\prime}$ with centres
$\mathscrs{c}=\\{c_{i}\\}_{i\in I}$ in $I\subseteq[r]$ and multiset
$\\{j_{i}\\}_{i\in I}\subseteq[\beta^{-1}]$ such that $c_{i}\in V_{i,j_{i}}$
for each $i\in I$.

For $(W,Y_{1},\ldots,Y_{m})\in\mathcal{W}_{set}$, we conclude that

$\displaystyle\textstyle\left|W\cap\bigcap_{\ell\in[m]}\phi(Y_{\ell})\right|$
$\displaystyle\stackrel{{\scriptstyle\hphantom{\rm\ref{item:II},\ref{item:refined
W},\eqref{eq:size
Y_l,j}}}}{{=}}\sum_{j\in[\beta^{-1}]}\textstyle\left|W_{j}\cap\bigcap_{\ell\in[m]}\phi(Y_{\ell,j})\right|$
$\displaystyle\stackrel{{\scriptstyle\rm\ref{item:II},\ref{item:refined
W},\eqref{eq:size
Y_l,j}}}{{=}}\sum_{j\in[\beta^{-1}]}\left(\frac{\beta^{m+1}\left(|W||Y_{1}|\cdots|Y_{m}|\pm\beta^{1/3}n^{m+1}\right)}{(\beta
n)^{m}}\pm{\beta^{k}}n^{\prime}\right)$
$\displaystyle\stackrel{{\scriptstyle\hphantom{\rm\ref{item:II},\ref{item:refined
W},\eqref{eq:size Y_l,j}}}}{{=}}|W||Y_{1}|\cdots|Y_{m}|/n^{m}\pm\alpha n.$

This establishes Theorem 1.5(i).

In order to establish Theorem 1.5(ii), we fix
$(\omega,\mathscrs{c})\in\mathcal{W}_{ver}$ with centres
$\mathscrs{c}=\\{c_{i}\\}_{i\in I}$ for $I\subseteq[r]$ and multiset
$\\{j_{i}\\}_{i\in I}\subseteq[\beta^{-1}]$ such that $c_{i}\in V_{i,j_{i}}$
for each $i\in I$, and we fix the corresponding tuple
$(\omega^{\prime},\mathscrs{c})\in\mathcal{W}_{ver}^{\prime}$. We conclude
that

$\displaystyle\omega(\phi^{-1}(\mathscrs{c}))$
$\displaystyle\stackrel{{\scriptstyle\rm\ref{item:I}}}{{=}}\leavevmode\nobreak\
\omega^{\prime}(\phi^{-1}(\mathscrs{c}))\stackrel{{\scriptstyle\rm\ref{item:III}}}{{=}}(1\pm\beta^{k})\frac{\omega^{\prime}\left(\bigcup_{H\in\mathcal{H}}\left(\bigsqcup_{i\in
I}X_{i,j_{i}}^{H}\right)\right)}{n^{\prime|I|}}\pm n^{\prime\beta^{k}}$
$\displaystyle\stackrel{{\scriptstyle\hphantom{\rm\ref{item:split
weights}}}}{{=}}(1\pm\beta^{k})\frac{\omega\left(\bigcup_{H\in\mathcal{H}}\left(\bigsqcup_{i\in
I}X_{i,j_{i}}^{H}\right)\right)}{n^{\prime|I|}}\pm n^{\prime\beta^{k}}$
$\displaystyle\stackrel{{\scriptstyle{\rm\ref{item:split
weights}}}}{{=}}(1\pm\beta^{k})\frac{(1\pm{\varepsilon})\beta^{|I|}\omega(\mathscr{X}_{\sqcup{I}})\pm
n^{1+{\varepsilon}}}{(\beta n)^{|I|}}\pm
n^{\prime\beta^{k}}=(1\pm\alpha)\omega(\mathscr{X}_{\sqcup{I}})/n^{|I|}\pm
n^{\alpha},$

where we employed conclusion (iv) of Lemma 3.9 in the penultimate equation.
This establishes Theorem 1.5(ii) and completes the proof.  $\square$

We now proceed to the proof of Theorem 1.6. The highlevel strategy is similar
as in the proof of Theorem 1.5. Additionally, we group the hypergraphs in
$\mathcal{H}$ into $P=\operatorname{polylog}n$ many collections of hypergraphs
$\mathcal{H}_{1},\ldots,\mathcal{H}_{P}$ and accordingly we partition the edge
set of the host graph $G$ into $G_{1},\ldots,G_{P}$ subgraphs. Afterwards, we
partition the vertex sets of the graphs in $\mathcal{H}$ via Lemma 3.10 and
randomly partition the vertex set of each $G_{p}$ for $p\in[P]$ accordingly.
Then, we can iteratively apply Lemma 6.1 for each $p\in[P]$ to map
$\mathcal{H}_{p}$ into $G_{p}$. Note that this yields a packing of
$\mathcal{H}$ into $G$, and considering $P=\operatorname{polylog}n$ partitions
enables us to establish conclusions (i) and (ii) of Theorem 1.6.

Proof of Theorem 1.6.  We set $P:=\log^{t}n$ and suppose
$1/n\ll{\varepsilon}\ll 1/t\ll\beta\ll\alpha,1/k$ for a new parameter $\beta$.

First, we group the graphs in $\mathcal{H}$ into $P$ collections
$\mathcal{H}_{1},\ldots,\mathcal{H}_{P}$ with roughly equally many edges. That
is, we claim that there exists a partition of $\mathcal{H}$ into $P$
collections of graphs $\mathcal{H}_{1},\ldots,\mathcal{H}_{P}$ such that each
$H\in\mathcal{H}$ belongs to exactly one $\mathcal{H}_{p}$ for $p\in[P]$, and
for each $p\in[P]$, we have

(7.2) $\displaystyle
e(\mathcal{H}_{p})\leq(1+{\varepsilon})P^{-1}e(\mathcal{H})+n^{1+{\varepsilon}},$

and for every $\omega\in\mathcal{W}_{ver}$ with $\omega(V(\mathcal{H}))\geq
n^{1+{\varepsilon}}$ and each $p\in[P]$, we have

(7.3)
$\displaystyle\omega(V(\mathcal{H}_{p}))=(1\pm{\varepsilon})P^{-1}\omega(V(\mathcal{H})).$

The existence of $\mathcal{H}_{1},\ldots,\mathcal{H}_{P}$ can be easily seen
by assigning every graph $H\in\mathcal{H}$ to one collection $\mathcal{H}_{p}$
for $p\in[P]$ uniformly and independently at random.

We now aim to apply Lemma 3.10 to each $\mathcal{H}_{p}$. Let $p\in[P]$ be
fixed. For each $(W,Y_{1},\ldots,Y_{m})\in\mathcal{W}_{set}$ and each
$\ell\in[m]$ such that $Y_{\ell}\subseteq V(H_{\ell})$ for
$H_{\ell}\in\mathcal{H}_{p}$, let $\omega_{Y_{\ell}}\colon
V(H_{\ell})\to\\{0,1\\}$ be such that
$\omega_{Y_{\ell}}(x)=\mathbbm{1}{\\{x\in Y_{\ell}\\}}$, and let
$\mathcal{W}_{Y}$ be the set containing all those weight functions. Further,
let
$\omega_{edges}\colon\bigcup_{H\in\mathcal{H}}\binom{V(H)}{k}_{\prec}\to\\{0,1\\}$
be defined by
$\omega_{edges}((x_{1},\ldots,x_{k})):=\mathbbm{1}\\{\\{x_{1},\ldots,x_{k}\\}\in
E(\mathcal{H}_{p})\\}$, and let $\mathcal{W}_{\mathcal{H}_{p}}$ be the set
containing all those weight functions. We apply Lemma 3.10 to
$\mathcal{H}_{p}$ with weight functions $\\{\omega|_{\cup
V(\mathcal{H}_{p})}\colon(\omega,\mathscrs{c})\in\mathcal{W}_{ver}\\}\cup\mathcal{W}_{Y}\cup\mathcal{W}_{\mathcal{H}_{p}}$.
This yields a partition
$\mathcal{X}_{p}=(X_{j}^{H})_{H\in\mathcal{H}_{p},j\in[\beta^{-1}]}$ of
$\mathcal{H}_{p}$ such that for all $H\in\mathcal{H}_{p}$, the partitions
$(X_{j}^{H})_{j\in[\beta^{-1}]}$ of $V(H)$ satisfy the conclusions (i)–(iv) of
Lemma 3.10.

For each $p\in[P]$, let $R_{p}$ be the $k$-graph with vertex set
$[\beta^{-1}]$ and $\mathscrs{r}\in\binom{[\beta^{-1}]}{k}$ is an edge in
$R_{p}$ if $H[X_{\sqcup\mathscrs{r}}^{H}]$ is non-empty for some
$H\in\mathcal{H}_{p}$. Clearly, $\Delta(R_{p})\leq\beta^{-k}$. Let
$n^{\prime}:=\beta n$.

Employing conclusion (iv) of Lemma 3.10 for the weight functions in
$\mathcal{W}_{\mathcal{H}_{p}}$ yields for all
$\mathscrs{r}=\\{i_{1},\ldots,i_{k}\\}\in E(R_{p})$ that

$\displaystyle\sum_{H\in\mathcal{H}_{p}}e_{H}(X_{\sqcup\mathscrs{r}}^{H})$
$\displaystyle=\omega_{edges}(\textstyle\bigcup_{H\in\mathcal{H}_{p}}(X_{i_{1}}^{H}\times\ldots\times
X_{i_{k}}^{H}))\leq(1+\beta^{1/2})\beta^{k}\omega_{edges}(V(\mathcal{H}_{p}))+n^{1+{\varepsilon}}$
(7.4)
$\displaystyle=(1+\beta^{1/2})\beta^{k}k!e(\mathcal{H}_{p})+n^{1+{\varepsilon}}\stackrel{{\scriptstyle\eqref{eq:edges
sliced Hs}}}{{\leq}}(1-\alpha/2)P^{-1}dn^{\prime k}$

because by assumption, $e(\mathcal{H})\leq(1-\alpha)e(G)$.

Now, we want to prepare $G$ accordingly to
$\mathcal{H}_{1},\ldots,\mathcal{H}_{P}$ and their partitions. To that end, we
first partition $G$ into $P$ edge-disjoint spanning subgraphs
$G_{1},\ldots,G_{P}$ such that $G_{p}$ is
$({\varepsilon}^{1/2},t,P^{-1}d)$-typical for every $p\in[P]$. The existence
of $G_{1},\ldots,G_{P}$ can be seen by assigning every edge in $G$ to one
subgraph $G_{p}$ for $p\in[P]$ uniformly and independently at random.

Further, we claim that there exist partitions
$\mathcal{V}_{p}=(V_{j})_{j\in[\beta^{-1}]}$ of $V(G_{p})$ according to the
partition $\mathcal{X}_{p}$ of $\mathcal{H}_{p}$, such that for every
$p\in[P]$ and $\mathcal{V}_{p}=(V_{j})_{j\in[\beta^{-1}]}$, we have

  1. (a)

$|W\cap V_{j}|=\beta|W|\pm\beta^{3/2}n$ for all
$(W,Y_{1},\ldots,Y_{m})\in\mathcal{W}_{set}$ and $j\in[\beta^{-1}]$,

  2. (b)

$\mathscr{B}_{p}:=(\mathcal{H}_{p},G_{p},R_{p},\mathcal{X}_{p},\mathcal{V}_{p})$
is an $({\varepsilon}^{1/2},t,P^{-1}d)$-typical, $\beta^{-k}$-bounded blow-up
instance of size $(n^{\prime},k,\beta^{-1})$ with $n^{\prime}=\beta n$,

as well as

  1. (c)

$\sum_{p\in[P]\colon\text{centres
collide}}\omega(V(\mathcal{H}_{p}))\leq\beta^{1/2}\omega(V(\mathcal{H}))$ for
all $(\omega,\mathscrs{c})\in\mathcal{W}_{ver}$ with
$\omega(V(\mathcal{H}))\geq n^{1+{\varepsilon}}$, where we say that the
_centres $\mathscrs{c}$ collide (with respect to $\mathcal{V}_{p}$)_ if
$|\mathscrs{c}\cap V_{j}|\geq 2$ for some $V_{j}\in\mathcal{V}_{p}$.

The existence of such partitions $\mathcal{V}_{p}$ can be seen by assigning
for every $p\in[P]$, every vertex to some $V_{j}$ for $j\in[\beta^{-1}]$
uniformly and independently at random. Theorem 3.1 and a union bound establish
(a) with probability, say, at least $1-{\rm e}^{-n^{1/2}}$. For (b), note that
standard properties of the multinomial distribution yield for $p\in[P]$ that
$|V_{j}|=|X_{j}^{H}|$ for all $j\in[\beta^{-1}]$ and $H\in\mathcal{H}$ with
probability at least $\Omega(n^{-\beta^{-1}})$. For (c), note that for
$p\in[P]$, the probability that the centres $\mathscrs{c}$ collide with
respect to $\mathcal{V}_{p}$ is at most $k^{2}\beta$. By (7.3), we therefore
expect that at most $\sum_{p\in[P]}k^{2}\beta\omega(V(\mathcal{H}_{p}))\leq
2k^{2}\beta\omega(V(\mathcal{H}))$ weight of $\omega$ collides in (c). Since
$P$ grows sufficiently fast in terms of $n$, we can establish concentration.
That is, Theorem 3.1 and a union bound that yield (c) with probability, say,
at least $1-n^{-\log n}$. Hence, a final union bound yields the existence of
these partitions $\mathcal{V}_{p}$ for $p\in[P]$ satisfying (a)–(c) with
positive probability.

Next, we iteratively apply Lemma 6.1 to $\mathscr{B}_{p}$ for $p\in[P]$ which
yields a packing $\phi_{p}$ of $\mathcal{H}_{p}$ into $G_{p}$. Let us first
explain how we adapt the vertex and set testers from the original blow-up
instance to the blow-up instance $\mathscr{B}_{p}$.

For $p\in[P]$, we define

$\displaystyle\mathcal{W}_{ver}(p):=\Big{\\{}(\omega_{p},\mathscrs{c})\colon$
$\displaystyle(\omega,\mathscrs{c})\in\mathcal{W}_{ver},\text{ centres
$\mathscrs{c}=\\{c_{i}\\}_{i\in I}$ do not collide with respect to
$\mathcal{V}_{p}$,}$
$\displaystyle\omega_{p}:=\omega|_{\bigcup_{H\in\mathcal{H}_{p},i\in
I}X_{j_{i}}^{H}}\Big{\\}},$

where we define $\\{j_{i}\\}_{i\in I}\subseteq[\beta^{-1}]$ as the indices
such that $c_{i}\in V_{j_{i}}$ for centres $\mathscrs{c}=\\{c_{i}\\}_{i\in I}$
that do not collide with respect to
$\mathcal{V}_{p}=(V_{j})_{j\in[\beta^{-1}]}$.

For all $j\in[\beta^{-1}]$, $(W,Y_{1},\ldots,Y_{m})\in\mathcal{W}_{set}$ and
distinct $H_{1},\ldots,H_{m}\in\mathcal{H}$ such that $Y_{\ell}\subseteq
V(H_{\ell})$, we define $Y_{\ell,j}:=Y_{\ell}\cap X_{j}^{H_{\ell}}$ for each
$\ell\in[m]$. For $j\in[\beta^{-1}],p\in[P]$, we define

$\displaystyle\mathcal{W}_{set}(j,p):=\Big{\\{}\big{(}W_{j}(p),\\{Y_{\ell,j}\\}_{\ell\in[m]\colon
Y_{\ell,j}\subseteq
V(\mathcal{H}_{p})}\big{)}\colon(W,Y_{1},\ldots,Y_{m})\in\mathcal{W}_{set},\leavevmode\nobreak\
Y_{\cup[m]}\cap V(\mathcal{H}_{p})\neq\emptyset\Big{\\}},$

where we define $W_{j}(p)$ for $(W,Y_{1},\ldots,Y_{m})\in\mathcal{W}_{set}$
recursively by

$W_{j}(p):=W_{j}(p-1)\cap\bigcap_{\ell\in[m]\colon Y_{\ell,j}\subseteq
V(\mathcal{H}_{p-1})}\phi_{p-1}(Y_{\ell,j})$

with $\phi_{0}$ being the empty function and thus, $W_{j}(1)=W_{j}(0):=W\cap
V_{j}$. By (a), we have that $|W\cap V_{j}|=\beta|W|\pm\beta^{3/2}n$. By
employing conclusion (iii) of Lemma 3.10 for the weight function
$\omega_{Y_{\ell}}\in\mathcal{W}_{Y}$, we have that

(7.5)
$\displaystyle|Y_{\ell,j}|=\omega_{Y_{\ell}}(X_{j}^{H_{\ell}})\stackrel{{\scriptstyle\ref{item:split'
weights one H,
|I|=1}}}{{=}}\beta\omega_{Y_{\ell}}(V({H_{\ell}}))\pm\beta^{3/2}n=\beta|Y_{\ell}|\pm\beta^{3/2}n.$

Hence, we iteratively apply Lemma 6.1 for every $p\in[P]$ to $\mathscr{B}_{p}$
with set testers $\bigcup_{j\in[\beta^{-1}]}\mathcal{W}_{set}(j,p)$ and vertex
testers $\mathcal{W}_{ver}(p)$ as follows:

parameter | $n^{\prime}$ | ${\varepsilon}^{1/2}$ | $t$ | $\beta^{k}$ | $P^{-1}d$ | $\beta^{-1}$
---|---|---|---|---|---|---
plays the role of | $n$ | ${\varepsilon}$ | $t$ | $\alpha$ | $d$ |  $r$ (

For every $p\in[P]$, this yields a packing $\phi_{p}$ of $\mathcal{H}_{p}$
into $G_{p}$ such that

  1. (I)

$\phi_{p}(X_{j}^{H})=V_{j}$ for all $j\in[\beta^{-1}]$, $H\in\mathcal{H}_{p}$;

  2. (II)

$|W_{j}(p)\cap\bigcap_{\ell\in[m]\colon Y_{\ell,j}\subseteq
V(\mathcal{H}_{p})}\phi_{p}(Y_{\ell,j})|=|W_{j}(p)|\prod_{\ell\in[m]\colon
Y_{\ell,j}\subseteq
V(\mathcal{H}_{p})}n^{\prime-1}|Y_{\ell,j}|\pm\beta^{k}n^{\prime}$ for all
$(W_{j}(p),\\{Y_{\ell,j}\\}_{\ell\in[m]\colon Y_{\ell}\subseteq
V(\mathcal{H}_{p})})\in\mathcal{W}_{set}(j,p)$, $j\in[\beta^{-1}]$;

  3. (III)

$\omega_{p}(\phi_{p}^{-1}(\mathscrs{c})))=(1\pm\beta^{k})\omega_{p}(\bigcup_{H\in\mathcal{H}_{p}}(\bigsqcup_{i\in
I}X_{j_{i}}^{H}))/n^{\prime|I|}\pm n^{\prime\beta^{k}}$ for all
$(\omega_{p},\mathscrs{c})\in\mathcal{W}_{ver}(p)$ with centres
$\mathscrs{c}=\\{c_{i}\\}_{i\in I}$ that do not collide with respect to
$\mathcal{V}_{p}$ and $\\{j_{i}\\}_{i\in I}\subseteq[\beta^{-1}]$ such that
$c_{i}\in V_{j_{i}}$ for each $i\in I$.

Let $\phi:=\bigcup_{p\in[P]}\phi_{p}$ and note that $\phi$ is a packing of
$\mathcal{H}$ into $G$.

For $(W,Y_{1},\ldots,Y_{m})\in\mathcal{W}_{set}$, we conclude that

$\displaystyle\textstyle\left|W\cap\bigcap_{\ell\in[m]}\phi(Y_{\ell})\right|$
$\displaystyle\stackrel{{\scriptstyle\hphantom{\rm\ref{item:refined
W},\eqref{eq:size Y_l,j
r=1}}}}{{=}}\sum_{j\in[\beta^{-1}]}\textstyle\left|W_{j}(P)\cap\bigcap_{\ell\in[m]\colon
Y_{\ell,j}\subseteq V(\mathcal{H}_{P})}\phi_{P}(Y_{\ell,j})\right|$
$\displaystyle\stackrel{{\scriptstyle\rm\leavevmode\nobreak\
\leavevmode\nobreak\ \ref{item:II r=1}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
}}{{=}}\sum_{j\in[\beta^{-1}]}\left(|W_{j}(0)||Y_{1,j}|\cdots|Y_{m,j}|/n^{\prime
m}\pm m\beta^{k}n^{\prime}\right)$
$\displaystyle\stackrel{{\scriptstyle\rm\ref{item:refined W
r=1},\eqref{eq:size Y_l,j r=1}}}{{=}}|W||Y_{1}|\cdots|Y_{m}|/n^{m}\pm\alpha
n.$

This establishes Theorem 1.6(i).

In order to establish Theorem 1.6(ii), we fix
$(\omega,\mathscrs{c})\in\mathcal{W}_{ver}$ with centres
$\mathscrs{c}=\\{c_{i}\\}_{i\in I}$. Recall that ${\rm supp}(\omega)\subseteq
E(\mathcal{H})$ for $|I|\geq 2$, and thus, if the centres $\mathscrs{c}$
collide with respect to one of the partitions $\mathcal{V}_{p}$, then
$\omega(\phi_{p}^{-1}(\mathscrs{c}))=0$. Therefore, we can consider the
corresponding tuples $(\omega_{p},\mathscrs{c})\in\mathcal{W}_{ver}(p)$ for
$p\in[P]$ and conclude that

$\displaystyle\allowdisplaybreaks\omega(\phi^{-1}(\mathscrs{c}))$
$\displaystyle\stackrel{{\scriptstyle\hphantom{\rm\ref{item:III
r=1}}}}{{=}}\sum_{p\in[P]}\omega(\phi_{p}^{-1}(\mathscrs{c}))=\sum_{p\in[P]\colon\text{no
collision}}\omega_{p}(\phi_{p}^{-1}(\mathscrs{c}))$
$\displaystyle\allowdisplaybreaks\stackrel{{\scriptstyle\rm\ref{item:III
r=1}}}{{=}}\sum_{p\in[P]\colon\text{no
collision}}\left((1\pm\beta^{k})\frac{\omega_{p}(\bigcup_{H\in\mathcal{H}_{p}}(\bigsqcup_{i\in
I}X_{j_{i}}^{H}))}{n^{\prime|I|}}\pm n^{\prime\beta^{k}}\right)$
$\displaystyle\allowdisplaybreaks\stackrel{{\scriptstyle\rm\ref{item:split'
weights}}}{{=}}\sum_{p\in[P]\colon\text{no
collision}}\left((1\pm\beta^{k})\frac{(1\pm\beta^{1/2})\beta^{|I|}\omega(V(\mathcal{H}_{p}))}{n^{\prime|I|}}\pm
n^{\prime\beta^{k}}\right)$
$\displaystyle\stackrel{{\scriptstyle\leavevmode\nobreak\ \rm\ref{item:centres
collide}\leavevmode\nobreak\
}}{{=}}(1\pm\alpha)\frac{\omega(V(\mathcal{H}))}{n^{|I|}}\pm n^{\alpha}.$

This establishes Theorem 1.6(ii) and completes the proof.  $\square$

##  8\. Concluding remarks

In this paper we have proved a functional tool that allows for approximate
decompositions of (sparse) (multipartite) quasirandom $k$-graphs into any
collection of spanning bounded degree $k$-graphs (with slightly fewer edges).
Our main result extends the strong decomposition result due to Kim, Kühn,
Osthus and Tyomkyn into two directions, both from the dense to the sparse
regime and from graphs to hypergraphs. It thereby answers Question 1.1 of
Keevash, and Kim, Kühn, Osthus and Tyomkyn and Question 1.2 of Kim, Kühn,
Osthus and Tyomkyn.

We conclude with a selection of immediate applications of Theorem 1.3
including an asymptotic solution to a hypergraph Oberwolfach problem asked by
Glock, Kühn and Osthus [21]. We first consider several natural hypergraph
analogues of graph decomposition questions and then turn to problems
concerning simplicial complexes. Along the way we state a few conjectures and
open problems. We also believe that our main results will have further
significantly more complex applications in the future.

###  8.1. Applications to hypergraph decompositions

As we pointed out in the introduction, the Conjectures (I)–(III) intrigued
mathematicians for decades. In the following we propose several conjectures of
similar spirit for $k$-graphs. Our main results imply approximate versions
thereof.

Recall that the Oberwolfach problem in (III) asks for a decomposition of
$K_{n}$ into $(n-1)/2$ copies of a graph on $n$ vertices that is the disjoint
union of cycles. There are many definitions for cycles in $k$-graphs and tight
cycles are among the most well studied cycles. A $k$-graph is a tight cycle if
its vertex set can be cyclically ordered and the edge set consists of all
$k$-sets that appear consecutively in this ordering. We refer to the number of
vertices in a tight cycle as its length. One potential version of a hypergraph
Oberwolfach problem has recently been asked by Glock, Kühn and Osthus.

######  Conjecture 8.1 (Hypergraph Oberwolfach problem; Glock, Kühn and Osthus
[21]).

Let $k\geq 3$ and suppose $n$ is sufficiently large in terms of $k$ and $k$
divides $\binom{n-1}{k-1}$. Suppose $F$ is a $k$-graph on $n$ vertices that is
the disjoint union of tight cycles each of length at least $2k-1$. Then there
is a decomposition of $K_{n}^{(k)}$ into copies of $F$.

Clearly, Theorem 1.3 yields an approximate solution of Conjecture 8.1.

We think that an even stronger result is true.

######  Conjecture 8.2 (Hypergraph Oberwolfach problem).

Let $k\geq 3$ and suppose $n$ is sufficiently large in terms of $k$ and $k$
divides $\binom{n-1}{k-1}$. Suppose $F$ is a $k$-graph on $n$ vertices that is
the disjoint union of tight cycles each of length at least $k+2$. Then there
is a decomposition of $K_{n}^{(k)}$ into copies of $F$.

Observe that Conjecture 8.1 includes the natural generalization of Walecki’s
theorem to hypergraphs, namely decompositions into Hamilton cycles. This has
already been conjectured by Bailey and Stevens [6] (and when $n$ and $k$ are
coprime by Baranyai [8] and independently by Katona) and there are a few
results that provide approximate decompositions of quasirandom graphs into
Hamilton cycles (of various types); see for example [7, 16, 17].

Whenever we allow cycles of length $k+1$ and the cycle factor consists
(essentially) of cycles of length $k+1$, we suspect that there are more
divisibility obstructions present. Hence we pose the following problem.

######  Problem 8.3 (Hypergraph Oberwolfach problem).

Let $k\geq 3$ and suppose $n$ is sufficiently large in terms of $k$ and $k$
divides $\binom{n-1}{k-1}$. Which disjoint unions of tight cycles whose length
add up to $n$ admit a decomposition of $K_{n}^{(k)}$?

It immediately follows from Theorem 1.3 that the hypergraph Oberwolfach
problems are approximately true in a sense that $K_{n}^{(k)}$ contains
$(1-o(1))\binom{n-1}{k-1}/k$ disjoint copies of $F$ (for any choice of $F$ as
above); in fact, we can we take any collection of $(1-o(1))\binom{n-1}{k-1}/k$
cycle factors.

Similarly as for cycles, there is more then one notion for trees in
$k$-graphs. Let us stick to the following recursive definition of tree to
which we refer as a $k$-tree. A single edge is a $k$-tree. A $k$-tree with
$\ell$ edges can be constructed from a $k$-tree with $\ell-1$ edges $T$ by
adding a vertex $v$ and an edge that contains $v$ and a $(k-1)$-set that is
contained in an edge of $T$. For this definition, we propose the following
generalization of Ringel’s conjecture.

######  Conjecture 8.4.

Let $k,n\in\mathbb{N}\setminus\\{1\\}$. Suppose $T$ is a $k$-tree with $n$
edges. Then $K_{kn+k-1}^{(k)}$ admits a decomposition into copies of $T$.

Observe that similarly as for Ringel’s conjecture, the order of the complete
graph needs to be at least $kn+k-1$ if we allow $T$ to be any tree with $n$
edges as the natural generalization of a star shows. It is an easy exercise to
show this conjecture for stars.

There is a conjecture related to Ringel’s conjecture for bipartite graphs due
to Graham and Häggkvist stating that $K_{n,n}$ can be decomposed into $n$
copies of any tree with $n$ edges. We propose here the following
strengthening.

######  Conjecture 8.5.

Suppose $k,n\in\mathbb{N}\setminus\\{1\\}$ and $T$ is a $k$-tree with $n$
edges. Then there is a decomposition of the complete balanced $k$-partite
graph on $kn$ vertices.

The tree packing conjecture has arguably the least obvious strengthening to
$k$-graphs and there may be more than one. We propose the following one.

######  Conjecture 8.6.

Suppose $k,n\in\mathbb{N}\setminus\\{1\\}$. Let $\mathcal{T}$ be a family of
$k$-trees such that $\mathcal{T}$ contains $\binom{n-i-1}{k-2}$ trees with $i$
edges for $i\in[n-k+1]$. Then $K_{n}^{(k)}$ admits a decomposition into
$\mathcal{T}$.

It follows directly from Theorem 1.3 that Conjectures 8.4 and 8.6 are
approximately true when restricted to bounded degree trees (and similarly an
approximate version of Conjecture 8.5 follows from our main theorem, see
Theorem 1.4 in Section 1.3).

###  8.2. Applications to simplicial complexes

Generalizing long-studied and nowadays classical combinatorial questions to
higher dimensions appears to be a challenging but insightful theme. There are
several results considering $k$-dimensional permutations and it was Linial and
Meshulam [33] who introduced a random model for simplicial complexes whose
probability measure is the same as those of a binomial random $(d+1)$-graph;
simply add all $d^{\prime}$-faces for $d^{\prime}\leq d-1$ with points in
$[n]$ and add every potential $d$-face independently with probability $p$.
Recently, Linial and Peled investigated and determined the threshold in
$Y_{d}(n,p)$ for the emergence of a what may considered as an analogoue of a
giant component [34].

With this topological viewpoint of treating a $k$-graph as a simplicial
complex, a cycle in a graph is simply an object homomorphic to
$\mathbb{S}^{1}$ and hence a $2$-dimensional Hamilton cycle a collection of
$2$-faces containing every vertex and which is homomorphic to
$\mathbb{S}^{2}$. In [35], Luria and Tessler determined the threshold in
$Y_{2}(n,p)$ for the appearance of such a Hamilton cycle (another suitable
term may be spanning triangulation of the sphere).

An analogue of Dirac’s theorem was proved by Georgakopoulos, Haslegrave,
Narayanan and Montgomery; to be precise, when every pair of vertices is
contained in at least $n/3+o(n)$ edges/2-faces of a $3$-graph $G$, then there
is a spanning triangulation of the sphere in $G$. This bound remains the same
when we replace $\mathbb{S}^{2}$ by any other compact surface without boundary
[18].

Instead of only asking for a single triangulation of some surface, we can of
course also investigate decompositions into (spanning) triangulations of
surfaces. Our results imply that every quasirandom simplicial complex (this in
particular includes almost all graphs in $Y_{d}(n,p)$) can even be almost
decomposed into any list of triangulations of any kind of manifolds provided
the density does not vanish too quickly with $n$ and as long as every vertex
is contained in at most a bounded number of $d$-faces. The triangulations may
even be chosen in advance. Hence a precise statement for 2-complexes is as
follows.

######  Corollary 8.7.

For all $\alpha>0$, there exist $n_{0},h\in\mathbb{N}$ and ${\varepsilon}>0$
such that the following holds for all $n\geq n_{0}$. Suppose $G$ is an
$({\varepsilon},h,d)$-typical $3$-graph on $n$ vertices with $d\geq
n^{-{\varepsilon}}$ and $H_{1},\ldots,H_{\ell}$ are spanning triangulations of
$\mathbb{S}^{2}$ where every vertex is contained in at most $\alpha^{-1}$
$2$-faces and $\ell\leq(1-\alpha)dn^{2}/12$. Then $G$ contains edge-disjoint
copies of $H_{1},\ldots,H_{\ell}$ such that every $2$-face of $G$ is contained
in at most one $H_{i}$.

We omit statements for higher dimensions as they follow in the obvious way
from Theorem 1.3. We wonder whether there is always an actual decomposition
(subject to certain divisibility conditions). This might be easier than a
decomposition into tight Hamilton cycles as the structure of tight Hamilton
cycles seems to be more restrictive.

## References

  * [1] P. Allen, J. Böttcher, D. Clemens, and A. Taraz, _Perfectly packing graphs with bounded degeneracy and many leaves_ , arXiv:1906.11558 (2019).
  * [2] P. Allen, J. Böttcher, H. Hàn, Y. Kohayakawa, and Y. Person, _Blow-up lemmas for sparse graphs_ , arXiv:1612.00622 (2016).
  * [3] P. Allen, J. Böttcher, J. Hladký, and D. Piguet, _Packing degenerate graphs_ , Adv. Math. 354 (2019), 106739.
  * [4] P. Allen, J. Böttcher, J. Skokan, and M. Stein, _Regularity inheritance in pseudorandom graphs_ , Random Structures Algorithms 56 (2020), 306–338.
  * [5] N. Alon, V. Rödl, and A. Ruciński, _Perfect matchings in $\epsilon$-regular graphs_, Electron. J. Combin. 5 (1998), 1–4.
  * [6] R. F. Bailey and B. Stevens, _Hamiltonian decompositions of complete $k$-uniform hypergraphs_, Discrete Math. 310 (2010), 3088–3095.
  * [7] D. Bal and A. Frieze, _Packing tight Hamilton cycles in uniform hypergraphs_ , SIAM J. Discrete Math. 26 (2012), 435–451.
  * [8] Z. Baranyai, _The edge-coloring of complete hypergraphs. I_ , J. Combin. Theory Ser. B 26 (1979), 276–294.
  * [9] J. Böttcher, J. Hladký, D. Piguet, and A. Taraz, _An approximate version of the tree packing conjecture_ , Israel J. Math. 211 (2016), 391–446.
  * [10] F. Chung and R. Graham, _Sparse quasi-random graphs_ , Combinatorica 22 (2002), 217–244.
  * [11] S. Ehard, _Embeddings and decompositions of graphs and hypergraphs_ , PhD thesis (2020).
  * [12] S. Ehard, S. Glock, and F. Joos, _Pseudorandom hypergraph matchings_ , Combin. Probab. Comput. 29 (2020), 868–885.
  * [13] S. Ehard and F. Joos, _A short proof of the blow-up lemma for approximate decompositions_ , arXiv:2001.03506 (2020).
  * [14] A. Ferber, C. Lee, and F. Mousset, _Packing spanning graphs from separable families_ , Israel J. Math. 219 (2017), 959–982.
  * [15] D. A. Freedman, _On tail probabilities for martingales_ , Ann. Probab. 3 (1975), 100–118.
  * [16] A. Frieze and M. Krivelevich, _Packing Hamilton cycles in random and pseudo-random hypergraphs_ , Random Structures Algorithms 41 (2012), 1–22.
  * [17] A. Frieze, M. Krivelevich, and P.-S. Loh, _Packing tight Hamilton cycles in 3-uniform hypergraphs_ , Random Structures Algorithms 40 (2012), 269–300.
  * [18] A. Georgakopoulos, J. Haslegrave, R. Montgomery, and B. Narayanan, _Spanning surfaces in $3$-graphs_, arXiv:1808.06864 (2018).
  * [19] S. Glock, F. Joos, J. Kim, D. Kühn, and D. Osthus, _Resolution of the Oberwolfach problem_ , arXiv:1806.04644 (2018).
  * [20] S. Glock, D. Kühn, A. Lo, and D. Osthus, _The existence of designs via iterative absorption: hypergraph $F$-designs for arbitrary $F$_, Mem. Amer. Math. Soc. (to appear).
  * [21] S. Glock, D. Kühn, and D. Osthus, _Extremal aspects of graph and hypergraph decomposition problems_ , Surveys in Combinatorics, London Mathematical Society Lecture Note Series, to appear.
  * [22] H. Hàn, J. Han, and P. Morris, _Factors and loose Hamilton cycles in sparse pseudo-random hypergraphs_ , Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2020, pp. 702–717.
  * [23] F. Joos, J. Kim, D. Kühn, and D. Osthus, _Optimal packings of bounded degree trees_ , J. Eur. Math. Soc. 21 (2019), 3573–3647.
  * [24] F. Joos and M. Kühn, _Fractional cycle decompositions in hypergraphs_ , arXiv:2101.05526 (2021).
  * [25] P. Keevash, _A hypergraph blow-up lemma_ , Random Structures Algorithms 39 (2011), 275–376.
  * [26] by same author, _The existence of designs_ , arXiv:1401.3665 (2014).
  * [27] by same author, _The existence of designs II_ , arXiv:1802.05900 (2018).
  * [28] by same author, _Hypergraph matchings and designs_ , Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. IV. Invited lectures, World Sci. Publ., Hackensack, NJ, 2018, pp. 3113–3135.
  * [29] P. Keevash and K. Staden, _The generalised Oberwolfach problem_ , arXiv:2004.09937 (2020).
  * [30] by same author, _Ringel’s tree packing conjecture in quasirandom graphs_ , arXiv:2004.09947 (2020).
  * [31] J. Kim, D. Kühn, D. Osthus, and M. Tyomkyn, _A blow-up lemma for approximate decompositions_ , Trans. Amer. Math. Soc. 371 (2019), 4655–4742.
  * [32] J. Komlós, G. N. Sárközy, and E. Szemerédi, _Blow-up lemma_ , Combinatorica 17 (1997), 109–123.
  * [33] N. Linial and R. Meshulam, _Homological connectivity of random 2-complexes_ , Combinatorica 26 (2006), 475–487.
  * [34] N. Linial and Y. Peled, _On the phase transition in random simplicial complexes_ , Ann. of Math. 184 (2016), 745–773.
  * [35] Z. Luria and R. J. Tessler, _A sharp threshold for spanning 2-spheres in random 2-complexes_ , Proc. Lond. Math. Soc. 119 (2019), 733–780.
  * [36] C. McDiarmid, _On the method of bounded differences_ , Surveys in combinatorics, 1989 (Norwich, 1989), London Math. Soc. Lecture Note Ser. 141, Cambridge Univ. Press, 1989, pp. 148–188.
  * [37] S. Messuti, V. Rödl, and M. Schacht, _Packing minor-closed families of graphs into complete graphs_ , J. Combin. Theory Ser. B 119 (2016), 245–265.
  * [38] R. Montgomery, A. Pokrovskiy, and B. Sudakov, _A proof of Ringel’s Conjecture_ , arXiv:2001.02665 (2020).
  * [39] V. Rödl and A. Ruciński, _Perfect matchings in $\epsilon$-regular graphs and the blow-up lemma_, Combinatorica 19 (1999), 437–452.
  * [40] A. Thomason, _Pseudo-random graphs_ , Proceedings of Random Graphs, Poznań 1985, Annals of Discrete Math. 33, North Holland, 1987, pp. 307–331.
  * [41] by same author, _Random graphs, strongly regular graphs and pseudo-random graphs_ , Surveys in Combinatorics, 123, London Mathematical Society Lecture Note Series, 1987, pp. 173–195.
  * [42] R. M. Wilson, _An existence theory for pairwise balanced designs I. Composition theorems and morphisms_ , J. Combin. Theory Ser. A 13 (1972), 220–245.
  * [43] by same author, _An existence theory for pairwise balanced designs II. The structure of PBD-closed sets and the existence conjectures_ , J. Combin. Theory Ser. A 13 (1972), 246–273.
  * [44] by same author, _An existence theory for pairwise balanced designs III. Proof of the existence conjectures_ , J. Combin. Theory Ser. A 18 (1975), 71–79.