the exceptional vertices in the proof of Theorem 1.7.

###### Proof of Lemma 11.1.

We introduce $\mu^{\prime}$ such that

$1/n\ll\xi\ll\varrho\ll 1/r\ll\varepsilon\ll\gamma\ll
d\ll\mu^{\prime}\ll\mu,1/\chi,1/\Delta.$

Given the statement, let $m=|V_{1}|$ be the common cluster size. Let
$L=V(G)\setminus V(G^{\prime})$ be the set of leftover vertices, and let
$\mathcal{K}$ be the set of ordered $k$-cliques in $R$.

######  Claim 12.1.

There is a partition $\mathcal{L}=\\{L_{K}\\}_{K\in\mathcal{K}}$ of $L$ with
parts of size at most $\sqrt{\varepsilon}m/r^{k-1}$ such that for each
$K\in\mathcal{K}$, every vertex in $L_{K}$ has at least $2dm$ neighbours in
$V_{i}$ where $i$ ranges over the first $k-1$ vertices of $K$.

###### Proof of the claim.

Let $W$ denote the bipartite graph with colour classes $L$ and $\mathcal{K}$.
We add an edge between $v\in L$ and $K\in\mathcal{K}$ if $v$ has at least
$2dm$ neighbours in each $V_{i}$ where $i$ ranges over the first $k-1$
vertices of $K$. Recall that $G$ is a $\mu$-robust
$(\chi,\varrho;t,\ell)$-tiling framework. By Proposition 8.1, every vertex in
$G$ is linked to $\mu^{\prime}n^{k}$ edges in $K_{k}(G)$. By 1 and
$\varepsilon\ll d\ll\mu^{\prime}$, it follows that every vertex in $G$ is
linked to $(\mu^{\prime}/2)n^{k}$ edges in $K_{k}(G^{\prime})$. This together
with 2 implies that each vertex in $L$ has at least $(\mu^{\prime}/4)r^{k}$
neighbours in $\mathcal{K}$. We obtain a bipartite graph $W^{\prime}$ from $W$
by blowing up each vertex $K\in\mathcal{K}$ to a set $K^{\prime}$ of size
$\sqrt{\varepsilon}m/r^{k-1}$. Let $\mathcal{K}^{\prime}=\bigcup K^{\prime}$.
So vertices in $L$ have at least
$(\mu^{\prime}/4)\sqrt{\varepsilon}mr\geqslant\varepsilon n$ neighbours in
$W^{\prime}$. Since $|L|\leqslant\varepsilon n$ by 1, we may greedily find a
matching in $W^{\prime}$ between $L$ and $\mathcal{K}^{\prime}$ covering $L$.
We then define $L_{K}$ as the vertices matched into $K^{\prime}$ for each
$K\in\mathcal{K}$. ∎

Now we show that one can individually cover the vertices of each part
$L_{K}\in\mathcal{L}$ by embedding a suitable subtiling $H_{K}\subseteq H$
into the clusters corresponding to $K$. To this end, fix
$L_{K}\in\mathcal{L}$. Without loss of generality, let $V(K)=[k]$. Let
$\mathcal{W}=\\{W_{i}\\}_{i\in[k]}$ where $W_{i}=V_{i}$. We apply Proposition
7.1 with $G^{\prime}[\mathcal{W}]$ and $k$ playing the role of $G$ and
$\Delta_{R^{\prime}}$. This gives a family of disjoint sets
$\mathcal{W}^{\prime}=\\{W_{i}^{\prime}\\}_{i\in[k]}$ with balanced clusters
$W_{i}^{\prime}\subseteq W_{i}$ of size
$m^{\prime}=\lfloor(1-{\sqrt{\varepsilon}})m\rfloor$ such that
$(G^{\prime}[\mathcal{W}^{\prime}],\mathcal{W}^{\prime})$ is a
$({2\varepsilon,d/2})$-super-regular $K$-partition. Let
$\mathcal{W}^{\prime\prime}=\\{W_{i}^{\prime\prime}\\}_{i\in[k]}$ be obtained
by adding the vertices of $L_{K}$ to $W^{\prime\prime}_{k}$. Let
$G^{\prime\prime}$ be obtained from $G^{\prime}[\mathcal{W}^{\prime\prime}]$
by adding the edges of $G$ between $L_{K}$ and the clusters
$W_{1}^{\prime\prime},\dots,W_{k-1}^{\prime\prime}$. Note that,
$(G^{\prime\prime},\mathcal{W}^{\prime\prime})$ is still a
$(\sqrt{\varepsilon},d/4)$-regular $K$-partition by Proposition 7.2.

Next, we select a subtiling $H_{K}\subseteq H$ of order
$(\varepsilon^{1/4}/(2kr^{k-1}))m\leqslant
v(H_{K})\leqslant(\varepsilon^{1/4}/(kr^{k-1}))m$. By assumption, $H_{K}$ has
a $k$-colouring, whose colour classes we denote by $C_{1},\dots,C_{k}$. Since
$\varepsilon\ll 1/\Delta,1/k$, we can assume that
$|C_{k}|\geqslant\Delta^{2}\sqrt{\varepsilon}m/r^{k-1}$. So we can greedily
find a set $C_{k}^{\prime}\subseteq C_{k}$ of size
$|C_{k}^{\prime}|\geqslant\sqrt{\varepsilon}m/r^{k-1}$ such that vertices in
$C_{k}^{\prime}$ are at distance $3$ in $H_{K}$ (meaning that their
neighbourhoods do not intersect). We greedily embed the vertices of $C_{k}$
into $W^{\prime\prime}_{k}$ covering the vertices of $L_{k}$ with
$C_{k}^{\prime}$. It remains to extend this partial embedding to a full
embedding of $H_{K}$, where $C_{1},\dots,C_{k-1}$ are embedded into
$W_{1}^{\prime},\dots,W_{k-1}^{\prime}$, respectively. This can be done by a
standard application of the Blow-Up Lemma with target sets [21]. We omit the
standard details.

Finally, we argue that the $H_{K}$’s can be chosen to be pairwise vertex-
disjoint. This is indeed possible by restricting the sets $\mathcal{W}$ to the
yet unused vertices, where we use that each $L_{K}$ requires at most
$(\varepsilon^{1/4}/(kr^{k-1}))m\leqslant\gamma m/(kr^{k-1})$ vertices of any
particular cluster $V_{i}$ and each $i\in V(R)$ is on at most $kr^{k-1}$
ordered $k$-cliques of $R$. It follows that
$H^{\prime}=\bigcup_{K\in\mathcal{K}}H_{K}$ has the desired properties. Since
$\gamma mr\leqslant\gamma n$ this finishes the proof. ∎

##  13\. Allocations

In the proof of Lemma 11.2, we aim to embed a graph $H$ into a (mostly)
balanced blow-up $R^{\ast}$ of a graph $R$. We can express this with a
homomorphism $\eta\colon H\rightarrow R$ that sends the correct number of
vertices of $H$ to every vertex of $R$. In the following, we introduce some
further vocabulary to formalise this. For a family of graphs $\mathcal{F}$, we
write
$\operatorname{{Hom}}(\mathcal{F};R)=\bigcup_{F\in\mathcal{F}}\operatorname{{Hom}}(F;R)$.
Recall that $\mathcal{F}=\mathcal{F}(k,w)$ is the family of properly
$k$-colourable graphs of order at most $w$. Suppose that $H$ is an
$\mathcal{F}$-tiling and let $R^{\prime}\subseteq R$. Hence we can express a
homomorphism $\eta\colon H\rightarrow R^{\prime}$ by a vector
$\mathbf{u}\in\mathbb{N}_{0}^{\operatorname{{Hom}}(\mathcal{F};R)}$ where
$\mathbf{u}(\phi)$ counts the number of tiles $F$ of $H$ for whom $\eta$
restricted to $F$ is $\phi\in\operatorname{{Hom}}(\mathcal{F};R^{\prime})$. In
this situation, we say that $\mathbf{u}$ is an _allocation of $H$ to
$R^{\prime}$_ and the vector $\mathbf{u}$ _encodes_ the homomorphism
$\eta$.555Strictly speaking, the encoding is only up automorphisms that
permute isomorphic tiles of $H$, but this is irrelevant for our argument.

It will be useful to track how many vertices of a tile $F\subseteq H$ are
mapped to a particular vertex in $R$ by a particular homomorphism
$\theta\in\operatorname{{Hom}}(F;R)$. To this end, we define
$A=A_{\mathcal{F},R}\in\mathbb{N}_{0}^{V(R)\times\operatorname{{Hom}}(\mathcal{F};R)}$
to be the _homomorphism incidence matrix_ by setting
$A(v,\theta)=|\theta^{-1}(v)|$ for each $v\in V(R)$ and
$\theta\in\operatorname{{Hom}}(\mathcal{F};R)$. Hence for a blow-up $R^{\ast}$
of $R$ with cluster sizes described by $\mathbf{x}\in\mathbb{N}_{0}^{V(R)}$,
an allocation $\mathbf{u}$ _encodes an embedding_ of $H$ into $R^{\ast}$
provided that $A\mathbf{u}\leqslant\mathbf{x}$.

Recall that for sets $T\subseteq S$ and a vector
$\mathbf{w}\in\mathbb{R}^{S}$, we obtain the restricted vector
${\left.\kern-1.2pt\mathbf{w}\vphantom{\big{|}}\right|_{T}}$ by setting all
entries that do not correspond to an element of $T$ to be zero. Suppose
$k\geqslant 2$ and let $J\subseteq K_{k}(R)$. We say that the allocation
$\mathbf{u}$ is _$(s,J)$ -surjective_ if we can write $\mathbf{u}$ as the sum
of (non-negative)
${\mathbf{v}^{\ast},}\mathbf{v}_{e,v}\in\operatorname{{Hom}}(\mathcal{F};R)$
ranging over all $e\in E(J)$ and $v\in e$ such that
$A\mathbf{v}_{e,v}(v)\geqslant s$ and $A\mathbf{v}_{e,v}(w)=0$ for all
$w\notin e$. In practice, a surjective allocation will act as a reservoir of
tiles that can be used for local adjustments.

To state the following results, we need the concept of reachability, which is
inspired by the work of Lo and Markström [31]. Let us recall the definition of
tight components. For a $k$-graph $J$, we define $T(J)$ to be the graph whose
vertices are the edges of $J$ where $e,f\in E(J)$ are adjacent whenever
$|e\cap f|=k-1$. The tight components of $J$ are the subgraphs $T\subseteq J$
whose edges form the connectivity components of $T(J)$. Let $J$ be a $k$-graph
and $T\subseteq J$ be a tight component. We define $\mathcal{R}(T)$ to be the
graph on the same vertex set as $T$ where two vertices $x,y$ are adjacent if
there are edges $e,f\in E(T)$ such that $x\in e\setminus f$, $y\in f\setminus
e$ and $|f\cap e|=k-1$. The _reachability components_ of $T$ are the
components of $\mathcal{R}(T)$.

######  Proposition 13.1.

A tight component in a $k$-graph has at most $k$ reachability components.
Moreover, each of its edges contains a vertex of each reachability component.

###### Proof.

Without loss of generality, we can assume that $J$ is a tight component,
meaning that $T(J)$ is connected. We proceed by induction on the number of
edges of $J$. Let $J^{\prime}$ be obtained by deleting the edge corresponding
to a leaf $e$ of a spanning tree of $T(J)$. So $J^{\prime}$ is still a tight
component. If $J^{\prime}$ is empty we are done as $e$ only has $k$ vertices,
so assume otherwise. By induction, $J^{\prime}$ has at most $k$ reachability
components. Moreover, each edge of $J^{\prime}$ contains a vertex of each
reachability component of $J^{\prime}$. By choice of $e$, there is an edge $f$
in $J^{\prime}$ with $|e\cap f|=k-1$. It follows that the vertex of
$e\setminus f$ is in the same reachability component as the vertex of
$f\setminus e$. Since $f\setminus e\subseteq V(J^{\prime})$, it is clear that
the vertex of $e\setminus f$ belongs to one of the (at most $k$) existing
tight components, and $e$ contains a vertex of each reachability component of
$T$. ∎

We also need the following simple fact. For a graph $G$, we denote by
$\vec{E}(G)$ the set of directed edges of $G$, that is, $\\{(u,v)\colon uv\in
E(G)\\}$. A function $f\colon\vec{E}(G)\to\mathbb{Z}$ is a _flow_ if
$f(u,v)=-f(v,u)$ for all $uv\in E(G)$ where we write $f(x,y)$ instead of
$f((x,y))$.

######  Proposition 13.2.

Suppose $G$ is a connected graph and $\mathbf{w}\in\mathbb{Z}^{V(G)}$
satisfies $\sum_{v\in V(G)}\mathbf{w}(v)=0$ and
$\lVert\mathbf{w}\rVert_{1}\leqslant s$. Then there exists a flow
$f\colon\vec{E}(G)\to\mathbb{Z}$ on $G$ satisfying $|f(u,v)|\leqslant s$ for
all $uv\in\vec{E}(G)$ and $\sum_{u\in N(v)}f(u,v)=\mathbf{w}(v)$ for all $v\in
V(G)$.

###### Proof.

We construct the flow as follows. Consider a set of
$\lVert\mathbf{w}\rVert_{1}$ positive and negative units assigned to $V(G)$.
The vertex $x\in V(G)$ receives $|\mathbf{w}(x)|$ units whose sign is
determined by the sign of $-\mathbf{w}(x)$. We match each negative unit to a
positive unit, say at $x$ and $x^{\prime}$ respectively, and then put a flow
of one unit on each edge of some (directed) path from $x$ to $x^{\prime}$.
This is possible because $G$ is connected. Next, we take the union of all
these paths; that is, for each such path $P$ and each (directed) edge
$(y,y^{\prime})$ in $P$, add $1$ to $(y,y^{\prime})$ and subtract $1$ from
$(y^{\prime},y)$. Taking the sum of the units assigned at each edge gives rise
to a flow $f\colon\vec{E}(G)\to\mathbb{Z}$ such that $\sum_{u\in
N(v)}f(u,v)=\mathbf{w}(v)$ and $|f(u,v)|\leqslant s$ for all $uv\in E(G)$. ∎

In the following we prove for a graph $R$ and a tight component $T\in
K_{k}(R)$ that surjective allocations to $R[V(T)]$ can be altered within a
reachability component $C$ of $T$.

######  Proposition 13.3.

Let $s,s^{\prime},r,w,k\in\mathbb{N}$ with $k\geqslant 2$ and
$r(rs+w)\leqslant s^{\prime}/2$. Let $R$ be a graph on $r$ vertices. Let $T$
be a tight component of $K_{k}(R)$, and let $C$ be a reachability component of
$T$. Let $\mathbf{b}\in\mathbb{Z}^{V(R)}$ satisfy $\mathbf{b}(v)=0$ for all
$v\in V(R)\setminus V(C)$ as well as $\sum_{v\in V(C)}\mathbf{b}(v)=0$ and
$\lVert\mathbf{b}\rVert_{\infty}\leqslant s$. Let
$\mathcal{F}=\mathcal{F}{(w,k)}$, $A=A_{\mathcal{F},R}$ and $H$ be an
$\mathcal{F}$-tiling. Let
$\mathbf{u}\in\mathbb{N}_{0}^{\operatorname{{Hom}}(\mathcal{F};R)}$ be an
$(s^{\prime},T)$-surjective allocation of $H$ to $R[V(T)]$. Then there exists
an $(s^{\prime}/2,T)$-surjective allocation
$\mathbf{w}\in\mathbb{N}_{0}^{\operatorname{{Hom}}(\mathcal{F};R)}$ of $H$ to
$R[V(T)]$ with $A(\mathbf{u}-\mathbf{w})=\mathbf{b}$.

###### Proof.

Let us give a brief overview of the proof. We start by viewing $\mathbf{b}$ as
a description of sinks and sources, before translating it into an integer flow
along the edges of $C\subseteq\mathcal{R}(T)$. This gives us a local
representation of $\mathbf{b}$ and allows us to treat the flow at each edge of
$C$ essentially independently. For each $xx^{\prime}\in E(C)$, we find a small
set of graphs, part of whom is allocated to $x$ or $x^{\prime}$ (depending on
the flow direction at $xx^{\prime}$) by $\mathbf{u}$. We alter the allocation
of these graphs at $x$ and $x^{\prime}$, ‘transferring’ vertices between $x$
and $x^{\prime}$ in order to mimic the flow at $xx^{\prime}$. Repeating this
for each edge, we mimic the entire flow and so the altered allocations; this
gives the desired
$\mathbf{w}\in\mathbb{N}_{0}^{\operatorname{{Hom}}(\mathcal{F};R)}$.

As $C$ is connected we can apply Proposition 13.2 to find a flow
$f\colon\vec{E}(C)\rightarrow\mathbb{Z}$ on $C$ satisfying
${\sum_{x^{\prime}\in N_{C}(x)}f(x^{\prime},x)}=\mathbf{b}(x)$ and
$|f(x,x^{\prime})|\leqslant\lVert\mathbf{b}\rVert_{\infty}v(R)\leqslant rs$
for all $xx^{\prime}\in E(C)$. So we now have a local representation of our
vector $\mathbf{b}$.

Fix an edge $xx^{\prime}\in E(C)$. We aim to find a set of tiles
$S_{xx^{\prime}}$ of $H$ that will be allocated differently in $\mathbf{u}$
and $\mathbf{w}$ so that $A(\mathbf{u}-\mathbf{w})$ mimics $f(x,x^{\prime})$.
Suppose, without loss of generality, that $f(x,x^{\prime})=c\geqslant 0$
(recall that $f(x,x^{\prime})\leqslant rs$). By the definition of reachability
components, there are $k$-cliques $K,K^{\prime}\subseteq R$ such that
$V(K),V(K^{\prime})\in E(T)$ with $V(K)\setminus V(K^{\prime})=\\{x\\}$ and
$V(K^{\prime})\setminus V(K)=\\{x^{\prime}\\}$. Given any $F\in\mathcal{F}$
and $\theta\in\operatorname{{Hom}}(F;K)$, we can find
$\theta^{\prime}\in\operatorname{{Hom}}(F;K\cup K^{\prime})$ such that
$\theta^{-1}(v)=\theta^{\prime-1}(v)$ for all $v\in V(K)\cap V(K^{\prime})$
with $|\theta^{\prime-1}(x)|=|\theta^{-1}(x)|-p$ and
${|\theta^{\prime-1}(x^{\prime})|=p}$ for each $0\leqslant
p\leqslant|\theta^{-1}(x)|$. Indeed, $K\cup K^{\prime}$ is a $(k+1)$-clique
minus the edge $xx^{\prime}$ and as $\theta^{-1}(x)$ is an independent set, it
is clear that such a $\theta^{\prime}$ exists. We choose $S_{xx^{\prime}}$ to
be a set of tiles $F$ in $H$ that are mapped to $R[V(K)]$ by some
$\theta_{F}\in\operatorname{{Hom}}(\mathcal{F};K)$ and such that
$c\leqslant\sum_{F\in S_{xx^{\prime}}}|\theta_{F}^{-1}(x)|\leqslant c+w$. This
is possible as the allocation $\mathbf{u}={\mathbf{u}^{\ast}+}\sum_{e\in
E(T),v\in e}\mathbf{u}_{e,v}$ of $H$ to $R$ is $(k,s^{\prime})$-surjective and
each tile $F$ of $H$ has order at most $w$. So in particular, we choose $F$ as
a subset of the tiles allocated by $\mathbf{u}_{V(K),x}$. We choose
$\theta_{F}^{\prime}\in\operatorname{{Hom}}(F;K\cup K^{\prime})$ for each
$F\in S_{xx^{\prime}}$ such that $\theta_{F}^{-1}(v)=\theta_{F}^{\prime-1}(v)$
for each $v\in V(K)\cap V(K^{\prime})$, while $\sum_{F\in
S_{xx^{\prime}}}(|\theta_{F}^{-1}(x)|-|\theta^{\prime-1}_{F}(x)|)=c$ and
$\sum_{F\in S_{xx^{\prime}}}|\theta_{F}^{\prime-1}(x^{\prime})|=c$.

We perform this procedure for each edge $xx^{\prime}\in E(C)$ in such a way
that for all distinct $xx^{\prime},yy^{\prime}\in E(C)$, we have
$S_{xx^{\prime}}\cap S_{yy^{\prime}}=\emptyset$. This is possible by
$(k,s^{\prime})$-surjectivity of $\mathbf{u}$ and since $s^{\prime}\geqslant
2r(rs+w)$. We then define our new allocation
$\mathbf{w}={\mathbf{u}^{\ast}+}\sum_{e\in E(R),v\in e}\mathbf{w}_{e,v}$ of
$H$ to $R$ as described above. The resulting $\mathbf{w}$ satisfies

$\left(A(\mathbf{u}-\mathbf{w})\right)(x)=\sum_{x^{\prime}\in
N_{C}(x)}f(x^{\prime},x)=\mathbf{b}(x)$

for all $x\in V(C)$, by construction. For each $e\in E(T)$ and $v\in e$, the
vector $\mathbf{w}_{e,v}$ allocates at most $r(s+w)\leqslant s^{\prime}/2$
fewer vertices to $v$ than $\mathbf{u}_{e,v}$. Thus $\mathbf{w}$ is
$(k,s^{\prime}/2)$-surjective. ∎

In Proposition 13.3, we require $\mathbf{b}$ to be zero outside of the vertex
set of the reachability component $C$ of the tight component $T$. If $H$
contains a proper flexi-chromatic subtiling, we can weaken this assumption to
being zero outside of $V(T)$.

For the following definition we extend the notion of topological colourings to
hypergraphs. That is, a _topological $k$-colouring of hypergraph
$\mathcal{J}$_ is a colouring $\phi:V(\mathcal{J})\rightarrow[k]$ of the
vertices of $\mathcal{J}$ with the property that all edges of $\mathcal{J}$
are monochromatic. It is worth noting that in a topological colouring all
loose components are monochromatic. Let $\mathcal{F}=\mathcal{F}(k,w)$, $W$ be
an $\mathcal{F}$-tiling and $R,R^{\prime}$ be graphs with $R^{\prime}\subseteq
R$. Suppose
$\mathbf{u}\in\mathbb{N}_{0}^{\operatorname{{Hom}}(\mathcal{F};R)}$ is an
allocation of $W$ to $R^{\prime}$. We say that $\mathbf{u}$ _encodes a proper
colouring_ $\phi$ of $W$ if $\mathbf{u}$ encodes a (restricted) homomorphism
$\eta\in\operatorname{{Hom}}(W;R^{\prime})$ such that there exists a proper
colouring $\phi^{\prime}$ of $R^{\prime}$ with $\phi^{\prime}\circ\eta=\phi$.

######  Proposition 13.4.

Let $s,s^{\prime},r,w,k\in\mathbb{N}$ with $k\geqslant 2$ and
$r(r^{2}s+w)\leqslant s^{\prime}/2^{k}$. Let $R$ be a graph on $r$ vertices,
$T$ a tight component of $K_{k}(R)$ and $e_{0}\in E(T)$. Let
$\mathcal{F}=\mathcal{F}(k,w)$ and $A=A_{\mathcal{F},R}$. Let $H$ be an
$\mathcal{F}$-tiling, and let
$\mathbf{u},\mathbf{u}_{1},\mathbf{u}_{2}\in\mathbb{N}_{0}^{\operatorname{{Hom}}(\mathcal{F};R)}$
be as follows. The vector $\mathbf{u}=\mathbf{u}_{1}+\mathbf{u}_{2}$ is an
allocation of $H$ to $R[V(T)]$. The vector $\mathbf{u}_{1}$ is an
$(s^{\prime},T)$-surjective allocation of a subtiling $H^{\prime}\subseteq H$
to $R[V(T)]$ and $\mathbf{u}_{2}$ is an allocation of a proper
$(k,{rs})$-flexi-chromatic subtiling $W=H-V(H^{\prime})$ to $R[e_{0}]$ that
encodes a proper central $k$-colouring of $W$.

Suppose $\mathbf{c}\in\mathbb{Z}^{V(R)}$ satisfies $\mathbf{c}(v)=0$ for all
$v\in V(R)\setminus V(T)$ as well as $\lVert\mathbf{c}\rVert_{\infty}\leqslant
s$ and $\sum_{v\in V(R)}\mathbf{c}(v)=0$. Then there exists an allocation
$\mathbf{w}\in\mathbb{N}_{0}^{\operatorname{{Hom}}(\mathcal{F};R)}$ of $H$ to
$R[V(T)]$ with $A(\mathbf{u}-\mathbf{w})=\mathbf{c}$.

###### Proof.

The proof traces the following outline. We begin by restricting the problem to
each of the reachability components in turn. This allows us to apply
Proposition 13.3 separately to each of them and find an allocation that is as
desired everywhere but at $e_{0}$. In some sense, we transfer all the
imbalance, encoded by $\mathbf{c}$, to $e_{0}$. Once we have all the imbalance
at $e_{0}$, we use the property of the proper flexi-chromatic subtiling at
$e_{0}$ to correct it, and thus obtain an allocation that is as desired
everywhere.

We divide the problem between the reachability components as follows. Denote
the reachability components of $T$ by $C_{1},\dots,C_{k^{\prime}}$, where
$k^{\prime}\leqslant k$ by Proposition 13.1. We deal with each reachability
component sequentially. Let $e_{0}=\\{v_{1},\dots,v_{k}\\}$ such that
$v_{i}\in V(C_{i})$ for all $i\in[k^{\prime}]$. Note that this is possible by
Proposition 13.1. To this end, for each $j\in[{k^{\prime}}]$, we define
$\mathbf{b}_{j}\in\mathbb{Z}^{V(R)}$ by setting

$\displaystyle\mathbf{b}_{j}(v)=\begin{cases}\mathbf{c}(v)-\sum_{u\in
V(C_{j})}\mathbf{c}(u)&\text{if $v=v_{j}$},\\\ \mathbf{c}(v)&\text{if $v\in
V(C_{j})\setminus\\{v_{j}\\}$ and}\\\ 0&\text{otherwise}.\end{cases}$

Thus, for each reachability component $C_{j}$, we can think of
$\mathbf{b}_{j}$ as encoding ‘transfers’ of the value $\mathbf{c}(v)$ to
$v_{j}\in e_{0}$ from each vertex in $v\in V(C_{j})\setminus\\{v_{j}\\}$. In
particular, for all $j\in[{k^{\prime}}]$, we have $\sum_{v\in
V(C_{j})}\mathbf{b}_{j}(v)=0$, $\mathbf{b}_{j}(v)=0$ for all $v\in
V(R)\setminus V(C_{j})$; in addition, we have
$\sum_{j\in[k^{\prime}]}\lVert\mathbf{b}_{j}\rVert_{\infty}\leqslant
r\lVert\mathbf{c}\rVert_{\infty}\leqslant rs$. We now have ${k^{\prime}}$
vectors $\mathbf{b}_{1},\dots,\mathbf{b}_{{k^{\prime}}}$, one for each
reachability component, each satisfying the conditions of Proposition 13.3.

Our next task is to find a set of altered allocations that, when combined,
implement the ‘transfers’ encoded by $\mathbf{b}_{j}$ on each reachability
component. Starting with $C_{1}$ this means we want to change the allocation
of some tiles such that the resulting change after we apply the map $A$ is
$\mathbf{b}_{1}$. Let $\mathbf{w}_{0}=\mathbf{u}_{1}$. We apply Proposition
13.3 in ${k^{\prime}}$ rounds with input
$H^{\prime},C_{i},\mathbf{b}_{i},\mathbf{w}_{i-1},rs,s^{\prime}/2^{i-1}$
playing the role of $H,C,\mathbf{b},\mathbf{u},s,s^{\prime}$ in the
$i^{\text{th}}$ round and the remaining parameters and objects keeping their
names, which is possible as $r(r^{2}s+w)\leqslant s^{\prime}/2^{k}$.

After the $i^{\text{th}}$ round, for $i\in[{k^{\prime}}]$, we obtain a
$(k,s^{\prime}/2^{i})$-surjective allocation
$\mathbf{w}_{i}\in\mathbb{N}_{0}^{\operatorname{{Hom}}(\mathcal{F};R)}$ of
$H^{\prime}$ to $R[V(T)]$ with
$A(\mathbf{w}_{i-1}-\mathbf{w}_{i})=\mathbf{b}_{i}$. Thus in
$\mathbf{w}_{{k^{\prime}}}$ we have implemented all the transfers
$\mathbf{b}_{1}.\dots,\mathbf{b}_{{k^{\prime}}}$ and
$A(\mathbf{u}_{1}-\mathbf{w}_{{k^{\prime}}})=\sum_{j\in[k^{\prime}]}\mathbf{b}_{j}$.
Note that here we also use the fact that $\mathbf{b}_{j}(v)$ is non-zero for
at most one $j\in[{k^{\prime}}]$ for all $v\in V(R)$. At this point we have
found an allocation $\mathbf{w}_{{k^{\prime}}}$ of $H^{\prime}$ such that
$\mathbf{w}_{{k^{\prime}}}+\mathbf{u}_{2}$ is the desired allocation
everywhere with the exception of the vertices of
$v_{1},\dots,v_{{k^{\prime}}}$.

The final step is to use the flexi-chromatic property to find a new allocation
of $W$ to replace $\mathbf{u}_{2}$ and so fix the only remaining imbalances,
which are at $e_{0}$. Define
$\mathbf{c}^{\prime}:=\mathbf{c}-A(\mathbf{u}_{1}-\mathbf{w}_{{k^{\prime}}})=\mathbf{c}-\sum_{j\in[k^{\prime}]}\mathbf{b}_{j}$
and note that $\mathbf{c}^{\prime}(v)\neq 0$ implies
$v\in\\{v_{1},\dots,v_{{k^{\prime}}}\\}$. By assumption $\sum_{v\in
V(R)}\mathbf{c}(v)=0$ and so

$\sum_{v\in
V(R)}\mathbf{c}^{\prime}(v)=\sum_{j\in[k^{\prime}]}\left(\mathbf{c}(v_{j})-\mathbf{b}_{j}(v_{j})\right)=\sum_{j\in[k^{\prime}]}\sum_{v\in
V(C_{j})}\mathbf{c}(v)=0.$

Observe that $\lVert\mathbf{c}^{\prime}\rVert_{\infty}\leqslant
r\cdot\lVert\mathbf{c}\rVert_{\infty}\leqslant rs$ and that $\mathbf{u}_{2}$
encodes a central $k$-colouring, say $\phi$, of the proper $(k,rs)$-flexi-
chromatic subtiling $W$ to $R[e_{0}]$. If we now consider
${\left.\kern-1.2pt\mathbf{c}^{\prime}\vphantom{\big{|}}\right|_{e_{0}}}$ and
view it as living in $\mathbb{Z}^{k}$, then by the definition of
$(k,rs)$-flexi-chromatic graphs, we can find a colouring $\phi^{\prime}$ of
$W$ with
$\operatorname{\mathbf{ord}}(\phi)-\operatorname{\mathbf{ord}}(\phi^{\prime})={\left.\kern-1.2pt\mathbf{c}^{\prime}\vphantom{\big{|}}\right|_{e_{0}}}$.
This colouring $\phi^{\prime}$ is encoded by an allocation
$\mathbf{u}^{\prime}_{2}\in\mathbb{N}_{0}^{\operatorname{{Hom}}(\mathcal{F};R)}$
of $W$ to $R[e_{0}]$ that satisfies
$A(\mathbf{u}_{2}-\mathbf{u}^{\prime}_{2})=\mathbf{c}^{\prime}$. We combine
the new allocation $\mathbf{w}_{{k^{\prime}}}$ of $H^{\prime}$ and
$\mathbf{u}_{2}^{\prime}$ of $W$ into an allocation
$\mathbf{w}\in\mathbb{N}_{0}^{\operatorname{{Hom}}(\mathcal{F};R)}$ of $H$ to
$R$ defined by $\mathbf{w}=\mathbf{w}_{{k^{\prime}}}+\mathbf{u}^{\prime}_{2}$.
Since

$A(\mathbf{u}-\mathbf{w})=A((\mathbf{u}_{1}-\mathbf{w}_{{k^{\prime}}})+(\mathbf{u}_{2}-\mathbf{u}^{\prime}_{2}))=\sum_{j\in[k^{\prime}]}\mathbf{b}_{j}+\mathbf{c}^{\prime}=\mathbf{c},$

this is the desired allocation $\mathbf{w}$ of $H$. ∎

##  14\. Properties of flexi-chromatic graphs

In the following, we establish a few further properties of flexi-chromatic
graphs. We start by extending the original definition (Definition 1.5)
slightly. A graph $W$ is $p$-_approximately $(k,s)$-flexi-chromatic_
($(k,s,p)$-_flexi-chromatic_ for short) with central colouring $\phi$ if the
following holds. For all $\mathbf{w}\in\mathbb{Z}^{k}$ with
$\sum_{i\in[k]}\mathbf{w}(i)=0$ and $\lVert\mathbf{w}\rVert_{\infty}\leqslant
s$, there exists a second $k$-colouring $\phi^{\prime}$ of $W$ with
$\lVert\operatorname{\mathbf{ord}}(\phi)-\operatorname{\mathbf{ord}}(\phi^{\prime})-\mathbf{w}\rVert_{\infty}\leqslant
p$. If the colourings are proper, then $W$ is properly flexi-chromatic, and if
they are topological, then $W$ is topologically flexi-chromatic. In particular
a proper $(k,s,0)$-flexi-chromatic graph is equivalent to, and is still
called, a proper $(k,s)$-flexi-chromatic graph (as defined in Definition 1.5).

We begin by proving the following result, which holds for both proper and
topological colourings and which implies Proposition 6.2.

######  Proposition 14.1.

Let $k,w\in\mathbb{N}$ and $p\in\mathbb{N}_{0}$ with $p<w$. Let
$H_{1},\dots,H_{k^{2}}$ be graphs such that $H_{i}$ has a proper (topological)
$k$-colouring $\theta_{i}$ for each $i\in[k^{2}]$ satisfying the following
property. For all $y\in[w]$, there exists a second proper (topological)
$k$-colouring $\theta^{\prime}_{i}$ of $H_{i}$ such that
$\operatorname{\mathbf{ord}}(\theta^{\prime}_{i})(j)=\operatorname{\mathbf{ord}}(\theta_{i})(j)$
for $j\in[k-2]$ and
$\operatorname{\mathbf{ord}}(\theta^{\prime}_{i})(k)=\operatorname{\mathbf{ord}}(\theta_{i})(k)+y\pm
p$. Then $\bigcup_{i\in[k^{2}]}H_{i}$ is properly (topologically)
$(k,w/k,kp)$-flexi-chromatic.

###### Proof.

We relabel the input so that we have a graph $H_{i,j}$ with a $k$-colouring
$\theta_{i,j}$ for each $1\leqslant i<j\leqslant k$ (the remaining
$k^{2}-\binom{k}{2}$ graphs of $H$ are not used). Let
$H=\bigcup_{i\in[k^{2}]}$. In order to show that $H$ is flexi-chromatic we
have to provide central colouring $\phi$. We construct the (candidate for our)
central colouring $\phi$ by defining its restrictions
$\phi_{i,j}={\left.\kern-1.2pt\phi\vphantom{\big{|}}\right|_{H_{i,j}}}$ as
follows. For $1\leqslant i<j\leqslant k$ and $F\in H_{i,j}$, we obtain
$\phi_{i,j}$ from $\theta_{i,j}$ by switching colour class $k-1$ with $i$ and
colour class $k$ with $j$. For all other tiles of $H$, $\phi$ and $\theta$
coincide.

Let us now show that $\phi$ has the properties of a central colouring of a
$(k,w/k,kp)$-flexi-chromatic graph. Suppose we are given some
$\mathbf{w}\in\mathbb{Z}^{k}$, with $\sum_{i\in[k]}\mathbf{w}(i)=0$ and
$\lVert\mathbf{w}\rVert_{\infty}\leqslant w/k$. Our goal is to construct a
second $k$-colouring $\phi^{\prime}$ of $H$ that satisfies
$\lVert\operatorname{\mathbf{ord}}(\phi)-\operatorname{\mathbf{ord}}(\phi^{\prime})-\mathbf{w}\rVert_{\infty}\leqslant
kp$.

Let us first reformulate $\mathbf{w}$ as follows. We apply Proposition 13.2 to
the complete graph with vertex set $[k]$ and weights
$\mathbf{w}(1),\dots,\mathbf{w}(k)$. This allows us to write
$\mathbf{w}=\sum_{1\leqslant i<j\leqslant k}\mathbf{w}_{i,j}$ as the sum of
vectors $\mathbf{w}_{i,j}\in\mathbb{Z}^{k}$ with
$\mathbf{w}_{i,j}(j)=-\mathbf{w}_{i,j}(i)$,
$\lVert\mathbf{w}_{i,j}\rVert_{\infty}\leqslant w$ and
$\mathbf{w}_{i,j}(\ell)=0$ for all $\ell\in[k]\setminus\\{i,j\\}$. (The factor
$k$ is due to the change of norm.)

Next, we define $\phi^{\prime}$ via its restriction to the $H_{i,j}$’s using
the weights $\mathbf{w}_{i,j}$. Now let $i,j\in[k]$ be distinct. Without loss
of generality, suppose that $0\leqslant
y=\mathbf{w}_{i,j}(j)=-\mathbf{w}_{i,j}(i)\leqslant w$. It remains to define
$\phi^{\prime}_{i,j}$. By assumption there is a colouring
$\theta^{\prime}_{i,j}$ of $H_{i,j}$, satisfying
$\operatorname{\mathbf{ord}}(\theta^{\prime}_{i,j})(k)=\operatorname{\mathbf{ord}}(\theta_{i,j})+y\pm
p$, while the other colour classes stay the same. We obtain
$\phi^{\prime}_{i,j}$ from $\theta^{\prime}_{i,j}$ by permuting the colour
classes taking $k-1$ to $i$ and $k$ to $j$. Thus
$\operatorname{\mathbf{ord}}(\phi^{\prime}_{i,j})(j)=\operatorname{\mathbf{ord}}(\phi_{i,j})(j)+y\pm
p$ and all colour class orders other than $i,j$ as before. Finally, let
$\phi^{\prime}=\bigcup\phi_{i,j}^{\prime}$.

To verify that $\phi^{\prime}$ has the desired property, we compute that for
all $i\in[k]$

$\displaystyle|$
$\displaystyle\operatorname{\mathbf{ord}}(\phi)(i)-\operatorname{\mathbf{ord}}(\phi^{\prime})(i)-\mathbf{w}(i)|\leqslant\sum_{\begin{subarray}{c}j\in[k]\end{subarray}}\left\lVert\operatorname{\mathbf{ord}}(\phi_{i,j})-\operatorname{\mathbf{ord}}(\phi^{\prime}_{i,j})-\mathbf{w}_{i,j}\right\rVert_{\infty}\leqslant
kp,$

which completes the proof. ∎

We obtain Proposition 6.6 as a corollary.

###### Proof of Proposition 6.6.

We choose $(k+1)^{2}$ subtilings $S_{i}$ for $i\in[(k+1)^{2}]$ each of order
at least $n/(k+1)^{2}-2w$. We can do this greedily as each tile has order at
most $w$. For each $S_{i}$, we choose a $k$-colouring with largest colour
class $k$ and empty colour class $k+1$. As we can recolour vertices from
colour $k$ to $k+1$ freely, and as the colour class $k$ has order at least
$n/(k+1)^{4}$, we can apply Proposition 14.1 with $k+1,n/(k+1)^{4},0$ as
$k,w,p$. It follows that $H$ is properly $(k+1,n/(k+1)^{5},0)$-flexi-
chromatic. ∎

The following is a simple but pertinent property of flexi-chromatic graphs.

######  Proposition 14.2.

Suppose $W_{1}$ is properly (topologically) $(k,s_{1},p_{1})$-flexi-chromatic
and $W_{2}$ is a $(k,s_{2},p_{2})$-flexi-chromatic with central colourings
$\phi_{1}$ and $\phi_{2}$, respectively. If $s_{2}\geqslant p_{1}$, then
$W=W_{1}\cup W_{2}$ is properly (topologically) $(k,s_{1},p_{2})$-flexi-
chromatic. Further, $\phi_{1}\cup\phi_{2}$ is a central colouring of $W$.

###### Proof.

Let $\phi=\phi_{1}\cup\phi_{2}$, and fix a $\mathbf{w}\in\mathbb{Z}^{k}$ with
$\sum_{i\in[k]}\mathbf{w}(i)=0$ and $\lVert\mathbf{w}\rVert_{\infty}\leqslant
s_{1}$. We seek a $k$-colouring $\phi^{\prime}$ of $W_{1}\cup W_{2}$ with
$\lVert\operatorname{\mathbf{ord}}(\phi)-\operatorname{\mathbf{ord}}(\phi^{\prime})-\mathbf{w}\rVert_{\infty}\leqslant
p_{2}$. We obtain this by first finding
$\phi^{\prime}_{1}:={\left.\kern-1.2pt\phi^{\prime}\vphantom{\big{|}}\right|_{W_{1}}}$
and then using $\phi^{\prime}_{1}$ to find
$\phi^{\prime}_{2}:={\left.\kern-1.2pt\phi^{\prime}\vphantom{\big{|}}\right|_{W_{2}}}$
such that $\phi^{\prime}$ has the desired properties.

As $W_{1}$ is $(k,s_{1},p_{1})$-flexi-chromatic, with central $k$-colouring
$\phi_{1}$, we can find a $k$-colouring $\phi^{\prime}_{1}$ of $W_{1}$ such
that $\sum_{i\in[k]}\mathbf{w}^{\prime}(i)=0$ and
$\lVert\mathbf{w}^{\prime}\rVert_{\infty}\leqslant p_{1}$ where
$\mathbf{w}^{\prime}:=-(\operatorname{\mathbf{ord}}(\phi_{1})-\operatorname{\mathbf{ord}}(\phi^{\prime}_{1})-\mathbf{w})\in\mathbb{Z}^{k}$.
By assumption $p_{1}\leqslant s_{2}$ and so we can find a colouring
$\phi^{\prime}_{2}$ of $W_{2}$ such that
$\lVert\operatorname{\mathbf{ord}}(\phi_{2})-\operatorname{\mathbf{ord}}(\phi^{\prime}_{2})-\mathbf{w}^{\prime}\rVert_{\infty}\leqslant
p_{2}$. We see that $\phi^{\prime}$ is the desired colouring as
$\operatorname{\mathbf{ord}}(\phi)=\operatorname{\mathbf{ord}}(\phi_{1})+\operatorname{\mathbf{ord}}(\phi_{2})$,
$\operatorname{\mathbf{ord}}(\phi^{\prime})=\operatorname{\mathbf{ord}}(\phi^{\prime}_{1})+\operatorname{\mathbf{ord}}(\phi^{\prime}_{2})$
and

$\displaystyle\lVert\operatorname{\mathbf{ord}}(\phi)-\operatorname{\mathbf{ord}}(\phi^{\prime})-\mathbf{w}\rVert_{\infty}\leqslant$
$\displaystyle\lVert\left(\operatorname{\mathbf{ord}}(\phi_{2})-\operatorname{\mathbf{ord}}(\phi^{\prime}_{2})\right)+\left(\operatorname{\mathbf{ord}}(\phi_{1})-\operatorname{\mathbf{ord}}(\phi^{\prime}_{1})-\mathbf{w}\right)\rVert_{\infty}$
$\displaystyle\leqslant$
$\displaystyle\lVert\operatorname{\mathbf{ord}}(\phi_{2})-\operatorname{\mathbf{ord}}(\phi^{\prime}_{2})-\mathbf{w}^{\prime}\rVert_{\infty}\leqslant
p_{2}.\qed$

We now prove that sufficiently large $\mathcal{F}(k,w)$-tilings are properly
$kw$-approximately flexi-chromatic.

######  Proposition 14.3.

Let $1/n\leqslant\xi\ll\tau\ll 1/\chi$ with $k={\lceil\chi\rceil}$ and
$\chi<k-\tau$. Let $w\leqslant\xi n$ and $H$ be an $\mathcal{F}(k,w)$-tiling
on $n$ vertices with $\operatorname{\chi_{\rm cr}}(H)<k-\tau$. Then $H$ is
properly $(k,\tau n/(2k^{5}),kw)$-flexi-chromatic.

###### Proof.

Our strategy for the proof is as follows. We first find a colouring $\theta$
of $H$ in which the size of the largest and smallest colour classes differ by
at least $\frac{\tau}{2k^{2}}n$. We then use this colouring to partition $H$
into subtilings that satisfy the conditions of Proposition 14.1 and conclude.

Observe that we can assume $\operatorname{\chi_{\rm cr}}(H)\geqslant k-1$ as
we can simply put a $(k-1)$-clique in $H$ to achieve this. We may thus write
$\operatorname{\chi_{\rm cr}}(H)=k-x$ for some $\tau<x<1$. By definition,
there is a $k$-colouring $\theta$ of $H$ such that $\operatorname{\chi_{\rm
cr}}(H)=(k-1)+\frac{(k-1)a}{n-a}$ where $a=|\theta^{-1}(k-1)|$. Solving for
$a$, this gives
$|\theta^{-1}(k-1)|=\frac{1-x}{1-x/k}\frac{n}{k}\leqslant(1-\frac{x}{k})\frac{n}{k}<(1-\frac{\tau}{k})\frac{n}{k}$,
where we used that $k\geqslant 2$ in the first inequality. Moreover, by
averaging, there is also some colour, say $k$, such that
$|\theta^{-1}(k)|\geqslant\frac{n}{k}$ and so
$|\theta^{-1}(k)|-|\theta^{-1}(k-1)|>{\frac{\tau}{k}\frac{n}{k}}$. For each
tile $F$ of $H$, we denote by
$\theta_{F}={\left.\kern-1.2pt\theta\vphantom{\big{|}}\right|_{V(F)}}$ the
colouring of $F$ induced by $\theta$. Summing over the tiles of $H$, this
gives

$\sum_{F}|\theta_{F}^{-1}(k)|-|\theta_{F}^{-1}(k-1)|=|\theta^{-1}(k)|-|\theta^{-1}(k-1)|\geqslant\frac{\tau}{k}\frac{n}{k}.$

We greedily partition the tiles of $H$ into $k^{2}$ subtilings $H_{i}$ for
$i\in[k^{2}]$ such that for each such $H_{i}$, we have

$\frac{1}{k^{2}}\frac{\tau}{k}\frac{n}{k}-w\geqslant\sum_{F\in
H_{i}}|\theta_{F}^{-1}(k)|-|\theta_{F}^{-1}(k-1)|.$

This is possible because $v(F)\leqslant w$. Let
$\theta_{i}=\bigcup_{F\subseteq H_{i}}\theta_{F}$.

We intend to apply Proposition 14.1 to the $H_{i}$’s with $k,\frac{\tau
n}{2k^{4}},w$ playing the role of $k,w,p$. To verify the assmumptions, fix
$H_{i}$ and consider an arbitrary $y\in[\frac{1}{2k^{2}}\frac{\tau}{k}]$. We
have to show that there exists a second $k$-colouring $\theta^{\prime}_{i}$ of
$H_{i}$ such that
$\operatorname{\mathbf{ord}}(\theta^{\prime}_{i})(j)=\operatorname{\mathbf{ord}}(\theta_{i})(j)$
for $j\in[k-2]$ and
$\operatorname{\mathbf{ord}}(\theta^{\prime}_{i})(k)=\operatorname{\mathbf{ord}}(\theta_{i})(k)+y\pm
w$. It is not hard to see that one can obtain such a colouring by flipping the
colours $k-1$ and $k$ of tiles $F\in H_{i}$ which has more vertices of colour
$k$ than colour $k-1$ under $\theta_{F}$. Since $v(F)\leqslant w$, we
overshoot by at most $w$ when this process ends. Hence Proposition 14.1
applies and it follows that $H$ is $(k,\tau n/(2k^{5}),kw)$-flexi-chromatic. ∎

##  15\. Proof of  (Lemma for $H$).

In the following, we show Lemma 11.2 ( (Lemma for $H$).), which states that
given a certain $R$-partition of $G$, we can find a size-compatible vertex
partition of the given graph $H$.

###### Proof of Lemma 11.2.

Let $k={\lceil\chi\rceil}$. Given $\mu$ with
$\chi+\mu/2\leqslant\lceil\chi\rceil$, we can assume that
$\chi+\mu/2=(k-1)+a/b$ for (coprime) natural numbers $a\leqslant b\leqslant
8/\mu$.666Let $4\mu\leqslant b:=4\lceil\mu^{-1}\rceil\leqslant 8/\mu$ and
choose $a\in\mathbb{N}$ maximal such that $k-1+a/b\leqslant\chi+\mu/2$. We
choose $\varrho^{\prime},\beta>0$ such that

$\displaystyle 1/n\leqslant\xi\ll\varrho\ll\varrho^{\prime}\ll\beta\ll
1/r\ll\alpha\ll\mu,1/\Delta,1/\chi.$

Let $w\leqslant\xi n$. Suppose that $G$ is a $\mu$-robust
$(\chi+\mu,\varrho;t,\ell)$-tiling framework on $n$ vertices. Let $R$ be a
$({\chi},\varrho;t,\ell)$-tiling framework on vertex set $[r]$ with a
$K_{k}$-cover $R^{\prime}\subseteq R$ with
$\Delta(R^{\prime})\leqslant\Delta$. For $\mathcal{V}=\\{V_{i}\\}_{i\in[r]}$,
let $(G,\mathcal{V})$ be a $2$-balanced $R$-partition, where
$m\leqslant|V_{i}|\leqslant 2m$ for $i\in[r]$. So in particular $m\geqslant
n/(2r)$. Let $H\in\mathcal{H}(n,w,\Delta;\chi;t,\ell,w^{\prime})$.

Our objective is now to find a size-compatible (with $\mathcal{V}$) vertex
partition $\mathcal{X}=\\{X_{i}\\}_{i\in[r]}$ of $H$ and
$\tilde{\mathcal{X}}=\\{\tilde{X}_{i}\\}_{i\in[r]}$ with
$\tilde{X}_{i}\subseteq X_{i}$ for each $i\in[r]$ such that $(H,\mathcal{X})$
is an $R$-partition and $\tilde{\mathcal{X}}$ is an
$(\alpha,R^{\prime})$-buffer for $(H,\mathcal{X})$. We reformulate this
problem in vector notation. Let $\mathbf{b}\in\mathbb{N}^{V(R)}$ with
$\mathbf{b}(i)=|V_{i}|$. Set $\mathcal{F}=\mathcal{F}(k,w)$ and
$A=A_{\mathcal{F},R}\in\mathbb{N}_{0}^{V(R)\times\operatorname{{Hom}}(\mathcal{F};R)}$.
Our goal is to find an allocation
$\mathbf{v}^{\ast}\in\mathbb{N}_{0}^{\operatorname{{Hom}}(\mathcal{F};R)}$ of
$H$ to $R$ (as defined in Section 13) such that

  1. (1)

$A\mathbf{v}^{\ast}=\mathbf{b}$ and

  2. (2)

$A({\left.\kern-1.2pt\mathbf{v}^{\ast}\vphantom{\big{|}}\right|_{\operatorname{{Hom}}(\mathcal{F};R^{\prime})}}){\geqslant\alpha
m}$.

Given such vectors we generate the desired $R$-partition $(H,\mathcal{X})$ as
follows. Let $\eta$ be a homomorphism from $H$ to $R$ encoded by
$\mathbf{v}^{\ast}$ (as defined in Section 13). We set $X_{i}=\eta^{-1}(i)$
for each $i\in[r]$, and let $\mathcal{X}=\\{X_{i}\\}_{i\in[r]}$. It follows
that $(\mathcal{X},R)$ is an $R$-partition. Moreover, $\mathcal{X}$ is size-
compatible with $\mathcal{V}$ by 1. For the buffer, observe that the
restriction
${\left.\kern-1.2pt\mathbf{v}^{\ast}\vphantom{\big{|}}\right|_{\operatorname{{Hom}}(\mathcal{F};R^{\prime})}}$
encodes homomorphisms from some tiles of $H$ to $R^{\prime}$. Thus
${\left.\kern-1.2pt\mathbf{v}^{\ast}\vphantom{\big{|}}\right|_{\operatorname{{Hom}}(\mathcal{F};R^{\prime})}}$
is an allocation of some subtiling $F$ of $H$ to $R^{\prime}$ and encodes a
homomorphism $\eta^{\prime}$ from $F$ to $R^{\prime}$. We define
$\tilde{X}_{i}=\eta^{\prime-1}(i)$. When combined with 2, this states that
$|\tilde{X}_{i}|\geqslant\frac{\alpha}{2}|X_{i}|$ for all $i\in[r]$.

Now we give an overview of the proof. We first ensure that 2 is satisfied by
finding a $\mathbf{v}_{2}^{\ast}$ that allocates a subtiling of $H$ (Claim
15.1). The remainder of $H$ is denoted by $H^{\prime}$. We then find a
$\mathbf{v}^{\prime}$, which allocates $H^{\prime}$ to $R$ such that
$A(\mathbf{v}^{\prime}+\mathbf{v}_{2}^{\ast})\approx\mathbf{b}$ (Claim 15.2).
In addition to this, $\mathbf{v}^{\prime}$ also matches the loose and tight
components of the tiling framework $R$ with the topological and proper flexi-
chromatic subtilings of $H^{\prime}$. We finish by applying Proposition 13.4
separately to each tight component (Claim 15.3) to obtain
$\mathbf{v}_{1}^{\ast}$ from $\mathbf{v}^{\prime}$ such that
$A(\mathbf{v}_{1}^{\ast}+\mathbf{v}_{2}^{\ast})=\mathbf{b}$. Now come the
details.

The following claim establishes 2.

######  Claim 15.1.

There is a subtiling $H^{\prime}\subseteq H$ and an allocation
$\mathbf{v}_{2}^{\ast}\in\mathbb{N}_{0}^{\operatorname{{Hom}}(\mathcal{F};R)}$
of $H-V(H^{\prime})$ to $R^{\prime}$ with

  1. n(3)

$H^{\prime}\in\mathcal{H}(n,w,\Delta;\chi+\sqrt{\alpha};t,\ell,w^{\prime})$
and

  2. n(4)

$\alpha m\leqslant
A({\left.\kern-1.2pt\mathbf{v}_{2}^{\ast}\vphantom{\big{|}}\right|_{\operatorname{{Hom}}(\mathcal{F};R^{\prime})}})\leqslant\sqrt{\alpha}m$.

We assume the truth of the claim for the time being and prove it later. Let
$H^{\prime}$ and $\mathbf{v}_{2}^{\ast}$ be as in Claim 15.1. Set
$\mathbf{b}^{\prime}=\mathbf{b}-\mathbf{v}_{2}^{\ast}$; that is,
$\mathbf{b}^{\prime}(i)$ equals the number of vertices of $V_{i}$ that are not
yet used by $H-V(H^{\prime})$ for the allocation. We now seek an allocation
$\mathbf{v}_{1}^{\ast}\in\mathbb{N}_{0}^{\operatorname{{Hom}}(\mathcal{F};R)}$
of $H^{\prime}$ to $R$ with $A\mathbf{v}_{1}^{\ast}=\mathbf{b}^{\prime}$. Let
$J=K_{k}(R)$. Since $R$ is a $({\chi},\varrho;t,\ell)$-tiling framework, we
know that $J$ is $(t,\ell)$-connected. Hence there is a (vertex) spanning
subgraph $J^{\prime}\subseteq J$ with tight components
$T_{1},\dots,T_{t^{\prime}}\subseteq J^{\prime}$ with $t^{\prime}\leqslant t$
and loose components $L_{1},\dots,L_{\ell^{\prime}}$ with
$\ell^{\prime}\leqslant\ell$. In the following, we may assume that
$t^{\prime}=t$ and $\ell^{\prime}=\ell$ as otherwise we simply redefine $t$
and $\ell$. We fix a $k$-edge $e_{j}\in E(T_{j})$ for each $j\in[t]$ and a
$k$-edge $f_{q}\in E(L_{q})$ for each $q\in[\ell]$.

The next claim provides an allocation
$\mathbf{v}^{\prime}\in\mathbb{N}_{0}^{\operatorname{{Hom}}(\mathcal{F};R)}$
of $H^{\prime}$ to $R$, which almost satisfies $\mathbf{b}^{\prime}$ and
prepares the flexi-chromatic subtilings for their upcoming uses. Note that the
proper flexi-chromatic subtilings are somewhat stronger than those ensured by
$H\in\mathcal{H}(n,w,\Delta;\chi;t,\ell,w^{\prime})$.

######  Claim 15.2.

There are disjoint subtilings $W,W_{1},\dots,W_{t}$ of $H$ such that $W$ is
topologically $(\ell,w)$-flexi-chromatic and $W_{j}$ is properly
$(k,{\sqrt{\varrho^{\prime}}rn})$-flexi-chromatic for each $j\in[t]$.
Moreover, there exist
$\mathbf{w},\mathbf{w}_{j},\mathbf{u}_{j},\mathbf{r}\in\mathbb{N}_{0}^{\operatorname{{Hom}}(\mathcal{F};R)}$
for each $j\in[t]$ with
$\mathbf{v}^{\prime}:=\mathbf{r}+\mathbf{w}+\sum_{j\in[t]}\mathbf{u}_{j}+\mathbf{w}_{j}$
and
$\mathbf{c}^{\prime}:=A\mathbf{v}^{\prime}-\mathbf{b}^{\prime}\in\mathbb{N}_{0}^{V(R)}$
such that

  1. n(5)

$\mathbf{w}$ is an allocation of $W$ to $R$ that encodes a central topological
$\ell$-colouring of $W$ such that each $R[f_{1}],\dots,R[f_{\ell}]$ receives
one colour class.

  2. n(6)

$\mathbf{w}_{j}$ is an allocation of $W_{j}$ to $R[e_{j}]$ that encodes a
central proper $k$-colouring of $W_{j}$,

  3. n(7)

$\mathbf{u}_{j}$ is a $(\beta n,T_{j})$-surjective allocation of a subtiling
of $H^{\prime}$ to $R[V(T_{j})]$,

  4. n(8)

$\mathbf{v}^{\prime}$ is an allocation of $H^{\prime}$ to $R$ and

  5. n(9)

${\sum_{i\in V(L_{q})}|\mathbf{c}^{\prime}(i)|}\leqslant w$ for each
$q\in[\ell]$.

We also defer the proof of this claim and continue with the main argument. Fix
$\mathbf{w}_{1},\dots,\mathbf{w}_{t}$, $\mathbf{u}_{1},\dots,\mathbf{u}_{t}$,
$\mathbf{r},\mathbf{v}^{\prime},\mathbf{c}^{\prime}$ and $W,W_{1},\dots,W_{t}$
as in Claim 15.2.

Next, we use the definition of topologically $(\ell,w)$-flexi-chromatic graphs
together with 5 to reallocate $W$. By 5, there is a central topological
$\ell$-colouring $\phi$ of $W$ encoded by $\mathbf{w}$. By Definition 1.5 and
9, there is a second topological $\ell$-colouring $\phi^{\prime}$ of $W$ with
$(\operatorname{\mathbf{ord}}(\phi))(q)-(\operatorname{\mathbf{ord}}(\phi^{\prime}))(q)=\sum_{i\in
V(L_{q})}\mathbf{c}^{\prime}(i)$. Let
$\mathbf{w}^{\prime}\in\mathbb{N}_{0}^{\operatorname{{Hom}}(\mathcal{F};R)}$
be an allocation of $W$ to $R$ that encodes $\phi^{\prime}$. (Such an
allocation exists as $W$ is properly $k$-colourable and each $R[f_{q}]$
induces a copy of $K_{k}$ to which we can allocate $W[\phi^{\prime-1}(q)]$.)
Define

$\mathbf{v}^{\prime\prime}=\mathbf{r}+\mathbf{w}^{\prime}+\sum_{j\in[t]}\mathbf{u}_{j}+\mathbf{w}_{j}$
and $\mathbf{c}=A\mathbf{v}^{\prime\prime}-\mathbf{b}^{\prime}$. (15.1)

By construction we have

$\lVert\mathbf{c}\rVert_{1}\leqslant r{\varrho^{\prime}}n$ and $\sum_{i\in
V(L_{q})}\mathbf{c}(i)=0$ for each $q\in[\ell]$. (15.2)

We may think of $\mathbf{c}$ as the imbalance that is still present in our
current allocation and (15.2) says that there is no imbalance across loose
components. The following claim states that the imbalance can be divided into
$t$ parts such that there is no imbalance across tight components any more.
The imbalance inside each tight component can then be handled by a single
flexi-chromatic subtiling via Proposition 13.4.

######  Claim 15.3.

There exist $\mathbf{c}_{1},\dots,\mathbf{c}_{t}\in\mathbb{Z}^{V(R)}$ such
that

  1. n(10)

$\sum_{j\in[t]}\mathbf{c}_{j}=\mathbf{c}$,

  2. n(11)

$\lVert\mathbf{c}_{j}\rVert_{\infty}\leqslant\sqrt{\varrho^{\prime}}n$ for all
$j\in[t]$,

  3. n(12)

$\sum_{i\in[r]}\mathbf{c}_{j}(i)=0$ for all $j\in[t]$ and

  4. n(13)

$i\in V(T_{j})$ whenever $\mathbf{c}_{j}(i)\neq 0$ for all $j\in[t]$.

As before, we assume the truth of the claim for now and prove it later. Let
$H_{j}^{\prime}$ be the subtiling of $H^{\prime}$ allocated by
$\mathbf{w}_{j}+\mathbf{u}_{j}$ for each $j\in[t]$. For each tight component
$T_{j}$, we apply Proposition 13.4 with

object/parameter | $W_{j}$ | $R[V(L_{j})]$ | $H_{j}^{\prime}$ | $T_{j}$ | $e_{j}$ | $\mathbf{u}_{j}$ | $\mathbf{w}_{j}$ | $\mathbf{c}_{j}$ | $\sqrt{\varrho^{\prime}}n$ | $\beta n$
---|---|---|---|---|---|---|---|---|---|---
playing the role of | $W$ | $R$ | $H$ | $T$ | $e_{0}$ | $\mathbf{u}_{1}$ | $\mathbf{u}_{2}$ | $\mathbf{c}$ | $s$ | $s^{\prime}$

to obtain a second allocation $\mathbf{v}_{j}$ of $H_{j}^{\prime}$ such that

$\displaystyle
A(\mathbf{u}_{j}+\mathbf{w}_{j}-\mathbf{v}_{j})=\mathbf{c}_{j}.$ (15.3)

We claim that these allocations combine to give the result. Note that as
$\mathbf{v}^{\prime\prime}=\mathbf{r}+\mathbf{w}^{\prime}+\sum_{j\in[t]}\mathbf{u}_{j}+\mathbf{w}_{j}$
is an allocation of $H^{\prime}$ to $R$, so is
$\mathbf{v}_{2}^{\ast}:=\mathbf{r}+\mathbf{w}^{\prime}+\sum_{j\in[t]}\mathbf{v}_{j}$.
Indeed we change neither $\mathbf{r}$ nor $\mathbf{w}^{\prime}$, and
$\mathbf{v}_{j}$ allocates the same subtiling $H_{j}^{\prime}\subseteq
H^{\prime}$ as $\mathbf{u}_{j}+\mathbf{w}_{j}$ does. Further,

$\displaystyle A\mathbf{v}_{2}^{\ast}-\mathbf{b}^{\prime}$
$\displaystyle=A(\mathbf{v}_{2}^{\ast}-\mathbf{v}^{\prime\prime})+(A\mathbf{v}^{\prime\prime}-\mathbf{b}^{\prime})$
$\displaystyle{=}A\left(\mathbf{r}+\mathbf{w}^{\prime}+\sum_{j\in[t]}\mathbf{v}_{j}-\left(\mathbf{r}+\mathbf{w}^{\prime}+\sum_{j\in[t]}\mathbf{u}_{j}+\mathbf{w}_{j}\right)\right)+\mathbf{c}$
$\displaystyle{=}-\sum_{j\in[t]}\mathbf{c}_{j}+\mathbf{c}=0.$

Thus $\mathbf{v}_{2}^{\ast}$ is the desired allocation of $H^{\prime}$, and so
$\mathbf{v}^{\ast}=\mathbf{v}_{1}^{\ast}+\mathbf{v}_{2}^{\ast}$ satisfies both
1 and 2. To finish the proof, it remains to show the three claims.

###### Proof of Claim 15.1.

Consider any $i\in[r]$. Choose a subtiling $H_{i}\subseteq H$ of order
$k\alpha m\leqslant v(H_{i})\leqslant k\alpha m+w\leqslant 2k\alpha m$. (This
is possible, since the tiles of $H$ have size at most $w\leqslant\xi
n\leqslant\alpha m$.) We do so such that each subtiling is disjoint and does
not intersect the flexi-chromatic subtilings of $H$ (which in total span at
most $(t+1)w^{\prime}\leqslant(t+1)\sqrt{\xi}n$ vertices). Consider a (proper)
$k$-colouring of $H_{i}$ and note that its largest colour class has at least
$\alpha m$ vertices. Since $R^{\prime}$ is a $K_{k}$-cover, there is some
$k$-clique $K_{i}\subseteq R^{\prime}$ which contains $i$. Let
$\mathbf{q}_{i}$ be the allocation of $H_{i}$ to the clique $K_{i}$ such that
the largest colour class is mapped to $i\in V(K_{i})$. Note that at most
$2k\alpha m$ vertices are allocated to any vertex $j$ of $K_{i}$. Moreover,
Since $\Delta(R^{\prime})\leqslant\Delta$, this allocates in total at most
$2k\Delta\alpha m$ vertices to any cluster. The union of the $H_{i}$’s has
order at most $2k\Delta\alpha mr\leqslant\sqrt{\alpha}n$. Consequently, we may
assume the $H_{i}$’s are pairwise disjoint. It follows that
$\mathbf{v}_{2}^{\ast}:=\sum_{i\in[r]}\mathbf{q}_{i}$ satisfies
${\sqrt{\alpha}m}\geqslant 2k\Delta\alpha m\geqslant
A({\left.\kern-1.2pt\mathbf{v}_{2}^{\ast}\vphantom{\big{|}}\right|_{\operatorname{{Hom}}(\mathcal{F};R^{\prime})}})\geqslant\alpha
m$. Let $H^{\prime}=H-\bigcup V(H_{i})$. Since
$v(H^{\prime})\geqslant(1-\sqrt{\alpha})n$, we may furthermore assume that
$H^{\prime}$ (like $H$) contains $t$ disjoint proper $(k,kw)$-flexi-chromatic
subtilings and one topological $(\ell,w)$-flexi-chromatic subtiling each of
order at most $w^{\prime}\leqslant\sqrt{\xi}n$. Moreover, we also have
$\operatorname{\chi_{\rm cr}}(H^{\prime})\leqslant\operatorname{\chi_{\rm
cr}}(H)+\sqrt{\alpha}$ where the additional term of $\sqrt{\alpha}$ accounts
for the vertices deleted from $H$ which are not in the (or a) smallest colour
class of $H$. Thus
$H^{\prime}\in\mathcal{H}(n,w,\Delta;\chi+\sqrt{\alpha};t,\ell,w^{\prime})$. ∎

###### Proof of Claim 15.2.

Let us first sketch the proof of the claim. We begin by finding and allocating
the flexi-chromatic subtilings $W,W_{1},\dots,W_{t}$ with
$\mathbf{w},\mathbf{w}_{1},\dots,\mathbf{w}_{t}$. Note that the subtilings
$W_{1},\dots,W_{t}$ are proper $(k,{\sqrt{\varrho^{\prime}}rn})$-flexi-
chromatic, whereas
$H^{\prime}\in\mathcal{H}(n^{\prime},w,\Delta;\chi+\sqrt{\alpha};t,\ell,w^{\prime})$
only guarantees proper $(k,kw)$-flexi-chromatic subtilings. We achieve this by
combining the flexi-chromatic subtilings given by the assumptions with
approximate flexi-chromatic subtilings generated by Proposition 14.3.

Recall that we aim to find an allocation of $H^{\prime}$ to $R$. Next, we find
surjective allocations $\mathbf{u}_{1},\dots,\mathbf{u}_{t}$ as in 7 by a
simple greedy argument. We then delete vertices from each cluster of
$\mathcal{V}$ according to the allocation so far. This yields an approximation
$G^{\prime}\subseteq G$ which is still a tiling framework. To finish, we use
Theorem 10.1 to find an almost perfect tiling of the yet–to–be–allocated
vertices in $G^{\prime}$. From this, we derive an allocation of almost all of
the vertices of $H^{\prime}$ to $R$. Arbitrarily allocating the remaining
vertices gives $\mathbf{r}$ and thus $\mathbf{v}^{\prime}$.

Let us now turn to the details. We begin by finding the flexi-chromatic
subtilings. Write $H^{\prime}=H^{(1)}$ for sake of notational symmetry. Since
$H^{(1)}\in\mathcal{H}(n^{\prime},w,\Delta;\chi+\sqrt{\alpha};t,\ell,w^{\prime})$,
there are pairwise disjoint subgraphs
$W^{\prime},W^{\prime}_{1},\dots,W^{\prime}_{t}\subseteq H^{(1)}$ such that
$W^{\prime}_{1},\dots,W^{\prime}_{t}$ are properly $(k,kw,0)$-flexi-chromatic
and $W^{\prime}$ is topologically $(\ell,w,0)$-flexi-chromatic. Let
$H^{(2)}=H^{(1)}-V(W^{\prime}\cup\bigcup_{i\in[t]}W^{\prime}_{i})$. As each
$W_{j}^{\prime}$ has order at most
$w^{\prime}\leqslant\sqrt{\xi}n\leqslant\beta n$, it follows that
$\operatorname{\chi_{\rm cr}}(H^{(2)})\leqslant\operatorname{\chi_{\rm
cr}}(H^{(1)})+\sqrt{\beta}$. Now choose disjoint subtilings
$W_{1}^{\prime\prime},\dots,W_{t}^{\prime\prime}\subseteq H^{(2)}$, each on
$\beta n+w\pm w$ vertices such that $W_{j}^{\prime\prime}$ has
$\operatorname{\chi_{\rm
cr}}(W_{j}^{\prime\prime})\leqslant\operatorname{\chi_{\rm
cr}}(H^{(2)})+2t\beta\leqslant k-\mu/4$ for $j\in[t]$. This is possible by our
choice of parameters, in particular $\chi\leqslant k-\mu/2$. We apply
Proposition 14.3 with $W_{j}^{\prime\prime}$, $\sqrt{\xi}$ and
$2k^{5}\varrho^{\prime 1/3}$ playing the role of $H$, $\xi$ and $\tau$. It
follows that $W_{j}^{\prime\prime}$ is properly $(k,\varrho^{\prime
1/3}n,kw)$-flexi-chromatic. Let $W_{j}=W^{\prime}_{j}\cup
W_{j}^{\prime\prime}$ for $j\in[t]$. By Proposition 14.2, we see that each
$W_{j}$ is properly $(k,{\varrho^{\prime}}^{1/3}n,0)$-flexi-chromatic. Let
$H^{(3)}=H^{(2)}-\bigcup_{j\in[t]}V(W_{j}^{\prime\prime})$ and observe that
$\operatorname{\chi_{\rm cr}}(H^{(3)})\leqslant\operatorname{\chi_{\rm
cr}}(H^{(2)})+4t\beta\leqslant\operatorname{\chi_{\rm cr}}(H)+\mu/4$. For each
$j\in[t]$, consider a central proper $k$-colouring $\phi_{j}$ of $W_{j}$, and
let $\mathbf{w}_{j}$ be an allocation of $W_{j}$ to $R[e_{j}]$ that encodes
$\phi_{j}$. Similarly, let $\mathbf{w}$ be an allocation of $W$ to $R$ that
encodes a central topological $\ell$-colouring of $W$ via $J^{\prime}$, so
$\mathbf{w}$ places one colour class into each $R[f_{q}]$ for $q\in[\ell]$.
(This is possible, since $W$ is properly $k$-colourable and $R[f_{q}]$ is a
$k$-clique.) Since $W,W_{1},\dots,W_{t}$ have together at most $2t\beta
n\leqslant\alpha m$ vertices, it follows that
$A(\mathbf{w}+\sum_{j\in[t]}\mathbf{w}_{j})\leqslant\alpha m$.

Next we find $(k,\beta n)$-surjective allocations
$\mathbf{u}_{1},\dots,\mathbf{u}_{t}$ as in 7. The argument is the same as in
Claim 15.1. Fix an arbitrary $j\in[t]$. Consider any $k$-clique $K\subseteq R$
with $V(K)\in E(T_{j})$ and a vertex $i\in V(K)$. Choose a subtiling
$H_{K,i}\subseteq H^{(3)}$ of order $k\beta n\leqslant v(H_{i})\leqslant
2k\beta n$; consider a (proper) $k$-colouring of $H_{K,i}$ and note that its
largest colour class has at least $\beta n$ vertices. Let
$\mathbf{q}_{K,i}\in\mathbb{N}_{0}^{\operatorname{{Hom}}(\mathcal{F};R)}$ be
the allocation of $H_{K,i}$ to the clique $K$ such that the largest colour
class is mapped to $i\in V(K)$. Note that this allocates at most $2k\beta n$
vertices to any vertex $j$ of $K_{i}$. Since the number of $k$-cliques in $R$
is at most $r^{k}$, this allocates in total at most $2kr^{k}\beta
n\leqslant\sqrt{\beta}m$ vertices to any cluster. Similarly, the union of the
$H_{K,i}$’s has order at most $2kr^{k}\beta nt\leqslant\sqrt{\beta}m$ where we
used that the number of tight components $t$ is trivially bounded by
$e(J)\leqslant r^{k}$. Consequently, we may assume the $H_{K,i}$’s are
pairwise disjoint. It follows that $\mathbf{u}_{j}=\sum_{V(K)\in
E(T_{j})}\mathbf{q}_{K,i}$ is a $(\beta n,T_{j})$-surjective allocation of a
subtiling of $H^{(1)}$ to $R$. We remark that
$A(\sum_{j\in[t]}\mathbf{u}_{j})\leqslant t\sqrt{\beta}m\leqslant\alpha m$.
Let $H^{(4)}=H^{(3)}-\bigcup V(H_{K,i})$ and note that
$\operatorname{\chi_{\rm cr}}(H^{(4)})\leqslant\operatorname{\chi_{\rm
cr}}(H^{(3)})+\sqrt{\beta}r\leqslant\operatorname{\chi_{\rm cr}}(H)+\mu/2$.

All that remains in the proof of Claim 15.2 is to find $\mathbf{r}$. Recall
that $G$ is a $\mu$-robust $(\chi+\mu,\varrho;t,\ell)$-tiling framework on $n$
vertices and $(G,\mathcal{V})$ is a $2$-balanced $R$-partition. Note that
$\mathbf{a}:=A(\mathbf{v}_{2}^{\ast}+\mathbf{w}+\sum_{j\in[t]}(\mathbf{u}_{j}+\mathbf{w}_{j}))$
records the overall number of vertices allocated to each $i\in V(R)$ so far.
Moreover, by the above choices and 4, we have $\mathbf{a}\leqslant
2{\alpha}m+\sqrt{\alpha}m\leqslant 2{\sqrt{\alpha}m}$. We obtain a subgraph
$G^{\prime}\subseteq G$ by deleting for each $i\in[r]$, exactly
$\mathbf{a}(i)$ vertices of $V_{i}$. This is possible as $|V_{i}|\geqslant m$.
Note that $G^{\prime}$ is a $(\mu/8,\mu/8)$-approximation of $G$. Thus
$G^{\prime}$ is a $\mu/2$-robust $(\chi+\mu/2,\varrho;t,\ell)$-tiling
framework. Choose an arbitrary subtiling $H^{*}\subseteq H^{(4)}$ such that
$(1-\varrho/2)v(G^{\prime})-w\leqslant
v(H^{*})\leqslant(1-\varrho/2)v(G^{\prime})$ and $\operatorname{\chi_{\rm
cr}}(H^{*})\leqslant\operatorname{\chi_{\rm cr}}(H)+\mu/2$. Note that
$H^{*}\in\mathcal{B}(v(H^{\ast}),w,\Delta)\cap\mathcal{J}(\chi+\mu/2)$. Hence,
we can apply Theorem 10.1 with

object/parameter | $G^{\prime}$ | $H^{*}$ | $v(G^{\prime})$ | $2\xi$ | $\chi+\mu/2$ | $a$ | $b$ | $\varrho$ | $\varrho^{\prime}/2$ | $\mu/2$
---|---|---|---|---|---|---|---|---|---|---
playing the role of | $G$ | $H$ | $n$ | $\xi$ | $\chi$ | $a$ | $b$ | $\varrho$ | $\varrho^{\prime}$ | $\mu$

to find an embedding of $H^{\ast}$ to $G^{\prime}$. We encode this embedding
by an allocation
$\mathbf{r}^{\prime}\in\mathbb{N}_{0}^{\operatorname{{Hom}}(\mathcal{F};R)}$
of $H^{*}$ to $R$. Finally, we allocate the tiles in $H^{(2)}-V(H^{*})$
arbitrarily to obtain an allocation
$\mathbf{r}\in\mathbb{N}_{0}^{\operatorname{{Hom}}(\mathcal{F};R)}$ of
$H^{(2)}$ to $R$. As $v(H^{(2)})-v(H^{*})\leqslant\varrho^{\prime}n/2$ and by
the construction of $\mathbf{r}$, we have that
$\mathbf{v}^{\prime}:=\mathbf{r}+\mathbf{w}+\sum_{j\in[t]}(\mathbf{u}_{j}+\mathbf{w}_{j})$
satisfies $\lVert
A\mathbf{v}^{\prime}-\mathbf{b}^{\prime}\rVert_{1}\leqslant\varrho^{\prime}n$.

Finally, let
$\mathbf{c}^{\prime}=A\mathbf{v}^{\prime}-\mathbf{b}^{\prime}\in\mathbb{N}_{0}^{V(R)}$.
By the last paragraph, we have ${|\sum_{i\in
V(L_{q})}\mathbf{c}^{\prime}(i)|}\leqslant{\sum_{i\in
V(L_{q})}|\mathbf{c}^{\prime}(i)|}\leqslant{\varrho^{\prime}}n$ for each
$q\in[\ell]$. In fact, we can assume that ${|\sum_{i\in
V(L_{q})}\mathbf{c}^{\prime}(i)|}\leqslant w$ for each $q\in[\ell]$. This is
indeed possible as $\sum_{i\in[r]}\mathbf{c}^{\prime}(i)=0$ which holds as
$\mathbf{v}^{\prime}$ is an allocation of all of $H$ to $R$. So repeatedly
reallocating a tile of $H$ (of order at most $w$) from the induced graph
$R[V(L_{q})]$ that maximises the sum of $\mathbf{c}^{\prime}$ on its vertices
to the $R[V(L_{q^{\prime}})]$ that minimises it, eventually gives the desired
result. ∎

###### Proof of Claim 15.3.

The idea is to construct the $\mathbf{c}_{j}$’s inductively with the
additional condition that
$\lVert\mathbf{c}_{j}\rVert_{\infty}\leqslant(2r)^{t}{\varrho^{\prime}}n$.
Note that this gives 11, since
$(2r)^{t}{\varrho^{\prime}}n\leqslant\sqrt{\varrho^{\prime}}n$. Recall
$T_{1},\dots,T_{t}$ are the tight components of $J^{\prime}$ and that
$L(J^{\prime})$ is the graph with vertex set $\\{T_{1},\dots,T_{t}\\}$ and
$T_{i}T_{j}$ is an edge if $V(T_{i})\cap V(T_{j})\neq\emptyset$ and $i\neq j$.
Moreover, we call the union of a set of $T_{j}$’s that form a connected
component in $L(J^{\prime})$, a loose component, and denote these by
$L_{1},\dots,L_{\ell}\subseteq J^{\prime}$. By (15.2), we have
$\lVert\mathbf{c}\rVert_{1}\leqslant r{\varrho^{\prime}}n$ and $\sum_{i\in
V(L_{q})}\mathbf{c}(i)=0$ for all $q\in[\ell]$. For simplicity, let us first
assume that $\ell=1$. Thus we simply have $\sum_{i\in[r]}\mathbf{c}(i)=0$.

We prove the claim by induction on $t$. The base case is trivial as we then
set $c_{1}=c$. Suppose now that the claim holds for $t^{\prime}<t$. Consider a
leaf $T_{t}\in V(L(J^{\prime}))$ of a spanning tree in $L(J^{\prime})$, which
is adjacent (in the spanning tree) to, say, $T_{t-1}\in V(L(J^{\prime}))$. By
definition of $L(J^{\prime})$, there is some $i^{\ast}\in V(T_{t})\cap
V(T_{t-1})$. We then define $\mathbf{c}_{t}\in\mathbb{Z}^{V(R)}$ by setting
$\mathbf{c}_{t}(i^{\ast})=\mathbf{c}(i^{\ast})-\sum_{i\in
V(T_{t})}\mathbf{c}(i)$, $\mathbf{c}_{t}(j)=\mathbf{c}(j)$ for all $j\in
V(T_{t})\setminus\\{i^{\ast}\\}$ and $\mathbf{c}_{t}(j)=0$ otherwise. Clearly,
$\sum_{i\in[r]}\mathbf{c}_{t}(i)=0$. Moreover,
$\lVert\mathbf{c}_{t}\rVert_{\infty}\leqslant
v(T_{t})\lVert\mathbf{c}\rVert_{\infty}\leqslant
r\lVert\mathbf{c}\rVert_{\infty}$.

Now let ${\tilde{J}}$ be obtained from $J^{\prime}$ by deleting the edges of
$T_{t}$ and the vertices contained in no other component than $T_{t}$. Since
$T_{t}$ was a leaf in a spanning tree of $L(J^{\prime})$, it follows that
$L({\tilde{J}})$ is still connected. Let
$\mathbf{\tilde{c}}=\mathbf{c}-\mathbf{c}_{t}$, and note that
$\lVert\mathbf{\tilde{c}}\rVert_{\infty}\leqslant
2v(T_{t})\lVert\mathbf{c}\rVert_{\infty}\leqslant
2r\lVert\mathbf{c}\rVert_{\infty}$. Hence we may use induction where
$\mathbf{\tilde{c}}$ plays the role of $\mathbf{c}$ to obtain
$\mathbf{c}_{1},\dots,\mathbf{c}_{{t-1}}\in\mathbb{Z}^{V(R)}$ satisfying the
statement (for $t^{\prime}=t-1$). In particular, we have
$\lVert\mathbf{c}_{j}\rVert_{\infty}\leqslant(2r)^{t-1}\lVert\mathbf{c}^{\prime}\rVert_{\infty}\leqslant(2r)^{t}\lVert\mathbf{c}\rVert_{\infty}$
for all $j\in[t-1]$. Thus $\mathbf{c}_{1},\dots,\mathbf{c}_{t}$ present the
desired solution. This concludes the analysis for $\ell=1$.

When $\ell>1$ we can use the same arguments separately on each of the loose
components, which is possible since $\sum_{i\in V(L_{q})}\mathbf{c}(i)=0$ for
all $q\in[\ell]$ and the loose components are vertex-disjoint. ∎

This completes the proof of Lemma 11.2. ∎

##  16\. Conclusion

In this paper, we conduct a systematic investigation of the question when a
dense host graph $G$ contains a (potentially spanning) guest graph $H$ where
$H$ has bounded maximum degree and where each component of $H$ may be huge,
but of smaller magnitude than the order of $G$. In particular, we study this
topic beyond the usual setting where one seeks for the optimal minimum degree
bound that guarantees the existence of a copy of $H$ in $G$. This has several
advantages as for example it covers many other natural conditions a host graph
may satisfy apart from (optimal) minimum degree conditions and it makes our
proof more modular. Nevertheless, our paper is by no means the end of the
story and there are a few interesting questions that remain.

We applied our framework to degree conditions and degree sequences. A related,
introduced by Ore [34], imposes a lower bound on the sum of the degrees of any
two non-adjacent vertices. Such Ore-type conditions have been investigated for
of perfect matchings [19] and $F$-tilings [26]. Our framework generally
applies to such problems after minor workarounds (see [27]). Hence, one can
extend the results of Kühn, Osthus and Treglown [26] to mixed tilings using
already established structural insights similar as in the proof of Theorem
5.7. On the other hand, in its current state our framework is unable to
reproduce these results for $F$-tilings with fixed $F$. This is because the
Ore-type ‘threshold’ that guarantees that every vertex of the host graph lies
in a copy of $F$ can be significantly lower than the ‘threshold’ for the
linkage property, in the cases when $F$ is not a bottle. To overcome this
limitation, we can define _$F$ -frameworks_ by replacing the space condition
in Definition 1.6 with an (almost) perfect fractional $F$-tiling and the
linkage condition with the property that every vertex is on a copy of $F$. It
is then not hard to see that the proof of Theorem 1.7 can be modified to show
that robust $F$-frameworks lead to perfect $F$-tilings. Given this, the
results of Kühn, Osthus and Treglown [26] can be fully replicated.

Turning to more general questions. The literature on spanning substructures
has so far identified three natural barriers to finding perfect tilings, which
correspond to obstacles in space, divisibility and local conditions. Very
recently, Freschi and Treglown [11] asked whether (in an approximate sense) it
can be proved that these are the only obstructions. Our work solves this ‘meta
problem’ for mixed tilings, since the space, divisibility and linkage
conditions of Definition 1.6 certify that each of the above obstacles can be
(individually) overcome.

In a similar vein, there has also been recently quite some research activity
on graph tilings in related settings such as directed graphs [7, 40], ordered
graphs [4, 11], multipartite graphs [32], random graphs [9] and in the
discrepancy setting [3]. We expect that many ideas of our paper also apply in
these cases and think it is an interesting and fruitful task to set up
respective frameworks.

While $F$-tilings of graphs have been an integral and well-studied question
for graphs not so much is known for uniform hypergraphs [18, 30, 33]; even an
analogous Hajnal–Szemerédi result seems currently out of reach. It would be
very interesting, but potentially also very challenging, to approach
hypergraph tilings from a framework viewpoint. The idea would be to identify
similar, rather abstract, conditions as in Definition 1.6 and prove that these
are sufficient to find an $F$-tiling. Once such a result is obtained, it only
remains to verify that these abstract conditions in fact are satisfied given
the host hypergraph admits certain minimum degree properties; however, this
might turn out to be the most difficult part.

## Acknowledgments

We would like to thank Andrew Treglown for stimulating discussions and
bringing the work of Ishigami [16, 17] to our attention.

## References

  * [1] P. Allen, J. Böttcher, H. Hàn, Y. Kohayakawa, and Y. Person, _Blow-up lemmas for sparse graphs_ , arXiv:1612.00622 (2016).
  * [2] N. Alon and R. Yuster, _$H$ -factors in dense graphs_, J. Combin. Theory Ser. B 66 (1996), 269–282.
  * [3] J. Balogh, B. Csaba, A. Pluhár, and A. Treglown, _A discrepancy version of the Hajnal–Szemerédi theorem_ , Comb. Probab. Comput. 30 (2021), 444–459.
  * [4] J. Balogh, L. Li, and A. Treglown, _Tilings in vertex ordered graphs_ , arXiv:2007.10832 (2020).
  * [5] J. Böttcher, M. Schacht, and A. Taraz, _Spanning 3-colourable subgraphs of small bandwidth in dense graphs_ , J. Combin. Theory Ser. B 98 (2008), 752–777.
  * [6] D. Conlon, J. Fox, and H. Pham, _Subset sums, completeness and colorings_ , arXiv:2104.14766 (2021).
  * [7] A. Czygrinow, L. DeBiasio, T. Molla, and A. Treglown, _Tiling directed graphs with tournaments_ , Forum of Mathematics, Sigma 6 (2018), 53 pp.
  * [8] O. Ebsen, G. Maesaka, Chr. Reiher, M. Schacht, and B. Schülke, _Embedding spanning subgraphs in uniformly dense and inseparable graphs_ , Random Structures Algorithms 57 (2020), 1077–1096.
  * [9] A. Ferber and M. Kwan, _Dirac-type theorems in random hypergraphs_ , arXiv:2006.04370 (2020).
  * [10] P. Frankl and N. Tokushige, _Extremal problems for finite sets_ , vol. 86, American Mathematical Soc., 2018.
  * [11] A. Freschi and A. Treglown, _Dirac-type results for tilings and coverings in ordered graphs_ , arXiv:2112.02909 (2021).
  * [12] F. Garbe, R. Lang, A. Lo, R. Mycroft, and N. Sanhueza-Matamala, _Lehel’s conjecture for $3$-uniform hypergraphs_, in preparation (2021).
  * [13] A. Hajnal and E. Szemerédi, _Proof of a conjecture of P. Erdős_ , Combinatorial theory and its applications, II (Proc. Colloq., Balatonfüred, 1969), 1970, pp. 601–623.
  * [14] J. Hyde, H. Liu, and A. Treglown, _A degree sequence Komlós theorem_ , SIAM J. Discrete Math. 33 (2019), 2041–2061.
  * [15] J. Hyde and A. Treglown, _A degree sequence version of the Kühn-Osthus tiling theorem_ , Electron. J. Combin. (2020), P3–48.
  * [16] Y. Ishigami, _Almost-spanning subgraphs with bounded degree in dense graphs_ , Eur. J. Comb. 23 (2002), no. 5, 583–612.
  * [17] by same author, _A common extension of the Erdős–Stone Theorem and the Alon–Yuster theorem for unbounded graphs_ , Eur. J. Comb. 23 (2002), no. 4, 431–448.
  * [18] P. Keevash and R. Mycroft, _A geometric theory for hypergraph matching_ , vol. 233, Amer. Math. Soc., 2015.
  * [19] H. A. Kierstead and A. V. Kostochka, _An Ore-type theorem on equitable coloring_ , J. Combin. Theory Ser. B 98 (2008), no. 1, 226–234.
  * [20] J. Komlós, _Tiling Turán theorems_ , Combinatorica 20 (2000), 203–218.
  * [21] J. Komlós, G. N. Sárközy, and E. Szemerédi, _Blow-Up Lemma_ , Combinatorica 17 (1997), 109–123.
  * [22] J. Komlós, G. N. Sárközy, and E. Szemerédi, _Proof of the Alon-Yuster conjecture_ , vol. 235, 2001, Combinatorics (Prague, 1998), pp. 255–269.
  * [23] J. Komlós and M. Simonovits, _Szemerédi’s Regularity Lemma and its applications in graph theory_ , Combinatorics, Paul Erdős is Eighty (D. Miklós, V. T. Sós, and T. Szőnyi, eds.), vol. 2, Bolyai Society Mathematical Studies, 1996, pp. 295–352.
  * [24] D. Kühn and D. Osthus, _The minimum degree threshold for perfect graph packings_ , Combinatorica 29 (2009), 65–107.
  * [25] D. Kühn, D. Osthus, and A. Taraz, _Large planar subgraphs in dense graphs_ , J. Combin. Theory Ser. B 95 (2005), 263–282.
  * [26] D. Kühn, D. Osthus, and A. Treglown, _An Ore-type theorem for perfect packings in graphs_ , SIAM Journal on Discrete Mathematics 23 (2009), no. 3, 1335–1355.
  * [27] R. Lang and N. Sanhueza-Matamala, _On sufficient conditions for hamiltonicity in dense graphs_ , arXiv:2110.14547 (2021).
  * [28] by same author, _Minimum degree conditions for tight Hamilton cycles_ , to appear in J. Lond. Math. Soc. (2022).
  * [29] V. F. Lev, _Consecutive integers in high-multiplicity sumsets_ , Acta Math. Hung. 129 (2010), 245–253.
  * [30] A. Lo and K. Markström, _A multipartite version of the Hajnal–Szemerédi theorem for graphs and hypergraphs_ , Comb. Probab. Comput. 22 (2013), 97–111.
  * [31] by same author, _$F$ -factors in hypergraphs via absorption_, Graphs Combin. 31 (2015), 679–712.
  * [32] R. Martin and J. Skokan, _Asymptotic multipartite version of the Alon–Yuster theorem_ , J. Combin. Theory Ser. B 127 (2017), 32–52.
  * [33] R. Mycroft, _Packing k-partite k-uniform hypergraphs_ , J. Combin. Theory Ser. A 138 (2016), 60–132.
  * [34] O. Ore, _Note on Hamilton circuits_ , Amer. Math. Monthly 67 (1960), 55.
  * [35] D. Piguet and M. Saumell, _A median-type condition for graph tiling_ , Eur. J. Comb. 77 (2019), 90–101.
  * [36] L. Pósa, _A theorem concerning Hamilton lines_ , Magyar Tud. Akad. Mat. Kutató Int. Közl 7 (1962), 225–226.
  * [37] A. Shokoufandeh and Y. Zhao, _Proof of a tiling conjecture of Komlós_ , Random Structures Algorithms 23 (2003), 180–205.
  * [38] K. Staden and A. Treglown, _The bandwidth theorem for locally dense graphs_ , Forum Math. Sigma 8 (2020), 42 pp.
  * [39] E. Szemerédi, _Regular partitions of graphs_ , Colloq. Internat. CNRS 260 (1976), 399–401.
  * [40] A. Treglown, _A degree sequence Hajnal–Szemerédi theorem_ , J. Combin. Theory Ser. B 118 (2016), 13–43.

##  Appendix A Fractional Tilings Under Degree Conditions

In this section we show Lemma 5.3 whose proof is adapted from Piguet and
Saumell [35]. Let $G$ and $F$ be graphs. We say that $c\colon
V(G)\to\operatorname{{Hom}}(F;G)$ is a _fractional $F$-cover_ if
$\sum_{v\in\text{Im}(\theta)}c(v)\geqslant 1$ for every
$\theta\in\operatorname{{Hom}}(F;G)$. The _size_ of this cover is $\sum_{v\in
V(G)}c(v)$. Moreover, the size of a fractional $F$-tiling
$\omega\colon\operatorname{{Hom}}(F;G)\rightarrow[0,1]$ is its weight divided
by $v(F)$. Thus the size of the minimum fractional $F$-cover of a graph $G$ is
equal to the size of the maximum fractional $F$-tiling by the duality of
linear programmes.

###### Proof of Lemma 5.3.

Let $k=\lceil\chi\rceil$ and $\delta=1-\frac{1}{\chi}$. We may assume that
$\operatorname{\chi_{\rm cr}}(F)=\chi$ and that $F$ is complete multipartite
as there is a complete $k$-partite supergraph of $F$ of the same order with
the same critical chromatic number. Let $f_{k}\leqslant\ldots\leqslant f_{1}$
be the sizes of the parts of $F$ and let $f=\sum_{i\in[k]}f_{i}$. Note that
$1-\delta=\frac{1-f_{k}/f}{k-1}$ by definition of $\operatorname{\chi_{\rm
cr}}(F)=\chi$. We show that a minimum $F$-cover of the graph has at least size
$n/f$ which implies the desired statement.

Let $c\colon V(G)\to\mathbb{R}$ be a minimum size $F$-cover. Pick a $k$-clique
with vertices $v_{1},\dots,v_{k}$ which has a smallest cover with respect to
the lexicographical ordering. Equivalently we can think of this $k$-clique as
the outcome of the following greedy procedure. Take $v_{1}$ to be a vertex
$v\in V(G)$ that takes the minimal value of $c(v)$. Given we have chosen
$v_{1},\dots,v_{i}$, let $v_{i+1}$ be the vertex
$v\in\bigcap_{j\in[i]}N(v_{j})$ that minimises $c(v)$ over all vertices in
$\bigcap_{j\in[i]}N(v_{j})$. Crucially, by the degree conditions
$\bigcap_{j\in[i]}N(v_{j})\neq\emptyset$ for all $i\in[k-1]$. Since $F$ is
$k$-colourable, we have in particular

$\displaystyle\sum_{i\in[k]}c(v_{i})f_{i}\geqslant 1.$ (A.1)

By observing that all vertices $v$ in $\bigcap_{j\in[i]}N(v_{j})$ satisfy
$c(v)\geqslant c(v_{i+1})$ for each $i\in[k]$, we obtain

$\displaystyle\sum_{v\in V(G)}c(v)$ $\displaystyle\geqslant c(v_{1})\cdot
n+\sum_{i\in[k-1]}(c(v_{i+1})-c(v_{i}))\cdot\left|\bigcap_{j\in[i]}N(v_{j})\right|$
$\displaystyle\geqslant c(v_{1})\cdot
n+\sum_{i\in[k-1]}(c(v_{i+1})-c(v_{i}))\cdot(1-i(1-\delta))n.$

Calculations and using the definitions of $f_{k}$ and $\delta$ yield

$\displaystyle\sum_{v\in V(G)}c(v)$
$\displaystyle{\geqslant}\sum_{i\in[k-1]}c(v_{i})\cdot(1-\delta)n+c(v_{k})\cdot\frac{f_{k}}{f}n$
$\displaystyle\geqslant\frac{n}{f}\left(\frac{f-f_{k}}{k-1}\sum_{i\in[k-1]}c(v_{i})+c(v_{k})f_{k}\right).$

Recall that $f_{1}\geqslant f_{2}\geqslant\dots\geqslant f_{k}$. Thus, if
$x_{1}\leqslant\dots\leqslant x_{k}$ then

$\sum_{i\in[k]}x_{i}f_{i}=x_{k}f_{k}+\sum_{i\in[k-1]}x_{i}f_{i}\leqslant
x_{k}f_{k}+\left(\frac{\sum_{i\in[k-1]}f_{i}}{k-1}\right)\sum_{i\in[k-1]}x_{i}=x_{k}f_{k}+\left(\frac{f-f_{k}}{k-1}\right)\sum_{i\in[k-1]}x_{i}.$

Replacing $x_{i}$ by $c(v_{i})$ in the above and using (A.1) therefore gives

$\sum_{v\in V(G)}c(v)\geqslant\frac{n}{f}.$

By the duality of linear programmes, this implies that the size of the maximum
fractional $F$-tiling of $G$ is $n/f$. Thus this tiling is perfect and this
completes the proof. ∎

##  Appendix B Robustness and regularity

In this section, we show Propositions 8.1 and 8.2.

###### Proof of Proposition 8.1.

The proof proceeds as follows. We translate the statement of the proposition
into a statement that there are many cliques “adjacent” to the neighbourhood
of an arbitrary vertex $v$. By $\mu$-robustness we cannot delete all said
cliques by deleting a proportion of $\mu$ edges and so by the Graph Removal
Lemma there are many such cliques.

To this end, let $v\in V(G)$ be an arbitrary vertex. Let $G_{v}\subseteq G-v$
be the subgraph containing all the edges that are incident to a neighbour of
$v$ in $G$. Consider a $k$-clique $K$ in $N_{G}(v)$. As all edges in $G_{v}$
have one endpoint in $N_{G}(v)$ we see that $K$ has at least $k-1$ vertices in
$N_{G}(v)$. It follows that these $k-1$ vertices, together with $v$, form a
$k$-clique. Thus the edge in $K_{k}(G)$ corresponding to $K$ is linked to $v$.
Conversely any linked edge $e$ of $v$ in $K_{k}(G)$ corresponds to a unique
$k$-clique in $G_{v}$. Indeed, let $K$ be the $k$-clique in $G$ corresponding
to $e$. By the definition of linkage, $K$ must intersect $N_{G}(v)$ in at
least $k-1$ vertices, and thus all edges of $K$ have at least one endvertex in
$N_{G}(v)$. Thus the proposition holds if and only if $G_{v}$ contains at
least $\mu^{\prime}n^{k}$ many $k$-cliques.

Now in order to apply the Graph Removal Lemma, we want to show that, after the
removal of any $(\mu^{2}/8)n^{2}$ edges from $G_{v}$, at least one $k$-clique
remains in $G_{v}$. Indeed, suppose we remove a set $Y$ of $(\mu^{2}/8)n^{2}$
edges from $G_{v}$. Double-counting reveals that at most $(\mu/2)n$ vertices
have more than $(\mu/2)n$ edges removed from them. Let $X$ be the set of those
vertices. Note that, in particular since $v\notin V(G_{v})$, we certainly have
$v\notin X$. In $G$, remove $Y$ from $E(G)$ and remove $X$ from $V(G)$ to
obtain a subgraph $G^{\prime}\subseteq G$. Note that $v\in V(G^{\prime})$.
Clearly, $G^{\prime}$ is a $(\mu,\mu)$-approximation of $G$. Since $G$ is a
$\mu$-robust $(\chi,\varrho;t,\ell)$-tiling framework, we deduce that
$G^{\prime}$ is a $(\chi,\varrho;t,\ell)$-tiling framework. Since $v\in
V(G^{\prime})$, it follows from the definition of a tiling framework that $v$
has a linked edge in $G^{\prime}$. Assuming $n$ is sufficiently large, we have
shown that $G_{v}$ satisfies the assumptions of the Graph Removal Lemma. Thus
there exists $\mu^{\prime}=\mu^{\prime}(\mu,k)>0$ such that the number of
$k$-cliques in $G_{v}$ is at least $\mu^{\prime}n^{k}$, as desired. ∎

###### Proof of Proposition 8.2.

Let $R^{\prime}\subseteq R$ be an arbitrary $(\mu,\mu)$-approximation of $R$.
If we can show that $R^{\prime}$ is a $(\chi,\varrho;t,\ell)$-tiling
framework, then we have proved the result. We will show that the three
properties of a tiling framework transfer from $G$ to $R^{\prime}$ in turn,
observing that components are maintained, fractional tilings can be translated
and finally, using Proposition 8.1, linked edges for every vertex in
$R^{\prime}$ exist.

To this end, let $\mathcal{V}^{\prime}$ be obtained from $\mathcal{V}$ by
deleting the clusters whose indices are not in $V(R^{\prime})$. We obtain
$G^{\prime}\subseteq G$ by deleting all vertices of clusters $V_{i}$ with
$i\notin V(R^{\prime})$ and all edges between $V_{i}$ and $V_{j}$ whenever
$ij\notin E(R^{\prime})$. Let $m$ denote the common cluster size of
$\mathcal{V}$. Since $n=mr$ and $1/n\ll 1/r\ll\mu$, it follows that
$G^{\prime}$ is a $(\frac{3}{2}\mu)$-approximation of $G$. By our robustness
assumption, $G^{\prime}$ is a $\mu/2$-robust $(\chi,\varrho;t,\ell)$-tiling
framework.

Returning to $R^{\prime}$, we consider its tight and loose components. Observe
that every $k$-clique in $G^{\prime}$ is contained in the cluster of a
$k$-clique of $R^{\prime}$ and so every tight or loose component of
$G^{\prime}$ corresponds to a tight, respectively loose, component in
$R^{\prime}$. Recall that by definition of $R$-partitions, the clusters of
$\mathcal{V}$ contain no edges of $G$. Moreover, whenever there is an edge in
$G$ between to clusters $V_{i}$ and $V_{j}$, the edges $ij$ is present in $R$.
It follows that the tight and loose components of $R^{\prime}$ correspond to
unions of the tight and loose components of $G^{\prime}$. Since there are at
most $t$ tight components that cover all vertices of $G^{\prime}$, there are
thus at most $t$ tight components that cover all vertices of $R^{\prime}$. The
same holds for loose components with $\ell$ in place of $t$.

Now for the almost perfect tiling of $R^{\prime}$. Define a homomorphism
$\eta\colon V(G^{\prime})\rightarrow V(R^{\prime})$ by setting $\eta(v)=i$ if
$v\in V_{i}$. Recall that $B_{\chi}$ is the $k$-partite complete graph
$B_{\chi}$ where $k=\lceil\chi\rceil$ and $a,b$ are coprime with
$\chi=(k-1)+a/b$. Consider a $(1-\varrho)$-perfect fractional
$B_{\chi}$-tiling
$\mathbf{w}\colon\operatorname{{Hom}}(B_{\chi};G^{\prime})\to[0,1]$. We
construct a $(1-\varrho)$-perfect fractional $B_{\chi}$-tiling
$\mathbf{w}^{\prime}\colon\operatorname{{Hom}}(B_{\chi};R^{\prime})\to[0,1]$
using our homomorphism $\eta$ to define a map from
$\operatorname{{Hom}}(B_{\chi};G^{\prime})$ to
$\operatorname{{Hom}}(B_{\chi};R^{\prime})$ as follows. For each
$\theta\in\operatorname{{Hom}}(B_{\chi};R^{\prime})$, set
$\mathbf{w}^{\prime}(\theta)$ to be the sum of the weights
$\mathbf{w}(\theta^{\prime})/m$ over all homomorphisms
$\theta^{\prime}\in\operatorname{{Hom}}(B_{\chi};G^{\prime})$ that that
satisfy $\eta\circ\theta^{\prime}=\theta$. Note that,
$\mathbf{w}^{\prime}(\theta)\leqslant 1$, since the size of the weights
$\mathbf{w}(\theta^{\prime})$ sum to at most $m$ (the size of the clusters)
for each $\theta$ as $\mathbf{w}\in[0,1]$. Let $s\geqslant(1-\varrho)n$ be the
weight of $\mathbf{w}$. Since every $\mathbf{w}(\theta^{\prime})$ is used
exactly once in the definition of $\mathbf{w}^{\prime}$, it follows that
$\mathbf{w}^{\prime}$ has weight
$s/m\geqslant(1-\varrho)n/m\geqslant(1-\varrho)r$. In other words,
$\mathbf{w}^{\prime}$ is a $(1-\varrho)$-perfect $B_{\chi}$-tiling of
$R^{\prime}$.

Finally, we show that $K_{k}(R^{\prime})$ is linked. Since $G^{\prime}$ is a
$\mu/2$-robust $(\chi,\varrho;t,\ell)$-tiling framework, it follows by
Proposition 8.1 that every vertex $v$ of $G^{\prime}$ has at least
$\mu^{\prime}n^{k}$ linked edges in $K_{k}(G^{\prime})$ for $\varrho\ll
1/r\ll\mu^{\prime}\ll 1/\chi,\mu$. Consider an arbitrary vertex $i\in
V(R^{\prime})$. Let $v\in V_{i}$. Since $\mu^{\prime}n$ is much larger than
$m=n/r$, it follows that $v$ must have a linked edge whose vertices are
outside of $V_{i}$. So as $(G,\mathcal{V})$ is an $R^{\prime}$-partition, $i$
must have a linked edge in $R^{\prime}$. This yields that $K_{k}(R^{\prime})$
is linked. Together with the above, this implies that $R^{\prime}$ is a
$(\chi,\varrho;t,\ell)$-tiling framework. ∎

###### Proof of Proposition 8.3.

Let $T_{1},\dots,T_{s}$ be the tight components of $G$. Fix $1\leqslant
q\leqslant s$ which maximises $e(T_{q})/e(\partial T_{q})$. By the definition
of tight components, we have $\sum_{i=1}^{s}e(T_{i})=e(G)$ and
$\sum_{i=1}^{s}e(\partial T_{i})=e(\partial G)$. It follows that

$\displaystyle e(G)=\sum_{i\in[s]}e(T_{i})\leqslant\frac{e(T_{q})}{e(\partial
T_{q})}\sum_{i\in[s]}e(\partial T_{i})=\frac{e(T_{q})}{e(\partial
T_{q})}e(\partial G).$

Now let $T=T_{q}$. By the above, we have $e(T)\geqslant e(\partial
T)e(G)/\binom{n}{k-1}\geqslant e(\partial
T)(1+\varepsilon)\mu\binom{n}{k}/\binom{n}{k-1}$. Let $x\in\mathbb{R}$ satisfy
$e(T)=\binom{xn}{k}$. It follows by the Theorem 5.1 that $e(\partial
T)\geqslant\binom{xn}{k-1}$. Hence
$\binom{xn}{k}\geqslant\binom{xn}{k-1}(1+\varepsilon)\mu\binom{n}{k}/\binom{n}{k-1}$.
Using that $\binom{yn}{\ell}\approx y^{\ell}\binom{n}{\ell}$ for
$\ell\leqslant k$ and our choice of $\varepsilon$, this solves to
$x\geqslant\mu$. Hence the result follows. ∎