# Graph tilings in incompatibility systems

Jie Hua Hao Lia Yue Wangb Donglei Yangc
a Laboratoire Interdisciplinaire des Sciences du Numérique,
CNRS–Université Paris-Saclay, Orsay 91405, France
b School of Mathematics,
Shandong University, Jinan 250100, China
c Data Science Institute,
Shandong University, Jinan 250100, China
Data Science Institute, Shandong University, Shandong, China. Email:
<EMAIL_ADDRESS>Supported by the China Postdoctoral Science Foundation
(2021T140413), Natural Science Foundation of China (12101365) and Natural
Science Foundation of Shandong Province (ZR2021QA029).

###### Abstract

Given two graphs $H$ and $G$, an _$H$ -tiling_ of $G$ is a collection of
vertex-disjoint copies of $H$ in $G$ and an _$H$ -factor_ is an $H$-tiling
that covers all vertices of $G$. Kühn and Osthus managed to characterize, up
to an additive constant, the minimum degree threshold which forces an
$H$-factor in a host graph $G$. In this paper we study a similar tiling
problem in a system that is locally bounded. An _incompatibility system_
$\mathcal{F}$ over $G$ is a family $\mathcal{F}=\\{F_{v}\\}_{v\in V(G)}$ with
$F_{v}\subseteq\\{\\{e,e^{\prime}\\}\in{E(G)\choose 2}:e\cap
e^{\prime}=\\{v\\}\\}$. We say that two edges $e,e^{\prime}\in E(G)$ are
_incompatible_ if $\\{e,e^{\prime}\\}\in F_{v}$ for some $v\in V(G)$, and
otherwise _compatible_. A subgraph $H$ of $G$ is _compatible_ if every pair of
edges in $H$ are compatible. An incompatibility system $\mathcal{F}$ is
_$\Delta$ -bounded_ if for any vertex $v$ and any edge $e$ incident with $v$,
there are at most $\Delta$ two-subsets in $F_{v}$ containing $e$. This notion
was partly motivated by a concept of transition system introduced by Kotzig in
1968, and first formulated by Krivelevich, Lee and Sudakov to study the
robustness of Hamiltonicity of Dirac graphs.

We prove that for any $\alpha>0$ and any graph $H$ with $h$ vertices, there
exists a constant $\mu>0$ such that for any sufficiently large $n$ with $n\in
h\mathbb{N}$, if $G$ is an $n$-vertex graph with
$\delta(G)\geq(1-\frac{1}{\chi^{*}(H)}+\alpha)n$ and $\mathcal{F}$ is a $\mu
n$-bounded incompatibility system over $G$, then there exists a compatible
$H$-factor in $G$, where the value $\chi^{*}(H)$ is either the chromatic
number $\chi(H)$ or the critical chromatic number $\chi_{cr}(H)$ and we
provide a dichotomy. Moreover, the error term $\alpha n$ is inevitable in
general case. Unlike in the previous work of Kühn and Osthus on embedding
$H$-factors, our proof uses the lattice-based absorption method.

##  1 Introduction

All the graphs considered here are finite, undirected and simple. Let $H$ be
an $h$-vertex graph and $G$ be an $n$-vertex graph. An _$H$ -tiling_ is a
collection of vertex-disjoint copies of $H$ in $G$. An _$H$ -factor_ (or
_perfect $H$-tiling_) is an $H$-tiling which covers all vertices of $G$. Note
that $n\in h\mathbb{N}$ is a necessary condition for $G$ containing an
$H$-factor.

###  1.1 Perfect graph tilings

One of the most fundamental research topics in extremal graph theory is to
determine sufficient conditions forcing spanning structures, such as perfect
matchings, Hamilton cycles, $H$-factors, etc. Textbook results of Hall and
Tutte give a sufficient condition for the existence of a perfect matching (see
e.g. [20]). A classical theorem of Dirac [21] states that every graph $G$ on
$n\geq 3$ vertices with minimum degree $\delta(G)\geq n/2$ contains a Hamilton
cycle. More often, a _Dirac graph_ is an $n$-vertex graph with minimum degree
at least $n/2$, where $n\geq 3$. For $H$-factors, when $H=K_{k}$, the seminal
Hajnal–Szemerédi theorem [25] characterizes the minimum degree forcing a
$K_{k}$-factor and the bound is best possible.

######  Theorem 1.1 (Hajnal and Szemerédi [25]).

Let $G$ be an $n$-vertex graph with $n\in k\mathbb{N}$. If
$\delta(G)\geq\left(1-1/k\right)n$, then $G$ contains a $K_{k}$-factor.

Up to an error term, the following theorem of Alon and Yuster [4] generalizes
Theorem 1.1.

######  Theorem 1.2 (Alon and Yuster [4]).

For every $\alpha>0$ and every graph $H$ there exists an integer $n_{0}$ such
that every graph $G$ whose order $n\geq n_{0}$ is divisible by $|H|$ and whose
minimum degree is at least $(1-1/\chi(H)+\alpha)n$ contains an $H$-factor.

Later, it was proved by Komlós, Sárközy and Szemerédi [33] that the $o(n)$
term can be replaced with a constant $C=C(H)$, which resolves a conjecture of
Alon and Yuster [4]. As given in [15, 29], there are graphs $H$ for which the
term $1-1/\chi(H)$ in the minimum degree condition can be improved
significantly. To illustrate this, Komlós [32] introduced the concept of
critical chromatic number. The _critical chromatic number_ $\chi_{cr}(H)$ of a
graph $H$ is defined as $(\chi(H)-1)|H|/(|H|-\sigma(H))$, where $\sigma(H)$
denotes the minimum size of the smallest color class in a coloring of $H$ with
$\chi(H)$ colors. Note that $\chi(H)-1<\chi_{cr}(H)\leq\chi(H)$. Komlós [32]
proved that one can replace $\chi(H)$ with $\chi_{cr}(H)$ at the price of
obtaining an $H$-tiling covering all but $\varepsilon n$ vertices, and he also
conjectured that the error term $\varepsilon n$ can be replaced with a
constant that only depends on $H$. This was confirmed by Shokoufandeh and Zhao
[51].

######  Theorem 1.3 (Shokoufandeh and Zhao [51]).

For any $H$ there is an $n_{0}$ so that if $G$ is a graph on $n\geq n_{0}$
vertices and minimum degree at least $(1-1/\chi_{cr}(H))n$, then $G$ contains
an $H$-tiling that covers all but at most $5|H|^{2}$ vertices.

Further, a significant result of Kühn and Osthus [43] managed to characterize,
up to an additive constant, the best possible minimum degree condition which
forces an $H$-factor. To state their result, we need more definitions here.
Let $\chi(H)=k$ and $\mathcal{C}(H)$ be the family of all proper $k$-colorings
of $H$. Given a $k$-coloring $c$ in $\mathcal{C}(H)$, let
$h_{1}^{c}\leq\cdots\leq h_{k}^{c}$ be the sizes of the color classes of $c$
and $D(c):=\\{h_{i+1}^{c}-h_{i}^{c}\mid i\in[k-1]\\}$. Let

$D(H):=\bigcup_{c\in\mathcal{C}(H)}D(c).$

Then we denote by $\mathrm{hcf}_{\chi}(H)$ the highest common factor of all
the integers in $D(H)$. In particular, if $D(H)=\\{0\\}$, then we set
$\mathrm{hcf}_{\chi}(H):=\infty$. Also, we write $\mathrm{hcf}_{c}(H)$ for the
highest common factor of all the orders of components of $H$. If $\chi(H)>2$,
then define $\mathrm{hcf}(H)=1$ if $\mathrm{hcf}_{\chi}(H)=1$. If $\chi(H)=2$,
then define $\mathrm{hcf}(H)=1$ if both $\mathrm{hcf}_{c}(H)=1$ and
$\mathrm{hcf}_{\chi}(H)\leq 2$. Then let

$\chi^{*}(H)=\begin{cases}\chi_{cr}(H)&\text{ if }\mathrm{hcf}(H)=1,\\\
\chi(H)&\text{ otherwise.}\end{cases}$

######  Theorem 1.4 (Kühn and Osthus [43]).

For any $H$ there exist integers $C=C(H)$ and $n_{0}=n_{0}(H)$ such that every
graph $G$ whose order $n\geq n_{0}$ is divisible by $|H|$ and whose minimum
degree is at least $(1-1/\chi^{*}(H))n+C$ contains an $H$-factor.

The degree condition in Theorem 1.4 is best possible up to the constant $C$
and there are also graphs $H$ for which the constant $C$ cannot be omitted
entirely [43].

###  1.2 Motivation

As mentioned above, many typical Dirac-type results in graph theory are of the
form “under certain degree conditions, $G$ has property $\mathcal{P}$”. Once
such a result is established, it is natural to ask how strongly does $G$
possess $\mathcal{P}$? In particular, this has motivated recent trends in the
study of robustness of graph properties (see [52]), aiming to strengthen
classical results in extremal graph theory and probabilistic combinatorics.
What measures of robustness can one utilize? In this direction, several
different measures of robustness have been explored in

  1. 1.

(sparse) random graphs $G(n,p)$ in the setting of so-called resilience (see
e.g. [3, 5, 7, 19, 38, 39, 53]);

  2. 2.

edge-colored graphs (see e.g. [1, 2, 8, 13, 16, 17, 18, 23, 24, 31, 44, 47,
50, 54]);

  3. 3.

Maker-Breaker games (see e.g. [6, 9, 14, 37, 42]).

For further works in this area the reader is referred to a comprehensive
survey from Sudakov [52].

Finding spanning subgraphs in edge-colored graphs with certain constraints has
also been widely and well studied. An edge-coloring $c$ of a graph is
_(globally) $k$-bounded_ if every color appears at most $k$ times in the
coloring, while $c$ is _locally $k$-bounded_ if every color appears at most
$k$ times at any given vertex (so $c$ is a proper edge-coloring when $k=1$). A
fundamental line of research is to find _rainbow subgraphs_ (all edges have
distinct colors) in $g$-bounded edge-colorings of graphs and _properly colored
subgraphs_ (any adjacent edges receive different colors) in locally
$\ell$-bounded edge-colorings of graphs. For perfect matchings, Erdős and
Spencer [23] proved that any $(n-1)/16$-bounded edge-coloring of $K_{n,n}$
admits a rainbow perfect matching. Recently, Coulson and Perarnau [17]
considered the sparse version and obtained that there exist $\mu>0$ and
$n_{0}\in\mathbb{N}$ such that if $n\geq n_{0}$ and $G$ is a Dirac bipartite
graph on $2n$ vertices, then any $\mu n$-bounded edge-coloring of $G$ contains
a rainbow perfect matching. For Hamilton cycles, a conjecture of Bollobás and
Erdős [8] states that every locally
$\left(\lfloor\frac{n}{2}\rfloor-1\right)$-bounded edge-colored $K_{n}$
contains a properly colored Hamilton cycle. There is a series of partial
results toward this conjecture (see e.g. [1, 13, 50]). In [44], Lo proved that
the conjecture of Bollobás and Erdős is true asymptotically. For sparse
version, Coulson and Perarnau [18] derived that there exist $\mu>0$ and
$n_{0}\in\mathbb{N}$ such that if $n\geq n_{0}$ and $G$ is a Dirac graph on
$n$ vertices, then any $\mu n$-bounded edge-coloring of $G$ contains a rainbow
Hamilton cycle. For $H$-factors, Coulson, Keevash, Perarnau and Yepremyan [16]
showed that there is a constant $\mu$ such that any $\mu n$-bounded edge-
coloring of $G$ with $\delta(G)\geq(1-\frac{1}{\chi^{*}(H)}+o(1))n$ contains a
rainbow $H$-factor.

In this paper, we consider a more general setting of incompatibility systems,
which was first proposed by Krivelevich, Lee and Sudakov [41].

######  Definition 1.5 (Incompatibility system).

Let $G=(V,E)$ be a graph.

  * •

An _incompatibility system_ $\mathcal{F}$ over $G$ is a family
$\mathcal{F}=\\{F_{v}\\}_{v\in V}$ such that for every $v\in V$, $F_{v}$ is a
family of 2-subsets of edges incident with $v$, i.e.
$F_{v}\subseteq\\{\\{e,e^{\prime}\\}\in{E\choose 2}:e\cap
e^{\prime}=\\{v\\}\\}$.

  * •

For any two edges $e$ and $e^{\prime}$, if there exists some vertex $v$ such
that $\\{e,e^{\prime}\\}\in F_{v}$, then we say that $e$ and $e^{\prime}$ are
_incompatible_ at $v$. Otherwise, they are _compatible_. A subgraph
$H\subseteq G$ is _compatible_ if all pairs of edges are compatible.

  * •

For a positive integer $\Delta$, an incompatibility system $\mathcal{F}$ is
_$\Delta$ -bounded_ if for any vertex $v$ and any edge $e$ incident with $v$,
there are at most $\Delta$ other edges incident with $v$ that are incompatible
with $e$.

Locally $\ell$-bounded edge-colorings can be viewed as transitive
$(\ell-1)$-bounded incompatibility systems in which two adjacent edges are
incompatible if only they have the same color, and compatible subgraphs
generalize the concept of properly colored subgraphs. Note that there is also
a similar generalization of $g$-bounded edge-colorings, called _systems of
conflicts_ (see [17]). Definition 1.5 was firstly introduced in [41] as a
measure of robustness and motivated by two concepts in graph theory. First, it
generalizes _transition systems_ introduced by Kotzig [36] in 1968. In our
terminology, a transition system is simply a 1-bounded incompatibility system.
Kotzig’s work was motivated by a problem of Nash–Williams on cycle covering of
Eulerian graphs (see, e.g. Section 8.7 in [10]).

In [41], Krivelevich, Lee and Sudakov studied the robustness of Hamiltonicity
of Dirac graphs with respect to the incompatibility system and derived Theorem
1.6.

######  Theorem 1.6 ([41]).

There exists a constant $\mu>0$ such that the following holds for large enough
$n$. For every $n$-vertex Dirac graph $G$ and a $\mu n$-bounded
incompatibility system $\mathcal{F}$ defined over $G$, there exists a
compatible Hamilton cycle.

Their main tool is based on Pósa’s rotation-extension technique. Theorem 1.6
settled in a very strong form, a conjecture of Häggkvist from 1988 (see
Conjecture 8.40 in [10]). They further studied compatible Hamilton cycles in
random graphs in [40] and proved that there is a constant $\mu>0$ such that if
$p\gg\frac{\log n}{n}$, then w.h.p. $G=G(n,p)$ contains a compatible Hamilton
cycle for every $\mu np$-bounded incompatibility system defined over $G$,
which strengthen the result about Hamilton cycles in $G(n,p)$ without
restrictions of incompatibility systems.

The concept of incompatibility system appears to provide a new and interesting
take on robustness of graph properties. Krivelevich, Lee and Sudakov [41] also
suggested looking at how various extremal results can be strengthened in this
context.

###  1.3 Main result and discussion

It is natural to consider other compatible spanning structures. We study the
minimum degree conditions for $H$-factors in incompatibility system. Note that
throughout this paper, we always assume $\chi(H)\geq 2$, since $\chi(H)=1$ is
a trivial case. For convenience, given constants $\mu,\delta$ and
$n\in\mathbb{N}$, an _$(n,\delta,\mu)$ -incompatibility system
_$(G,\mathcal{F})$ consists of an $n$-vertex graph $G$ with
$\delta(G)\geq\delta n$ and a $\mu n$-bounded incompatibility system
$\mathcal{F}$ over $G$. Our main result is formally stated as follows.

######  Theorem 1.7.

Let $h\in\mathbb{N}$ and $H$ be any $h$-vertex graph. For any $\alpha>0$,
there exists a constant $\mu>0$ such that for any sufficiently large $n$ with
$n\in h\mathbb{N}$, every
$(n,1-\frac{1}{\chi^{*}(H)}+\alpha,\mu)$-incompatibility system
$(G,\mathcal{F})$ contains a compatible $H$-factor. In particular, the term of
$\alpha$ in the minimum degree condition cannot be omitted when $H$ is a
complete $r$-partite graph for $r\geq 3$.

We first remark that Theorem 1.7 can be seen as a ‘local resilience’ version
of Theorem 1.4 in incompatibility systems. Towards the ‘in particular’ part in
the statement, an obvious question is for which graphs the error term $\alpha
n$ in the the minimum degree condition can be replaced by a constant term.

####  1.3.1 A space barrier

For $r\geq 3$ and $h_{1},\ldots,h_{r}\geq 1$, we use
$K_{r}(h_{1},h_{2},\ldots,h_{r})$ to denote the complete $r$-partite graph
with each part of size $h_{i}$. In particular, when $h_{i}=s$ for any
$i\in[r]$, we write $K_{r}^{s}$ for $K_{r}(s,s,\ldots,s)$. Now we show that
the minimum degree condition is in some sense tight when
$H=K_{r}(h_{1},h_{2},\ldots,h_{r})$ by constructing for any
$0<\mu<\frac{{\chi_{cr}(H)}+1-r}{r}$ an
$(n,1-\frac{1}{\chi^{*}(H)}+\frac{\mu}{2},\mu)$-incompatibility system
$(G,\mathcal{F})$ which contains no compatible
$K_{r}(h_{1},h_{2},\ldots,h_{r})$-factor. Here we need two results as follows
which provide lower bound constructions for the minimum degree threshold
forcing an $H$-factor.

######  Proposition 1.8.

_[32]_ For every graph $H$ with $2\leq\chi(H)=:r$ and every integer $n$ that
is divisible by $|H|$, there exists a complete $r$-partite graph $G$ of order
$n$ with minimum degree $(1-\frac{1}{\chi_{cr}(H)})n-1$ which does not contain
an $H$-factor.

It is easy to observe that every part in $G$ as above, say $V_{i},i\in[r]$,
satisfies that $\frac{{\chi_{cr}(H)}+1-r}{r}n\leq|V_{i}|\leq\lceil
n/{\chi_{cr}(H)}\rceil+1$.

######  Proposition 1.9.

_[43]_ Let $H$ be a graph with $3\leq\chi(H)=:r$ and let $h\in\mathbb{N}$. Let
$G$ be the complete $r$-partite graph of order $k|H|$ whose vertex classes
$V_{1},\ldots,V_{r}$ satisfy $|V_{1}|=\lfloor k|H|/r\rfloor+1,|V_{2}|=\lceil
k|H|/r\rceil-1$ and $\lfloor k|H|/r\rfloor\leq|V_{i}|\leq\lceil k|H|/r\rceil$
for all $i\geq 3$. So $\delta(G)=\lceil(1-\frac{1}{\chi(H)})|G|\rceil-1$. If
$\mathrm{hcf}(H)\neq 1$, then $G$ does not contain an $H$-factor.

Recall that $H=K_{r}(h_{1},h_{2},\ldots,h_{r})$ for $r\geq 3$ and write
$h=\sum_{i\in[r]}h_{i}$. Let $n=kh$ and $G_{0}$ be an $n$-vertex complete
$r$-partite graph with $\delta(G_{0})\geq(1-\frac{1}{\chi^{*}(H)})n-1$ such
that $G_{0}$ contains no $H$-factors. Indeed such $G_{0}$ can be obtained from
Proposition 1.8 or Proposition 1.9. Write $V_{1},\ldots,V_{r}$ for the $r$
parts of $G_{0}$ and inside every part $V_{i}$ of $G_{0}$, we add a bipartite
spanning subgraph with minimum degree at least $\frac{\mu n}{2}+1$ and maximum
degree at most $\mu n$. Denote the resulting graph by $G$. Hence,
$\delta(G)\geq\left(1-\frac{1}{\chi^{*}(H)}+\frac{\mu}{2}\right)n$ and for
every $i\in[r]$, $G[V_{i}]$ is a triangle-free graph with
$\delta(G[V_{i}])\geq\frac{\mu n}{2}+1$ and $\Delta(G[V_{i}])\leq\mu n$. Now
we define an incompatibility system $\mathcal{F}$ over $G$. For any two
different parts $V_{i},V_{j}$ of $G$, let $v$ be any vertex in $V_{i}$ and
$u,w$ be any two different vertices in $V_{j}$. If $uw$ is an edge in
$G[V_{j}]$, then let $vu$ and $vw$ be incompatible at $v$. Since
$\Delta(G[V_{j}])\leq\mu n$, $\mathcal{F}$ is $\mu n$-bounded.

Now it remains to verify that there is no compatible
$K_{r}(h_{1},h_{2},\ldots,h_{r})$-factor. Before that, for any subgraph
$F\subseteq G$ we define the _index vector_
$\textbf{i}_{F}=(x_{1},\ldots,x_{r})$ by choosing $x_{i}=|V(F)\cap
V_{i}|,i\in[r]$. We claim that for every compatible copy of
$K_{r}(h_{1},h_{2},\ldots,h_{r})$ in $G$, its index vector is an $r$-tuple of
$h_{1},h_{2},\ldots,h_{r}$. In fact, assume that there is a compatible copy of
$K_{r}(h_{1},h_{2},\ldots,h_{r})$ in $G$, denoted by $K$, whose index vector
is not an $r$-tuple of $h_{1},h_{2},\ldots,h_{r}$. Then $K$ has an edge in
$G[V_{i}]$ for some $i\in[r]$, say $uw$. Since $r\geq 3$, $uw$ is contained in
a triangle of $K$, say $vuw$. As $G[V_{i}]$ is triangle-free, one can observe
that $v$ is in some $V_{j}$ for $j\neq i$ and by assumption $vu$ and $vw$ are
compatible at $v$, which contradicts the definition of $\mathcal{F}$. Hence,
since $G_{0}$ contains no $K_{r}(h_{1},h_{2},\ldots,h_{r})$-factor, it follows
from the aforementioned claim that $G$ contains no compatible
$K_{r}(h_{1},h_{2},\ldots,h_{r})$-factor as well.

##  2 Notation and preliminaries

For a graph $G$, we use $e(G)$ to denote the number of edges of $G$. For a
graph $G=(V,E)$ and $k$ pairwise disjoint vertex subsets
$U_{1},\ldots,U_{k}\subseteq V$, we use $G[U_{1},\ldots,U_{k}]$ to denote the
$r$-partite subgraph induced by $U_{1},\ldots,U_{r}$. In the proofs, if we
choose $a\ll b$, then this means that for any $b>0$, there exists $a_{0}>0$
such that for any $a<a_{0}$ the subsequent statement holds. Hierarchies of
other lengths are defined similarly.

###  2.1 Proof strategy and main tools

Our proof uses the absorption method, pioneered by the work of Rödl, Ruciński
and Szemerédi [49] on perfect matchings in hypergraphs. In recent years, the
method has become an extremely important tool for studying the existence of
spanning structures in graphs, digraphs and hypergraphs. Before its appearance
a well-known systematic way in this area is the blow-up lemma due to Komlós,
Sárközy and Szemerédi [34], which has successfully been adopted by many
scholars for various classical results [4, 43]. It is worth noting that Glock
and Joos [24] developed a rainbow version of the blow-up lemma, which enables
the systematic study of rainbow embeddings of bounded degree spanning
subgraphs [22, 31]. However, there has been no such variant for
incompatibility systems. Instead, we utilize the absorption framework and
develop a different counting argument for embedding compatible graphs under
certain pseudorandomness conditions (see Lemma 3.7).

The general idea of absorption is to split the problem of finding perfect
tilings into two subproblems. The first major task is to define and find an
absorbing set in the host graph which can ‘absorb’ left-over vertices. We will
start with the notion of absorbers needed in our proof.

######  Definition 2.1 (Absorber).

Let $H$ be an $h$-vertex graph and $G$ be an $n$-vertex graph. For any $h$-set
$S\subseteq V(G)$ and integer $t$, we say that a set $A_{S}\subseteq
V(G)\setminus S$ is an _$(H,t)$ -absorber_ for $S$ if $|A_{S}|\leq h^{2}t$ and
both $G[A_{S}]$ and $G[A_{S}\cup S]$ contain compatible $H$-factors.

The first task is handled as follows.

######  Definition 2.2 (Absorbing set).

Let $H$ be an $h$-vertex graph, $G$ be an $n$-vertex graph and $\xi$ be a
constant. A set $A\subseteq V(G)$ is called a $\xi$-_absorbing set_ (for
$V(G)$) if for any set $R\subseteq V(G)\setminus A$ with $|R|\leq\xi n$ and
$|A\cup R|\in h\mathbb{N}$, the graph $G[A\cup R]$ contains a compatible
$H$-factor.

######  Lemma 2.3 (Absorbing lemma).

Let $H$ be an $h$-vertex graph with $\chi(H)\geq 2$. For any
$\alpha,\sigma>0$, there exist $\mu,\xi>0$ such that for any sufficiently
large $n$, if $(G,\mathcal{F})$ is an
$\left(n,1-\frac{1}{\chi^{*}(H)}+\alpha,\mu\right)$-incompatibility system,
then $G$ contains a $\xi$-absorbing set $A$ of size at most $\sigma n$.

The second major task in absorption arguments for perfect tilings is to find a
tiling that covers most of the vertices, leaving just a small portion of
vertices uncovered. We will sometimes call such a tiling an _almost perfect
tiling_ or an _almost cover_.

######  Lemma 2.4 (Almost cover).

Let $H$ be an $h$-vertex graph with $\chi(H)\geq 2$. For any $\alpha,\tau>0$,
there exists $\mu>0$ such that for any sufficiently large $n$, if
$(G,\mathcal{F})$ is an
$\left(n,1-\frac{1}{\chi_{cr}(H)}+\alpha,\mu\right)$-incompatibility system,
then there exists a compatible $H$-tiling covering all but at most $\tau n$
vertices of $G$.

Now we are ready to prove Theorem 1.7 to end this section.

###### Proof of Theorem 1.7.

Given $\alpha>0$, we choose

$\frac{1}{n}\ll\mu\ll\tau\ll\xi\ll\sigma\ll\alpha.$

Applying Lemma 2.3 with $\sigma\leq\frac{\alpha}{2}$, $G$ contains a
$\xi$-absorbing set $A$ of size at most $\sigma n$. Since
$\delta(G-A)\geq\left(1-\frac{1}{\chi^{*}(H)}+\frac{\alpha}{2}\right)n$, we
can apply Lemma 2.4 on $G-A$ to obtain a compatible $H$-tiling
$\mathcal{H}_{1}$ covering all but at most $\tau n$ vertices in $G-A$. Denote
by $R$ the set of uncovered vertices in $G-A$. Since $\tau\ll\xi$, $G[A\cup
R]$ contains a compatible $H$-factor $\mathcal{H}_{2}$. Thus,
$\mathcal{H}_{1}\cup\mathcal{H}_{2}$ is a compatible $H$-factor of $G$. ∎

The rest of the paper is organised as follows. In Section 2, we set up some
basic notation and outline the proof of Theorem 1.7. Then we state two crucial
results (Lemmas 2.3 and 2.4) that decode the proof of Theorem 1.7. Sections 3
and 4 are devoted to proving Lemmas 2.3 and 2.4, respectively.

##  3 Almost compatible $H$-factor

The main tools in the proof of Lemma 2.4 are Szemerédi’s Regularity Lemma and
an embedding lemma (see Lemma 3.7). We first give some definitions and lemmas.

###  3.1 Regularity

######  Definition 3.1 (Regular pair).

Given a graph $G$ and disjoint vertex subsets $X,Y\subseteq V(G)$, the
_density_ of the pair $(X,Y)$ is defined as

$d(X,Y):=\frac{e(X,Y)}{|X||Y|},$

where $e(X,Y):=e(G[X,Y])$. For $\varepsilon>0$, the pair $(X,Y)$ is
$\varepsilon$-_regular_ if for any $A\subseteq X,B\subseteq Y$ with
$|A|\geq\varepsilon|X|,|B|\geq\varepsilon|Y|$, we have

$|d(A,B)-d(X,Y)|<\varepsilon.$

Additionally, if $d(X,Y)\geq d$ for some $d>0$, then we say that $(X,Y)$ is
$(\varepsilon,d)$-_regular_.

######  Definition 3.2 (Regular partition).

For a graph $G=(V,E)$ and $\varepsilon,d>0$, a partition $V=V_{0}\cup
V_{1}\cup\ldots\cup V_{k}$ is $(\varepsilon,d)$_-regular_ , if

  * •

$|V_{0}|\leq\varepsilon|V|$;

  * •

$|V_{1}|=|V_{2}|=\ldots=|V_{k}|\leq\lceil\varepsilon|V|\rceil$;

  * •

all but at most $\varepsilon k^{2}$ pairs $(V_{i},V_{j})$ with $1\leq i<j\leq
k$ are $(\varepsilon,d)$-regular.

Moreover, we usually call $V_{0},V_{1},\ldots,V_{k}$ _clusters_ and call the
cluster $V_{0}$ _exceptional set_.

######  Fact 3.3.

Let $(X,Y)$ be an $(\varepsilon,d)$-regular pair, and $B\subseteq Y$ with
$|B|\geq\varepsilon|Y|$. Then all but $\varepsilon|X|$ vertices in $X$ have
degree at least $(d-\varepsilon)|B|$ in $B$.

######  Fact 3.4 (Slicing lemma, [35]).

Let $(X,Y)$ be an $(\varepsilon,d)$-regular pair, and for some
$\eta>\varepsilon$, let $X^{\prime}\subseteq X,Y^{\prime}\subseteq Y$ with
$|X^{\prime}|\geq\eta|X|,|Y^{\prime}|\geq\eta|Y|$. Then
$(X^{\prime},Y^{\prime})$ is an $\varepsilon^{\prime}$-regular pair with
$\varepsilon^{\prime}=\max\\{\varepsilon/\eta,2\varepsilon\\}$, and for its
density $d^{\prime}$ we have $|d^{\prime}-d|<\varepsilon$.

######  Lemma 3.5 (Degree form of the Regularity Lemma, [35]).

For every $\varepsilon>0$, there is an $M=M(\varepsilon)$ such that if
$G=(V,E)$ is any graph and $d\in(0,1]$ is any real number, then there is an
$(\varepsilon,d)$-regular partition $V=V_{0}\cup V_{1}\cup\ldots\cup V_{k}$
with $|V_{i}|=m$ for each $i\in[k]$, and a spanning subgraph
$G^{\prime}\subseteq G$ with the following properties:

  * •

$1/\varepsilon\leq k\leq M$,

  * •

$d_{G^{\prime}}(v)>d_{G}(v)-(d+\varepsilon)|V|$ for all $v\in V$,

  * •

$e(G^{\prime}[V_{i}])=0$ for all $i\geq 1$,

  * •

all pairs $(V_{i},V_{j})$ $(1\leq i<j\leq k)$ are $\varepsilon$-regular in
$G^{\prime}$ with density $0$ or at least $d$.

######  Definition 3.6 (Reduced graph).

Given an arbitrary graph $G=(V,E)$, a partition $V=V_{1}\cup\ldots\cup V_{k}$,
and two parameters $\varepsilon,d>0$, the _reduced graph_ $R=R(\varepsilon,d)$
of $G$ is defined as follows:

  * •

$V(R)=[k]$,

  * •

$ij\in E(R)$ if and only if $(V_{i},V_{j})$ is $(\varepsilon,d)$-regular.

As remarked in [35], a typical application of degree form of the Regularity
Lemma begins with a graph $G=(V,E)$ and appropriate parameters
$\varepsilon,d>0$, and then obtains an $(\varepsilon,d)$-regular partition
$V=V_{0}\cup V_{1}\cup\ldots\cup V_{k}$ and a subgraph $G^{\prime}$ with
above-mentioned properties. Then we usually drop the exceptional set $V_{0}$
to get a pure graph $G^{\prime}-V_{0}$ and study the properties of reduced
graph $R=R(\varepsilon,d)$. By Lemma 3.5,

$\displaystyle\delta(R)\geq\frac{\delta(G)-(d+\varepsilon)|V|-|V_{0}|}{m}\geq\frac{\delta(G)-(d+2\varepsilon)|V|}{m}.$

In particular, if $\delta(G)\geq c|V|$, then
$\delta(R)\geq(c-d-2\varepsilon)k$.

###  3.2 Proof of Lemma 2.4

To find an almost cover, we adopt the approach of Komlós in [32], making use
of Szemerédi’s Regularity Lemma and a result of Shokoufadeh and Zhao [51] (see
Theorem 1.3). In [32], due to the graph counting lemma (e.g, see [35]), the
arguments often reduce to greedily picking vertex-disjoint copies of $H$
within a bunch of clusters under certain pseudorandom properties. To adopt
this approach in the context of incompatibility systems which boils down to
embedding compatible copies of $H$, we develop a ‘compatible’ variant of the
graph counting lemma as follows.

######  Lemma 3.7.

For constant $\eta,d>0$ and positive integers $r,h_{1},\ldots,h_{r}$ with
$\sum_{i=1}^{r}h_{i}=:h$, there exist positive constants
$\varepsilon^{\ast}=\varepsilon^{\ast}(r,d,h),c=c(r,d,h)$ and
$\mu=\mu(r,d,h,\eta)$ such that the following holds for sufficiently large
$n$. Let $(G,\mathcal{F})$ be a $\mu n$-bounded incompatibility system with
$|G|=n$ and $U_{1},\ldots,U_{r}$ be pairwise vertex-disjoint sets in $V(G)$
with $|U_{i}|\geq\eta n$, $i\in[r]$ and every pair $(U_{i},U_{j})$ being
$(\varepsilon^{\ast},d)$-regular. Then there exist at least
$c\prod_{i=1}^{r}|U_{i}|^{h_{i}}$ compatible copies of
$K_{r}(h_{1},\ldots,h_{r})$ in $G[U_{1},\ldots,U_{r}]$, each containing
exactly $h_{i}$ vertices in $U_{i}$ for every $i\in[r]$.

We also give a notion of bottle-graphs by Komlós in [32].

######  Definition 3.8.

Given integers $h,r$ and an $h$-vertex graph $H$ with $\chi(H)=r$, we define a
_bottle-graph_ $B$ of $H$ as a complete $r$-partite graph with part sizes
$(r-1)\sigma(H),h-\sigma(H),\ldots,h-\sigma(H)$.

It is easy to see that $\chi_{cr}(B)=\chi_{cr}(H)$ and $B$ contains an
$H$-factor consisting of $r-1$ copies of $H$. Based on this, our proof
strategy is to find an almost cover with compatible copies of $B$.

###### Proof of Lemma 2.4.

Given $\alpha,\tau>0$ and an $h$-vertex graph $H$, we let $\chi(H)=:r$ and
choose

$\frac{1}{n}\ll\mu\ll\varepsilon\ll\rho\ll\alpha,\tau,\frac{1}{r},\frac{1}{h}.$

We first apply Lemma 3.5 on $G$ with $d=\rho$ to obtain a spanning subgraph
$G^{\prime}$ and an $(\varepsilon,\rho)$-regular partition $V(G)=V_{0}\cup
V_{1}\cup\ldots\cup V_{k}$ for some $1/\varepsilon\leq k\leq M$ with
$|V_{i}|=m\geq\frac{(1-\varepsilon)n}{k}$ for every $i\in[k]$. Let
$R=R(\varepsilon,\rho)$ be the reduced graph for this partition. Since
$\varepsilon\ll\rho\ll\alpha$, we have
$\delta(R)\geq\left(1-\frac{1}{\chi_{cr}(H)}+\alpha-\rho-2\varepsilon\right)k\geq\left(1-\frac{1}{\chi_{cr}(H)}+\frac{\alpha}{2}\right)k$.
Since $\chi_{cr}(B)=\chi_{cr}(H)$, by Theorem 1.3, $R$ has a $B$-tiling
$\mathcal{B}$ that covers all but at most $5|B|^{2}$ vertices in $R$.

Recall that $B$ has part sizes
$(r-1)\sigma(H),h-\sigma(H),\ldots,h-\sigma(H)$. Here we write
$\ell:=h-\sigma(H),y:=(r-1)\sigma(H)$ and $r^{\prime}=|B|=(r-1)h$ for
simplicity, and thus $r^{\prime}=y+(r-1)\ell$. Given a copy of $B$ in
$\mathcal{B}$, without loss of generality, we may assume that its vertex set
is $\\{V_{1},\ldots,V_{r^{\prime}}\\}$ with the $r$-partition of $V(B)$
denoted as

$\mathcal{W}_{1}=\\{V_{1},\ldots,V_{y}\\}\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\
\mathcal{W}_{s+1}=\\{V_{y+1+(s-1)\ell},\ldots,V_{y+s\ell}\\}\leavevmode\nobreak\
\text{for}\leavevmode\nobreak\ s\in[r-1].$

Note that every pair of clusters $V_{i},V_{j}$ from distinct parts forms an
$(\varepsilon,\rho)$-regular pair.

We shall greedily embed in $G^{\prime}$ vertex-disjoint compatible copies of
$B$ that cover almost all the vertices in $\cup_{i=1}^{r^{\prime}}V_{i}$. Now
for every $i\in[y]$ we divide $V_{i}$ arbitrarily into $\ell$ subclusters
$V_{i,1},\ldots,V_{i,\ell}$ of (almost) equal size. For every
$j\in[y+1,r^{\prime}]$ we divide $V_{j}$ into $y$ subclusters
$V_{j,1},\ldots,V_{j,y}$ of (almost) equal size. Here for simplicity we may
further assume that $|V_{i,i^{\prime}}|=\frac{m}{\ell}$ for
$i\in[y],i^{\prime}\in[\ell]$ and $|V_{j,j^{\prime}}|=\frac{m}{y}$ for every
$j\in[y+1,r^{\prime}],j^{\prime}\in[y]$. We call a family
$\\{V_{i_{s},j_{s}}\\}_{s=1}^{r}$ of $r$ subclusters _legal_ if
$V_{i_{s}}\in\mathcal{W}_{s}$ for every $s\in[r]$, i.e.,
$\\{V_{i_{s}}\\}_{s=1}^{r}$ forms a copy of $K_{r}$ in $R$. Note that every
$\mathcal{W}_{s}$ ($s\in[r]$) contains exactly $y\ell$ subclusters in total.
Therefore we can greedily partition the set of all subclusters into $y\ell$
pairwise disjoint legal families.

Now if for every legal family $\\{V_{i_{s},j_{s}}\\}_{s=1}^{r}$ we have a
$B$-tiling in $G^{\prime}[\bigcup_{s=1}^{r}V_{i_{s},j_{s}}]$ that covers all
but at most $\frac{\tau}{4y\ell}r^{\prime}m$ vertices of
$\bigcup_{s=1}^{r}V_{i_{s},j_{s}}$, then putting them together would give a
$B$-tiling covering all but at most $\frac{\tau}{4}r^{\prime}m$ vertices of
$V_{1}\cup V_{2}\cup\cdots\cup V_{r^{\prime}}$. Applying this to every copy of
$B$ from $\mathcal{B}$ would give us a $B$-tiling covering all but at most

$|V_{0}|+5|B|^{2}m+|\mathcal{B}|\frac{\tau}{4}r^{\prime}m<\varepsilon
n+5r^{\prime 2}\varepsilon n+\frac{\tau}{4}n<\tau n$

vertices in $G$. So to complete the proof of Lemma 2.4, it is sufficient to
prove the following claim.

######  Claim 3.9.

Given any legal family $\\{V_{i_{s},j_{s}}\\}_{s=1}^{r}$,
$G[V_{i_{1},j_{1}},\ldots,V_{i_{r},j_{r}}]$ admits a $B$-tiling covering all
but at most $\frac{\tau}{4y\ell}r^{\prime}m$ vertices of
$\bigcup_{s=1}^{r}V_{i_{s},j_{s}}$.

For convenience, we write $Y_{s}:=V_{i_{s},j_{s}}$ with $s\in[r]$. Recall that
$|Y_{1}|=\frac{m}{\ell}$ and $|Y_{s}|=\frac{m}{y}$ for $s\in[2,r]$. Now it
suffices to show that for any $Y_{s}^{\prime}\subseteq Y_{s}$ with $s\in[r]$,
each of size at least $\frac{\tau}{4y\ell}m$, there exists a compatible copy
of $B$ with exactly $y$ vertices inside $Y_{1}^{\prime}$ and $\ell$ vertices
inside every $Y_{s}^{\prime}$, $s\in[2,r]$.

For any distinct $s,t\in[r]$, the pair $(V_{i_{s}},V_{i_{t}})$ is
$\varepsilon$-regular with density at least $\rho$. Then Fact 3.4 implies that
every two sets from $Y_{1}^{\prime},\ldots,Y_{r}^{\prime}$ forms an
$\varepsilon^{\prime}$-regular pair with density at least $\rho-\varepsilon$,
where $\varepsilon^{\prime}=\frac{4y\ell}{\tau}\varepsilon$. Therefore by the
fact that
$\frac{1}{n}\ll\mu\ll\varepsilon\ll\rho,\tau,\frac{1}{r},\frac{1}{h}$, Lemma
3.7 applied on $G$ with
$U_{i}=Y_{i}^{\prime},d=\rho/2,\varepsilon^{*}=\varepsilon^{\prime},\eta=\frac{\tau}{4y\ell}\frac{1-\varepsilon}{k},h_{1}=y,h_{i}=\ell$
for $i\in[2,r]$, gives a desired compatible copy of $B$. This completes the
proof of Claim 3.9. ∎

###  3.3 Proof of Lemma 3.7: counting compatible subgraphs

In the rest of this section, we will focus on the proof of Lemma 3.7. Before
that, we give a definition.

######  Definition 3.10 (Good pair).

Given an incompatibility system $(G,\mathcal{F})$, a vertex $v\in V(G)$ and a
subgraph $H\subseteq G$, we say that $(v,H)$ is a _good pair_ if

  * •

$H$ is compatible;

  * •

$v$ is adjacent to all vertices of $H$;

  * •

all edges from $v$ to $V(H)$ are mutually compatible at $v$.

Moreover, the vertex $v$ is called the _center_ of good pair $(v,H)$.

We also state an obvious fact as follows, which is widely used throughout the
proofs.

######  Fact 3.11.

Let $(G,\mathcal{F})$ be a $\mu n$-bounded incompatibility system with
$|G|=n$. Then for every $v\in V(G)$, there are at most $\mu n^{2}$ pairs
$\\{v_{1},v_{2}\\}$ of vertices from $N(v)$ that satisfy one of the following
property:

  1. (1)

$vv_{1}$ and $vv_{2}$ are incompatible at $v$;

  2. (2)

$vv_{1}$ and $v_{1}v_{2}$ are incompatible at $v_{1}$.

###### Proof of Lemma 3.7.

We prove this lemma by induction on $r$. Given $\eta,d>0$, we choose

$\frac{1}{n}\ll\varepsilon_{r}\ll\varepsilon_{r-1}\ll\cdots\ll\varepsilon_{1}\ll
d,\frac{1}{r},\frac{1}{h}\leavevmode\nobreak\ \text{and
additionally}\leavevmode\nobreak\
\frac{1}{n}\ll\mu\ll\eta,d,\frac{1}{r},\frac{1}{h}.$

The base case $r=1$ is trivial since we can find $|U_{1}|\choose h_{1}$
$h_{1}$-subsets in $U_{1}$.

Suppose that Lemma 3.7 is true for $r-1$. Now we consider the case $r$, that
is, $U_{1},\ldots,U_{r}$ are pairwise $(\varepsilon_{r},d)$-regular and
$|U_{i}|\geq\eta n$ for any $i\in[r]$. We want to find
$c\prod_{i=1}^{r}|U_{i}|^{h_{i}}$ compatible copies of
$K_{r}(h_{1},\ldots,h_{r})$ in $G[U_{1},\ldots,U_{r}]$ for some
$c=c(r,d,h)>0$.

We choose a subset $U_{r}^{\prime}\subseteq U_{r}$ such that any vertex in
$U_{r}^{\prime}$ has degree at least $(d-\varepsilon_{r})|U_{i}|$ in $U_{i}$
for every $i\in[r-1]$. By Fact 3.3, there are at least
$(1-\varepsilon_{r})|U_{r}|$ vertices of $U_{r}$ with degree at least
$(d-\varepsilon_{r})|U_{i}|$ in $U_{i}$ for any fixed $i\in[r-1]$. Hence,
$|U_{r}^{\prime}|\geq(1-(r-1)\varepsilon_{r})|U_{r}|$.

Let $v$ be an arbitrary vertex in $U_{r}^{\prime}$. Denote by $U_{i}^{\prime}$
the neighborhood of $v$ in $U_{i}$ for every $i\in[r-1]$. Then
$|U_{i}^{\prime}|\geq(d-\varepsilon_{r})|U_{i}|$. By Fact 3.4, for any $1\leq
i<j\leq r-1$, $U_{i}^{\prime}$ and $U_{j}^{\prime}$ is an
$(\varepsilon^{\prime},d^{\prime})$-regular pair with
$\varepsilon^{\prime}=\max\\{\varepsilon_{r}/(d-\varepsilon_{r}),2\varepsilon_{r}\\}$
and $|d^{\prime}-d|<\varepsilon_{r}$, which is also an
$(\varepsilon_{r-1},\frac{d}{2})$-regular pair by the fact that
$\varepsilon_{r}\ll\varepsilon_{r-1}$ and
$d^{\prime}>d-\varepsilon_{r}\geq\frac{d}{2}$. By the induction hypothesis on
$r-1$ with $h^{\prime}=\sum_{i=1}^{r-1}h_{i}$, there is a family
$\mathcal{K}_{v}$ of at least
$c(r-1,\frac{d}{2},h^{\prime})\prod_{i=1}^{r-1}|U_{i}^{\prime}|^{h_{i}}$
compatible copies of $K_{r-1}(h_{1},\ldots,h_{r-1})$ in
$G[U_{1}^{\prime},\ldots,U_{r-1}^{\prime}]$. Inside $\mathcal{K}_{v}$, we know
from Fact 3.11 that there are at most $\mu n^{\sum_{i=1}^{r-1}h_{i}}$
compatible copies of $K_{r-1}(h_{1},\ldots,h_{r-1})$, each containing two
vertices $v_{1},v_{2}$ such that $vv_{1}$ and $vv_{2}$ are incompatible at
$v$. Thus it follows by definition and the fact that
$\frac{1}{n}\ll\mu\ll\eta,d,\frac{1}{r},\frac{1}{h}$, there exists a subfamily
$\mathcal{K}^{\prime}_{v}$ of at least

$c(r-1,\frac{d}{2},h^{\prime})\prod_{i=1}^{r-1}|U_{i}^{\prime}|^{h_{i}}-\mu
n^{\sum_{i=1}^{r-1}h_{i}}\geq\frac{1}{2}c(r-1,\frac{d}{2},h^{\prime})\prod_{i=1}^{r-1}|U_{i}^{\prime}|^{h_{i}}$

copies of $K_{r-1}(h_{1},\ldots,h_{r-1})$ that can form good pairs with $v$.
Let $\mathcal{K}^{\prime}:=\bigcup_{v\in
U_{r}^{\prime}}\mathcal{K}^{\prime}_{v}$. Since
$|U_{r}^{\prime}|\geq(1-(r-1)\varepsilon_{r})|U_{r}|$, there are at least

$\displaystyle|U_{r}^{\prime}|\min\\{|\mathcal{K}^{\prime}_{v}|:v\in
U_{r}^{\prime}\\}|\geq(1-(r-1)\varepsilon_{r})|U_{r}|\cdot\frac{1}{2}c(r-1,\frac{d}{2},h^{\prime})\prod_{i=1}^{r-1}|U_{i}^{\prime}|^{h_{i}}$
$\displaystyle\geq$
$\displaystyle\frac{1}{4}c(r-1,\frac{d}{2},h^{\prime})|U_{r}|\prod_{i=1}^{r-1}|U_{i}^{\prime}|^{h_{i}}=c_{1}|U_{r}|\prod_{i=1}^{r-1}|U_{i}|^{h_{i}}$
(1)

good pairs $(v,K)$ with centers $v\in U_{r}^{\prime}$ and
$K\in\mathcal{K}^{\prime}$, where
$c_{1}=\frac{1}{4}c(r-1,\frac{d}{2},h^{\prime})\cdot(d-\varepsilon_{r})^{\sum_{i=1}^{r-1}h_{i}}$.

Now we shall greedily embed compatible copies of $K_{r}(h_{1},\ldots,h_{r})$
by extending every element inside $\mathcal{K}^{\prime}$. Here we define

$\mathcal{X}_{1}:=\\{K\in\mathcal{K}^{\prime}\mid K\leavevmode\nobreak\
\text{is contained in at least}\leavevmode\nobreak\
c_{1}|U_{r}|/2\leavevmode\nobreak\ \text{good pairs with centers
in}\leavevmode\nobreak\ U_{r}^{\prime}\\}.$

######  Claim 3.12.

The following statements hold.

  1. (1)

$|\mathcal{X}_{1}|\geq\frac{c_{1}}{2}\prod_{i=1}^{r-1}|U_{i}|^{h_{i}}$;

  2. (2)

every compatible copy $K\in\mathcal{X}_{1}$ is contained in at least
$c_{2}|U_{r}|^{h_{r}}$ compatible copies of $K_{r}(h_{1},\ldots,h_{r})$ in
$G[U_{1},\ldots,U_{r}]$, where $c_{2}$ will be determined later.

###### Proof.

We first show (2). For every $K\in\mathcal{X}_{1}$, we denote by $C(K)$ the
set of vertices $v\in U_{r}$ which together with $K$ forms a good pair. Then
$|C(K)|\geq c_{1}|U_{r}|/2$. To extend a fixed $K\in\mathcal{X}_{1}$ into a
compatible copy of $K_{r}(h_{1},\ldots,h_{r})$, we can iteratively choose
$h_{r}$ proper vertices $v_{1},\ldots,v_{h_{r}}$ from $C(K)$ in the following
way:

  * •

choose $v_{1}\in C(K)$ such that $V(K)\cup\\{v_{1}\\}$ induces a compatible
copy of $K_{r}(h_{1},\ldots,h_{r-1},1)$;

  * •

for $2\leq i\leq h_{r}$, given $v_{1},\ldots,v_{i-1}$ as above, choose
$v_{i}\in C(K)$ such that $V(K)\cup\\{v_{1},\ldots,v_{i}\\}$ induces a
compatible copy of $K_{r}(h_{1},\ldots,h_{r-1},i)$.

Note that there are at least $c_{1}|U_{r}|/2-2\mu n\cdot
e(K_{r-1}(h_{1},\ldots,h_{r-1}))\geq c_{1}|U_{r}|/4$ choices for $v_{1}$,
where the term $2\mu n\cdot e(K_{r-1}(h_{1},\ldots,h_{r-1}))$ bounds the
number of vertices $u\in C(K)$ for which there exists an incompatible pair
$(uv,vw)$ of edges with $v,w\in V(K)$. Similarly, there are at least

$c_{1}|U_{r}|/2-(i-1)-2\mu n\cdot e(K_{r-1}(h_{1},\ldots,h_{r-1}))-\mu
n\cdot(i-1)\sum_{i=1}^{r-1}h_{i}\geq c_{1}|U_{r}|/4$

choices for $v_{i}$. Hence, there are at least
$(c_{1}|U_{r}|/4)^{h_{r}}/h_{r}!=c_{2}|U_{r}|^{h_{r}}$ compatible copies of
$K_{r}(h_{1},\ldots,h_{r})$ in $G[U_{1},\ldots,U_{r}]$ containing $K$, where
$c_{2}=(c_{1}/4)^{h_{r}}/h_{r}!$.

The proof of (1) is easy and we write
$\mathcal{X}_{2}=\mathcal{K}^{\prime}-\mathcal{X}_{1}$. By inequality (3.3),
the number $N$ of good pairs $(v,K)$ with centers $v\in U_{r}^{\prime}$ and
$K\in\mathcal{K}^{\prime}$ satisfy

$c_{1}|U_{r}|\prod_{i=1}^{r-1}|U_{i}|^{h_{i}}\leq N\leq|\mathcal{X}_{2}|\cdot
c_{1}|U_{r}|/2+|\mathcal{X}_{1}|\cdot|U_{r}|,$

which implies that
$|\mathcal{X}_{1}|\geq\frac{c_{1}}{2}\prod_{i=1}^{r-1}|U_{i}|^{h_{i}}.$ ∎

Thus, the proof easily follows from Claim 3.12 by letting
$c(r,d,h)=c_{1}c_{2}/2$ and $\varepsilon^{\ast}=\varepsilon_{r}$ as there are
at least

$|\mathcal{X}_{1}|\cdot
c_{2}|U_{r}|^{h_{r}}\geq\frac{c_{1}c_{2}}{2}\prod_{i=1}^{r}|U_{i}|^{h_{i}}=c(r,d,h)\prod_{i=1}^{r}|U_{i}|^{h_{i}}$

compatible copies of $K_{r}(h_{1},\ldots,h_{r})$ in $G[U_{1},\ldots,U_{r}]$,
each containing exactly $h_{i}$ vertices in $U_{i}$ for every $i\in[r]$.

∎

##  4 Building an absorbing set

The construction of an absorbing set has now been known via a novel idea of
Montgomery [46] in a series of works [11], provided that (almost) every set of
$h$ vertices has linearly many vertex-disjoint absorbers. In this paper we
make use of a ‘compatible’ variant as follows, whose proof follows from that
of Lemma 2.2 in [48] and will be included in Appendix A.

######  Lemma 4.1.

Let $t\in\mathbb{N}$, $H$ be an $h$-vertex graph and $\gamma>0$. Then there
exists $\xi=\xi(t,h,\gamma)>0$ such that the following holds. If
$(G,\mathcal{F})$ is an incompatibility system with $|V(G)|=n$ such that for
every $S\in{V(G)\choose h}$ there is a family of at least $\gamma n$ vertex-
disjoint $(H,t)$-absorbers, then $G$ contains a $\xi$-absorbing set of size at
most $\gamma n$.

###  4.1 Finding absorbers

As aforementioned, the first main task is to find for every $h$-set of
vertices linearly many vertex-disjoint absorbers. To achieve this, we first
state a crucial notion of $H$-reachability as follows, which is slightly
different from the original version by Lo and Markström [45].

######  Definition 4.2 (Reachability & Closedness).

Let $m,t\in\mathbb{N}$, $H$ be an $h$-vertex graph and $G$ be an $n$-vertex
graph. We say that two vertices $u,v\in V(G)$ are _$(H,m,t)$ -reachable_ if
for any set $W$ of $m$ vertices, there is a set $S\subseteq V(G)\setminus W$
of size at most $ht-1$ such that both $G[S\cup\\{u\\}]$ and $G[S\cup\\{v\\}]$
have compatible $H$-factors, where we call such $S$ an _$H$ -connector_ for
$u,v$. We say $V(G)$ is _$(H,m,t)$ -closed_ if every two vertices $u,v$ in
$V(G)$ are $(H,m,t)$-reachable.

The following result guarantees that every $h$-vertex set has a family of
linearly many vertex-disjoint absorbers as long as $V(G)$ is $(H,\beta
n,t)$-closed for some $\beta>0$ and $t\in\mathbb{N}$. Its proof follows from
that of Lemma 3.9 in [27] and will be included in Appendix A for completeness.

######  Lemma 4.3 (Lemma 3.9 in [27]).

Given $h,t\in\mathbb{N}$ with $h\geq 3$ and $\beta>0$, the following holds for
any $h$-vertex graph $H$ and sufficiently large $n\in\mathbb{N}$. If
$(G,\mathcal{F})$ is an incompatibility system with $|V(G)|=n$ such that
$V(G)$ is $(H,\beta n,t)$-closed, then every $S\in{V(G)\choose h}$ has at
least $\frac{\beta}{h^{3}t}n$ vertex-disjoint $(H,t)$-absorbers.

Note that the original versions of Lemmas 4.1 and 4.3 deal with absorbing sets
and absorbers without the context of incompatibility systems. By going through
their proofs, the two lemmas are also valid for compatible version. Based on
Lemmas 4.1 and 4.3, it suffices to show that $V(G)$ is closed.

######  Lemma 4.4.

Let $H$ be an $h$-vertex graph and $\chi(H)\geq 2$. For any $\alpha>0$, there
exist $\mu,\beta>0$ and $t\in\mathbb{N}$ such that for any sufficiently large
$n$, if $(G,\mathcal{F})$ is an
$\left(n,1-\frac{1}{\chi^{*}(H)}+\alpha,\mu\right)$-incompatibility system,
then $V(G)$ is $(H,\beta n,t)$-closed.

###### Proof of Lemma 2.3.

Given $\alpha,\sigma>0$ and an $h$-vertex graph $H$, we choose

$\frac{1}{n}\ll\mu,\xi\ll\beta,\frac{1}{t}\ll\alpha,\sigma,\frac{1}{h},$

and let $(G,\mathcal{F})$ be an
$\left(n,1-\frac{1}{\chi^{*}(H)}+\alpha,\mu\right)$-incompatibility system. By
Lemma 4.4, $V(G)$ is $(H,\beta n,t)$-closed. By applying Lemma 4.3 on $G$,
every $S\in{V(G)\choose h}$ has at least $\frac{\beta}{h^{3}t}n$ vertex-
disjoint $(H,t)$-absorbers. Thus Lemma 4.1 applied on $G$ with
$\gamma=\min\\{\frac{\beta}{h^{3}t},\sigma\\}$ immediately gives a
$\xi$-absorbing set $A$ of size at most $\gamma n$.

∎

###  4.2 Lattice-based absorbing method

The proof of Lemma 4.4 makes use of the lattice-based absorbing method
developed by Han [26], Keevash, Knox and Mycroft [30]. To illustrate this, we
first need some notion introduced in [30]. For any vector
$\mathbf{x}=\\{x_{1},\ldots,x_{k}\\}\in\mathbb{Z}^{k}$, let
$|\mathbf{x}|:=\sum_{i=1}^{k}x_{i}$. We say that $\mathbf{x}\in\mathbb{Z}^{k}$
is an _$r$ -vector_ if it has non-negative coordinates and $|\mathbf{x}|=r$.

######  Definition 4.5.

Let $(G,\mathcal{F})$ be an incompatibility system with $|G|=n$ and
$\mathcal{P}=\\{V_{1},\ldots,V_{k}\\}$ be a vertex partition of $V(G)$ for
some integer $k\geq 1$.

  1. 1.

The _index vector_ $\mathbf{i}_{\mathcal{P}}(S)\in\mathbb{Z}^{k}$ of a subset
$S\subseteq V(G)$ with respect to $\mathcal{P}$ is the vector whose $i$th
coordinate is the size of the intersections of $S$ with $V_{i}$, i.e. $|S\cap
V_{i}|$, for every $i\in[k]$.

  2. 2.

Given an $h$-vertex graph $H$ and a constant $\beta>0$, an $h$-vector
$\mathbf{i}\in\mathbb{Z}^{k}$ is called $(H,\beta)$-_robust_ if for any set
$W\subseteq V(G)$ of size $\beta n$, $G-W$ contains a compatible copy of $H$
whose vertex set has the index vector $\mathbf{i}$ with respect to
$\mathcal{P}$.

  3. 3.

Denote by $I_{\mathcal{P}}^{\beta}(G,H)$ the set of all $(H,\beta)$-robust
$h$-vectors $\mathbf{i}\in\mathbb{Z}^{k}$. Let $L_{\mathcal{P}}^{\beta}(G)$
denote the lattice (additive subgroup) in $\mathbb{Z}^{k}$ generated by
$I_{\mathcal{P}}^{\beta}(G,H)$.

  4. 4.

For every $j\in[k]$, let $\mathbf{u}_{j}\in\mathbb{Z}^{k}$ be the $j$th unit
vector, i.e. $\mathbf{u}_{j}$ has $1$ on the $j$th coordinate and 0 on the
other coordinates.

  5. 5.

A _transferral_ is a vector of the form $\mathbf{u}_{i}-\mathbf{u}_{j}$ for
some distinct $i,j\in[k]$.

As stated in Lemma 4.4, we shall prove that $V(G)$ is $(H,\beta n,t)$-closed
for some $\beta>0$ and $t\in\mathbb{N}$. Our proof adopts a less direct
approach as follows and builds on the merging techniques in [27]:

$(1)$

$1$-reachability: We first show that every vertex in $V(G)$ is $1$-reachable
to linearly many vertices (see Lemma 4.6);

$(2)$

Reachablility partition: Then construct a partition
$\mathcal{P}=\\{V_{1},\ldots,V_{p}\\}$ of $V(G)$ such that every $V_{i}$ is
closed (see Lemma 4.7);

$(3)$

Merging process: Lemma 4.8 allows us to merge two parts $V_{i},V_{j}$ into a
larger (still closed) part, provided that there exists a transferral
$\mathbf{u}_{i}-\mathbf{u}_{j}$ in the lattice $L_{\mathcal{P}}^{\beta}(G)$
for some $\beta>0$. Then the arguments often reduce to iteratively detecting
the existence of a transferral with respect to the up-to-date partition.

Here we collect a couple of lemmas as sketched above which together decode the
proof of Lemma 4.4.

######  Lemma 4.6.

Let $H$ be an $h$-vertex graph and $\chi(H)=r\geq 2$. For any $\alpha>0$,
there exist $\mu,\beta_{1},\gamma_{1}>0$ such that for any sufficiently large
$n$, if $(G,\mathcal{F})$ is an
$\left(n,1-\frac{1}{r-1}+\alpha,\mu\right)$-incompatibility system, then every
vertex $u\in V(G)$ is $(H,\beta_{1}n,1)$-reachable to at least $\gamma_{1}n$
other vertices.

######  Lemma 4.7 (see Lemma 4.1 in [27]).

For positive constants $\gamma_{1},\beta_{1}$, an integer $h\geq 2$ and an
$h$-vertex graph $H$, there exist
$\beta_{2}=\beta_{2}(\gamma_{1},\beta_{1},h)>0$ and $t\in\mathbb{N}$ such that
the following holds for sufficiently large $n$. Let $(G,\mathcal{F})$ be an
incompatibility system with $|G|=n$ such that every vertex in $V(G)$ is
$(H,\beta_{1}n,1)$-reachable to at least $\gamma_{1}n$ other vertices. Then
there is a partition $\mathcal{P}=\\{V_{1},\ldots,V_{p}\\}$ of $V(G)$ with
$p\leq\lceil\frac{1}{\gamma_{1}}\rceil$ such that for every $i\in[p]$, $V_{i}$
is $(H,\beta_{2}n,t)$-closed and has size at least $\frac{\gamma_{1}}{2}n$.

######  Lemma 4.8.

Given any positive integers $\ell,h,t$ with $h\geq 3$, constants $\beta,\mu>0$
and an $h$-vertex graph $H$, there exist $\beta^{\prime}>0$ and
$t^{\prime}\in\mathbb{N}$ such that the following holds for sufficiently large
$n$. Let $(G,\mathcal{F})$ be an incompatibility system with $|G|=n$ and
$\mathcal{P}=\\{V_{1},\ldots,V_{\ell}\\}$ be a partition of $V(G)$ such that
every $V_{i}$ is $(H,\beta n,t)$-closed. If $\mathbf{u}_{i}-\mathbf{u}_{j}\in
L_{\mathcal{P}}^{\mu}(G)$ for some distinct $i,j\in[\ell]$, then $V_{i}\cup
V_{j}$ is $(H,\beta^{\prime}n,t^{\prime})$-closed.

We shall present the proofs of Lemmas 4.6 and 4.8 in Sections 4.4 and 4.5,
respectively, whilst the proof of Lemma 4.7 follows that of Lemma 4.1 in [27]
and will be included in Appendix B for completeness.

###  4.3 $V(G)$ is closed

Now we are ready to prove Lemma 4.4, taking for granted Lemmas 4.6-4.8.

###### Proof of Lemma 4.4.

Given $\alpha>0$ and an $h$-vertex graph $H$ with $\chi(H)=r\geq 2$, we choose

$\frac{1}{n}\ll\mu,\beta,\frac{1}{t}\ll\alpha,\frac{1}{h}$

and let $(G,\mathcal{F})$ be an
$\left(n,1-\frac{1}{\chi^{*}(H)}+\alpha,\mu\right)$-incompatibility system. By
Lemma 4.6, we obtain that every vertex in $V(G)$ is
$(H,\beta_{1}n,1)$-reachable to at least $\gamma_{1}n$ other vertices in
$V(G)$. Then applying Lemma 4.7 on $G$, we obtain a partition
$\mathcal{P}_{0}=\\{V_{1},\ldots,V_{p}\\}$ of $V(G)$ for some integer
$p\leq\lceil\frac{1}{\gamma_{1}}\rceil$, where every $V_{i}$ is
$(H,\beta_{2}n,t_{2})$-closed and $|V_{i}|\geq\frac{\gamma_{1}n}{2}$.

We shall iteratively merge as many distinct parts as possible. As an
intermediate step, we choose positive constants

$\beta=\beta^{\prime}_{p+1}\ll\beta_{p+1}\ll\cdots\ll\beta_{3}^{\prime}\ll\beta_{3}\ll\beta_{2}^{\prime}\ll\beta_{2}\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\
\frac{1}{t}=\frac{1}{t_{p+1}}\ll\frac{1}{t_{p}}\cdots\ll\frac{1}{t_{3}}\ll\frac{1}{t_{2}}.$

Our merging procedure is stated as follows: at step $s$ ($s\geq 1$), based on
the current partition $\mathcal{P}_{s-1}=\\{V_{1},\ldots,V_{p^{\prime}}\\}$
with $p^{\prime}=p-s+1\in\mathbb{N}$ and every $V_{i}$ being
$(H,\beta_{s+1}n,t_{s+1})$-closed, if there exist distinct
$i,j\in[p^{\prime}]$ such that $\textbf{u}_{i}-\textbf{u}_{j}\in
L^{\beta^{\prime}_{s+1}}_{\mathcal{P}}(G)$, then we merge $V_{i},V_{j}$ as a
new part. In fact, by applying Lemma 4.8 with
$\beta=\beta_{s+1},\mu=\beta^{\prime}_{s+1}$ and $t=t_{s+1}$, we obtain that
$V_{i}\cup V_{j}$ is $(H,\beta_{s+2}n,t_{s+2})$-closed. By renaming if
necessary, we end the $s$th step with a new partition
$\mathcal{P}_{s}=\\{V_{1},\ldots,V_{p^{\prime}-1}\\}$ such that every $V_{i}$
is $(H,\beta_{s+2}n,t_{s+2})$-closed. In this way, we continue until the
procedure terminates after at most $p-1$ steps.

Suppose we end up with a final partition
$\mathcal{P}=\mathcal{P}_{s}=\\{V_{1},\ldots,V_{p^{\prime}}\\}$ for some
integer $p^{\prime}=p-s$ and $0\leq s<p$, where every $V_{i}$ is
$(H,\beta_{s+2}n,t_{s+2})$-closed. Now we claim that $p^{\prime}=1$, and thus
the proof is completed as $V(G)$ is $(H,\beta n,t)$-closed by taking
$\beta=\beta_{p+1}$ and $t=t_{p+1}$. Assume for a contradiction that
$p^{\prime}>1$, and recall that every $V_{i}$ is
$(H,\beta_{s+2}n,t_{s+2})$-closed with
$|V_{i}|\geq\frac{\gamma_{1}}{2}n,i\in[p^{\prime}]$. We additionally choose

$\beta^{\prime}_{s+2}\ll\frac{1}{M}\ll\varepsilon\ll
d\ll\alpha,\gamma_{1},\frac{1}{h}.$

Then by applying Lemma 3.5 on $G$ with constants $\varepsilon$ and
$d:=\frac{\alpha}{4}$, we obtain, as a refinement of $\mathcal{P}$, an
$(\varepsilon,d)$-regular partition
$\mathcal{P}^{*}=\\{V_{0}\\}\cup\\{V_{i,j}\subseteq
V_{i}:i\in[p^{\prime}],j\in[k_{i}]\\}$ and a spanning subgraph
$G^{\prime}\subseteq G$ such that $|V_{0}|\leq\varepsilon n$ and
$\frac{1}{\varepsilon}\leq\sum_{i=1}^{p^{\prime}}k_{i}\leq M$. We write
$m:=|V_{i,j}|$ for all $i\in[p^{\prime}],j\in[k_{i}]$ and
$k:=\sum_{i=1}^{p^{\prime}}k_{i}$. Let $R:=R(\varepsilon,d)$ be the reduced
graph for the $(\varepsilon,d)$-regular partition $\mathcal{P}^{*}$. By the
choice $\varepsilon\ll d\ll\alpha$ and the fact that
$\delta(G)\geq(1-\frac{1}{\chi^{*}(H)}+\alpha)n$, we have
$\delta(R)\geq\left(1-\frac{1}{\chi^{*}(H)}+\alpha-d-2\varepsilon\right)k\geq\left(1-\frac{1}{\chi^{*}(H)}+\frac{\alpha}{2}\right)k$.

We call a subgraph in $R$ _crossing_ with respect to $\mathcal{P}$ if it has
two vertices in $R$ whose corresponding clusters lie in different parts of
$\mathcal{P}$. Recall that $p^{\prime}>1$. Then the following claims allow us
to further merge $V_{i},V_{j}$ into a new part, a contrary to the minimality
of $p^{\prime}$. We divide the proof into two cases depending on the dichotomy
of $\chi^{*}(H)$. Before that, we state a simple fact as follows which would
widely be used in the proof.

######  Fact 4.9.

Let $G$ be an $n$-vertex graph and $v_{1},\ldots,v_{k}$ be $k$ distinct
vertices in $G$. Then

$|\cap_{i=1}^{k}N(v_{i})|\geq\Sigma_{i=1}^{k}|N(v_{i})|-(k-1)n.$

######  Claim 4.10.

If $\chi^{*}(H)=\chi(H)=r$, then there exist distinct $i,j\in[p^{\prime}]$
such that $\textbf{u}_{i}-\textbf{u}_{j}\in
L^{\beta^{\prime}_{s+2}}_{\mathcal{P}}(G)$.

###### Proof.

In this case, we have that
$\delta(R)\geq\left(1-\frac{1}{r}+\frac{\alpha}{2}\right)k>\frac{k}{2}$. Thus
we can easily find in $R$ a crossing edge, say $V_{i,1}V_{j,1}$ for distinct
$i,j\in[p^{\prime}]$. Next we show that such a pair $\\{i,j\\}$ is as desired
by finding two vectors

$\mathbf{s},\leavevmode\nobreak\ \mathbf{t}\in\leavevmode\nobreak\
I^{\beta^{\prime}_{s+2}}_{\mathcal{P}}(G)\leavevmode\nobreak\
\leavevmode\nobreak\ \text{with}\leavevmode\nobreak\ \leavevmode\nobreak\
\mathbf{s}-\mathbf{t}\leavevmode\nobreak\ =\leavevmode\nobreak\
\mathbf{u}_{i}-\mathbf{u}_{j}.$

By Fact 4.9, we can find a copy of $K_{r+1}$ containing $V_{i,1},V_{j,1}$ in
$R$, where the other $r-1$ vertices, without loss of generality, are denoted
as $V_{a_{1},1},\ldots,V_{a_{r-1},1}$.

Let $h_{1}\leq\ldots\leq h_{r}$ be the color-class sizes of $H$ under a proper
$r$-coloring of $V(H)$. Clearly, $H$ is a subgraph of
$K_{r}(h_{1},\ldots,h_{r})$. By Lemma 3.7 applied on $G$ with

$\eta=\frac{1-\varepsilon}{k},\leavevmode\nobreak\
U_{s}=V_{a_{s},1},s\in[r-1]\leavevmode\nobreak\ \text{and}\leavevmode\nobreak\
U_{r}=V_{j,1}$

and the fact that $\frac{1}{n}\ll\mu\ll\varepsilon\ll d$, we obtain that there
exist at least $c(r,d,h)m^{h}$ compatible copies of
$K_{r}(h_{1},\ldots,h_{r})$ (also $H$) in
$G[V_{a_{1},1},\ldots,V_{a_{r-1},1},V_{j,1}]$, each containing exactly $h_{s}$
vertices in $V_{a_{s},1}$ for every $s\in[r-1]$ and $h_{r}$ vertices in
$V_{j,1}$. Note that all those compatible copies of $H$ have the same index
vector with respect to $\mathcal{P}$, denoted by $\mathbf{t}$. Similarly,
Lemma 3.7 applied on $G$ with

$\eta=\frac{1-\varepsilon}{k},\leavevmode\nobreak\
U_{s}=V_{a_{s},1},s\in[r-1]\leavevmode\nobreak\ \text{and}\leavevmode\nobreak\
U_{r}=V_{j,1},U_{r+1}=V_{i,1}$

gives at least $c(r+1,d,h)\prod_{i=1}^{r}m^{h_{i}}$ compatible copies of
$K_{r+1}(h_{1},\ldots,h_{r}-1,1)$ (also $H$ and here we may assume $h_{r}>1$
as the case $h_{r}=1$ can be done in the same way) each containing exactly
$h_{s}$ vertices in $V_{a_{s},1}$ for every $s\in[r-1]$, $h_{r}-1$ vertices in
$V_{j,1}$ and one vertex in $V_{i,1}$, where the corresponding index vector is
denoted as $\mathbf{s}$. Then it is to see that
$\mathbf{s}-\mathbf{t}=\textbf{u}_{i}-\textbf{u}_{j}$ and we claim that
$\mathbf{s},\mathbf{t}\in I^{\beta^{\prime}_{s+2}}_{\mathcal{P}}(G)$. Indeed,
this easily follows by the choice
$\beta^{\prime}_{s+2}\ll\frac{1}{M}\ll\varepsilon\ll d\ll\alpha,\frac{1}{h}$
and the fact that there are at least $c^{\prime}m^{h}$ compatible copies of
$H$ for $c^{\prime}=\min\\{c(r,d,h),c(r+1,d,h)\\}$, whose vertex sets all have
index vector $\mathbf{s}$ (or $\mathbf{t}$). ∎

Before diving into the case $\chi^{*}(H)=\chi_{cr}(H)$ (i.e.
$\mathrm{hcf}(H)=1$), we first deal with a case which would commonly be used.

######  Claim 4.11.

If $\mathrm{hcf}_{\chi}(H)$ is finite and $R$ has a crossing copy of $K_{r}$,
then there exist distinct $i,j\in[p^{\prime}]$ such that
$\mathrm{hcf}_{\chi}(H)(\textbf{u}_{i}-\textbf{u}_{j})\in
L^{\beta^{\prime}_{s+2}}_{\mathcal{P}}(G)$.

###### Proof.

Without loss of generality, let $V_{x_{1},1},\ldots,V_{x_{r},1}$ be the
vertices of a crossing copy of $K_{r}$ in $R$, where $x_{1}=1,x_{2}=2$ and
$1\leq x_{3}\leq\ldots\leq x_{r}\leq p^{\prime}$ (if $r\geq 3$). Next we show
that such a pair $\\{1,2\\}$ is as desired.

For any $r$-coloring $\phi$ in $\mathcal{C}(H)$ and its color-class sizes
$h_{1}^{\phi}\leq\cdots\leq h_{r}^{\phi}$, by Lemma 3.7 applied on
$G^{\prime}$ with $U_{i}=V_{x_{i},1}$ for every $i\in[r]$, we obtain for every
permutation $\sigma\in\mathbf{S}_{r}$, a family $\mathcal{F}_{\sigma}$ of at
least $cm^{h}$ compatible copies of $H$ each containing exactly
$h_{\sigma(i)}^{\phi}$ vertices in $V_{x_{i},1}$ for $i\in[r]$. It is easy to
see by definition that every $\mathcal{F}_{\sigma}$ yields a
$(H,\beta^{\prime}_{s+2})$-robust $h$-vector, denoted as
$\mathbf{i}_{\sigma}^{\phi}$, whose $i$th coordinate is

$\mathbf{i}_{\sigma}^{\phi}(i)=\sum_{s:x_{s}=i}h_{\sigma(s)}^{\phi},\leavevmode\nobreak\
i\in[p^{\prime}].$

Thus for every $i\in[r-1]$, we choose
$\sigma,\sigma^{\prime}\in\mathbf{S}_{r}$ which have
$\sigma(1)=i=\sigma^{\prime}(2),\sigma(2)=i+1=\sigma^{\prime}(1)$ and
$\sigma(j)=\sigma^{\prime}(j)$ for $j\neq 1,2$. Then it follows that

$\mathbf{d}_{i}^{\phi}:=(h_{i+1}^{\phi}-h_{i}^{\phi},h_{i}^{\phi}-h_{i+1}^{\phi},0,\ldots,0)\leavevmode\nobreak\
=\leavevmode\nobreak\
\mathbf{i}_{\sigma^{\prime}}^{\phi}-\mathbf{i}_{\sigma}^{\phi}\leavevmode\nobreak\
\in\leavevmode\nobreak\ L^{\beta^{\prime}_{s+2}}_{\mathcal{P}}(G).$

Recall that
$D(H)=\bigcup_{{\phi}\in\mathcal{C}(H)}\\{h_{i+1}^{\phi}-h_{i}^{\phi}:i\in[r-1]\\}$
and all the integers in $D(H)$ have the highest common factor
$\mathrm{hcf}_{\chi}(H)$. Then there exist integers $a_{i}^{\phi}$ for any
${\phi}\in\mathcal{C}(H),i\in[r-1]$ such that

$\sum_{{\phi}\in\mathcal{C}(H),i\in[r-1]}a_{i}^{\phi}\leavevmode\nobreak\
(h_{i+1}^{\phi}-h_{i}^{\phi})\leavevmode\nobreak\ =\leavevmode\nobreak\
\mathrm{hcf}_{\chi}(H).$

Therefore

$\sum_{{\phi}\in\mathcal{C}(H),i\in[r-1]}a_{i}^{\phi}\leavevmode\nobreak\
\mathbf{d}_{i}^{\phi}\leavevmode\nobreak\ =\leavevmode\nobreak\
(\mathrm{hcf}_{\chi}(H),-\mathrm{hcf}_{\chi}(H),0,\ldots,0)$

and by definition we have
$\mathrm{hcf}_{\chi}(H)(\mathbf{u}_{1}-\mathbf{u}_{2})\in
L^{\beta^{\prime}_{s+2}}_{\mathcal{P}}(G)$. This completes the proof. ∎

Now we are ready to study the case $\chi^{*}(H)=\chi_{cr}(H)$. If $r\geq 3$,
then by definition, it follows that $\mathrm{hcf}_{\chi}(H)=1$. Moreover,
since $\chi_{cr}(H)>r-1$, it holds that
$\delta(R)\geq\left(1-\frac{1}{r-1}+\frac{\alpha}{2}\right)k>\frac{k}{2}$ and
we can easily find in $R$ a crossing edge, say $V_{1,1}V_{2,1}$ for simple. By
Fact 4.9 with $k=r-1$, we can similarly find a crossing copy of $K_{r}$
containing $V_{1,1},V_{2,1}$, and we are done by Claim 4.11. Hence, it remains
to consider the case when $H$ is bipartite with $\mathrm{hcf}_{c}(H)=1$ and
$\mathrm{hcf}_{\chi}(H)\leq 2$.

######  Claim 4.12.

If $\chi(H)=2$, $\mathrm{hcf}_{c}(H)=1$ and $\mathrm{hcf}_{\chi}(H)\leq 2$,
then there exist distinct $i,j\in[p^{\prime}]$ such that
$\textbf{u}_{i}-\textbf{u}_{j}\in L^{\beta^{\prime}_{s+2}}_{\mathcal{P}}(G)$.

###### Proof.

Since $\mathrm{hcf}_{c}(H)=1$, one can easily observe that $H$ is
disconnected. Let $C_{1},C_{2},\ldots,C_{\ell}$ be the components of $H$ and
$c_{i}:=|C_{i}|,i\in[\ell]$. We further split the argument into two subcases:
$\mathrm{hcf}_{\chi}(H)=1,2$.

If $\mathrm{hcf}_{\chi}(H)=1$, then we may further assume that $R$ contains no
crossing edge as otherwise we are done by Claim 4.11. Since $p^{\prime}\geq
2$, we can pick two edges from different parts, say $V_{1,1}V_{1,2}$ and
$V_{2,1}V_{2,2}$. Clearly, every component $C_{i}$ is a subgraph of $K_{h,h}$.
By Lemma 3.7 on $V_{1,1},V_{1,2}$ (resp. $V_{2,1},V_{2,2}$), we obtain for
every subset $S\subseteq[\ell]$, a family $\mathcal{F}_{S}$ of at least
$c^{2}m^{h}$ compatible copies of $H$ each containing exactly $\sum_{i\in
S}c_{i}$ vertices in $V_{1}$ and $h-\sum_{i\in S}c_{i}$ vertices in $V_{2}$.
It is easy to see by definition that every $\mathcal{F}_{S}$ yields an
$(H,\beta_{s+2}^{\prime})$-robust $h$-vector, denoted as
$\mathbf{i}_{S}:=(\sum_{i\in S}c_{i},h-\sum_{i\in S}c_{i},0,\ldots,0)$. Thus
for every $i\in[\ell]$, we choose $S=\\{i\\},S^{\prime}=\emptyset$ and it
follows that

$\mathbf{d}_{i}:=(c_{i},-c_{i},0,\ldots,0)\leavevmode\nobreak\
=\leavevmode\nobreak\
\mathbf{i}_{S}-\mathbf{i}_{S^{\prime}}\leavevmode\nobreak\
\in\leavevmode\nobreak\ L^{\beta^{\prime}_{s+2}}_{\mathcal{P}}(G).$

Recall that all the integers in $\\{c_{1},c_{2},\ldots,c_{\ell}\\}$ have the
highest common factor $\mathrm{hcf}_{c}(H)=1$. Then there exist integers
$a_{i}$, $i\in[\ell]$ such that $\sum_{i\in[\ell]}a_{i}c_{i}=1$. Therefore

$\sum_{i\in[\ell]}a_{i}\mathbf{d}_{i}=(1,-1,0,\ldots,0)$

and thus by definition we have $\mathbf{u}_{1}-\mathbf{u}_{2}\in
L^{\beta^{\prime}_{s+2}}_{\mathcal{P}}(G)$.

For the case $\mathrm{hcf}_{\chi}(H)=2$, we may instead assume that there
exists a crossing edge in $R$. As otherwise we can pick two edges from
different parts since $p^{\prime}\geq 2$, one can thus follow the same
arguments in the paragraph above. Let $V_{1,1}V_{2,1}$ be such a crossing
edge. Then Claim 4.11 immediately implies that
$2(\mathbf{u}_{1}-\mathbf{u}_{2})\in
L^{\beta^{\prime}_{s+2}}_{\mathcal{P}}(G)$.

Since $\mathrm{hcf}_{\chi}(H)=2$ and $\mathrm{hcf}_{c}(H)=1$, it is easy to
observe that $h=0$ (mod $2$) and there exists an odd component of $H$, say
$C_{1}$, i.e. $c_{1}$ is odd. Given a $2$-coloring $\phi$ in $\mathcal{C}(H)$,
we write $x_{1},x_{2}$ as the color-class sizes for $C_{1}$, and $y_{1},y_{2}$
for $H-C_{1}$ under $\phi$. We may further assume by observation that $x_{1}$
and $y_{1}$ are odd whilst $x_{2}$ and $y_{2}$ are even. Recall that
$V_{1,1}V_{2,1}$ is a crossing edge. Then by Lemma 3.7 applied on $G$ with
$r=2,U_{1}=V_{1,1},U_{2}=V_{2,1}$ and $h_{1}=x_{1}+y_{1},h_{2}=x_{2}+y_{2}$,
we obtain at least $cm^{h}$ compatible copies of $H$ each containing exactly
$x_{i}+y_{i}$ vertices in $V_{i,1}$ for $i\in[2]$. It is easy to see by
definition that every such family yields an $(H,\beta^{\prime}_{s+2})$-robust
$h$-vector, denoted as
$\mathbf{i}_{even}:=(x_{1}+y_{1},x_{2}+y_{2},0,\ldots,0)$. Similarly we obtain
$\mathbf{i}_{odd}:=(x_{1}+y_{2},x_{2}+y_{1},0,\ldots,0)\in
I^{\beta^{\prime}_{s+2}}_{\mathcal{P}}(G)$.

Recall that $2(\mathbf{u}_{1}-\mathbf{u}_{2})\in
L^{\beta^{\prime}_{s+2}}_{\mathcal{P}}(G)$. Since $y_{1}-y_{2}$ is odd, by
letting $s=\frac{y_{1}-y_{2}-1}{2}$, we obtain that

$\mathbf{i}_{even}-\mathbf{i}_{odd}-2s(\mathbf{u}_{1}-\mathbf{u}_{2})=\mathbf{u}_{1}-\mathbf{u}_{2}\leavevmode\nobreak\
\in\leavevmode\nobreak\ L^{\beta^{\prime}_{s+2}}_{\mathcal{P}}(G).$

This completes the proof. ∎

∎

###  4.4 1-reachablility

In this section, we shall focus on proving Lemma 4.6.

###### Proof of Lemma 4.6.

Given $\alpha>0$, we choose

$\frac{1}{n}\ll\mu,\beta_{1}\ll c,\gamma_{1}\ll\frac{1}{M}\ll\varepsilon\ll
d\ll\alpha,\frac{1}{h}.$

Apply Lemma 3.5 on $G$ and obtain an $(\varepsilon,d)$-regular partition
$V(G)=V_{0}\cup V_{1}\cup\ldots\cup V_{k}$ for some $1/\varepsilon\leq k\leq
M$ such that $|V_{0}|\leq\varepsilon n,|V_{i}|=m$ for every $i\in[k]$. Let
$R=R(\varepsilon,d)$ be the reduced graph for this partition. Then
$\delta(R)\geq\left(1-\frac{1}{r-1}+\frac{\alpha}{2}\right)k$.

Choose an arbitrary vertex $u$ from $V(G)$. Let
$N^{\alpha/2}=\\{V_{i}:i\in[k]\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ |N_{G}(u)\cap V_{i}|\geq\alpha m/2\\}$. By the
double counting, we have

$(1-1/(r-1)+\alpha)n-|V_{0}|\leq d_{G-V_{0}}(u)\leq|N^{\alpha/2}|\cdot
m+(k-|N^{\alpha/2}|)\cdot\alpha m/2,$

that is, $|N^{\alpha/2}|\geq\left(1-\frac{1}{r-1}+\frac{\alpha}{4}\right)k$.
Let $\ell=\left(1-\frac{1}{r-1}+\frac{\alpha}{4}\right)k$. We choose arbitrary
$\ell$ clusters from $N^{\alpha/2}$. Suppose that the corresponding vertices
in $R$ of these $\ell$ clusters are $V_{1},\ldots,V_{\ell}$. Write
$L=\\{V_{1},\ldots,V_{\ell}\\}$. Then we shall find a copy of $K_{r-1}$ in
$R[L]$. Indeed, the case when $r=2$ is trivial and thus we assume that $r\geq
3$. Since $\delta(R)\geq\left(1-\frac{1}{r-1}+\frac{\alpha}{2}\right)k$, we
have $\delta(R[L])\geq\left(1-\frac{2}{r-1}+\frac{3\alpha}{4}\right)k$. Since
$(r-2)\left(1-\frac{2}{r-1}+\frac{3\alpha}{4}\right)k-(r-3)\ell>1$, by Fact
4.9 with $k=r-2$, we can greedily pick a copy of $K_{r-1}$ as every $r-2$
vertices in $L$ have a common neighbor in $L$. Suppose that the corresponding
clusters of this copy of $K_{r-1}$ are $V_{1},\ldots,V_{r-1}$. Again by Fact
4.9 applied on $R$ with $k=r-1$ and the fact that
$(r-1)\left(1-\frac{1}{r-1}+\frac{\alpha}{2}\right)k-(r-2)k>1$, we obtain that
$V_{1},\ldots,V_{r-1}$ have a common neighbor in $V(R)$, say $V_{r}$. It is
worth noting that here the cluster $V_{r}$ may not in $L$. Let
$V_{i}^{\prime}=V_{i}\cap N_{G}(u)$ for every $i\in[r-1]$. Then
$|V_{i}^{\prime}|\geq\frac{\alpha
m}{2}\geq\frac{\alpha(1-\varepsilon)}{2k}n,i\in[r-1]$.

Let $V^{\prime}_{r}:=\\{v\in V_{r}\mid
d_{V_{i}^{\prime}}(v)\geq(d-\varepsilon)|V_{i}^{\prime}|\text{
\leavevmode\nobreak\ for\leavevmode\nobreak\ each\leavevmode\nobreak\
}i\in[r-1]\\}$. Then by Fact 3.3, we have that
$|V_{r}^{\prime}|\geq(1-(r-1)\varepsilon)m\geq\frac{1}{2}m$. The following
claim would finish the proof as $|V_{r}^{\prime}|\geq\gamma_{1}n$.

######  Claim 4.13.

Every vertex $v\in V_{r}^{\prime}$ is $(H,\beta_{1}n,1)$-reachable to $u$.

To prove this, for every $v\in V_{r}^{\prime}$, we write
$U_{i}=V_{i}^{\prime}\cap N(v)$ for every $i\in[r-1]$ and
$U_{r}:=V_{r}^{\prime}\setminus\\{v\\}$. Then
$|U_{i}|\geq(d-\varepsilon)|V_{i}^{\prime}|\geq\frac{d\alpha}{4}m\geq\frac{d\alpha}{8M}n,i\in[r]$
and Lemma 3.4 implies that $U_{1},\ldots,U_{r}$ are pairwise
$(\varepsilon^{\prime},d^{\prime})$-regular with
$\varepsilon^{\prime}=\max\\{4\varepsilon/d\alpha,2\varepsilon\\}$ and
$|d^{\prime}-d|<\varepsilon$. By Lemma 3.7 on $G$ with all subsets $U_{i}$ as
given above, $\eta=\frac{d\alpha}{8M}$ and the fact that
$\mu\ll\frac{1}{M}\ll\varepsilon\ll d\ll\alpha,\frac{1}{h}$, we obtain at
least $cn^{rh-1}$ compatible copies of $K_{r}(h,\ldots,h,h-1)$ in
$G[U_{1},\ldots,U_{r}]$ each containing $h$ vertices in $U_{i}$ for
$i\in[r-1]$ and $h-1$ vertices in $U_{r}$. Note that by Fact 3.11, there are
at most $4\mu n^{rh-1}\leq\frac{c}{2}n^{rh-1}$ compatible copies of
$K_{r}(h,\ldots,h,h-1)$, each of which fails to form a compatible copy of
$K^{h}_{r}$ with $u$ or $v$. Therefore we can find a family $\mathcal{K}$ of
at least $\frac{c}{2}n^{rh-1}$ compatible copies of $K_{r}(h,\ldots,h,h-1)$
which together with $u$ (also for $v$) form compatible copies of $K^{h}_{r}$.
Moreover, from the choice $\beta_{1}\ll c$, one can observe that deleting an
arbitrary set of $\beta_{1}n$ vertices would destroy at most
$\beta_{1}n^{rh-1}<|\mathcal{K}|$ copies of $K_{r}(h,\ldots,h,h-1)$ in
$\mathcal{K}$. Thus, $u$ and $v$ are $(K^{h}_{r},\beta_{1}n,1)$-reachable and
also are $(H,\beta_{1}n,1)$-reachable. ∎

###  4.5 Transferral

Following similar arguments as in the proof of Lemma 3.9 in [28], we give a
proof of Lemma 4.8.

###### Proof of Lemma 4.8.

Let $G$, $\beta,\mu>0$ and $\mathcal{P}=\\{V_{1},V_{2},\ldots,V_{\ell}\\}$ be
a partition of $V(G)$ as given in the assumption. Recall that
$I=I_{\mathcal{P}}^{\mu}(G)\subseteq\mathbb{Z}^{\ell}$ is a base for
$L_{\mathcal{P}}^{\mu}(G)$, that is, every vector in
$L_{\mathcal{P}}^{\mu}(G)$ can be written as linear combinations of the
$h$-vectors in $I$. Thus given $\mathbf{u}_{i}-\mathbf{u}_{j}\in
L_{\mathcal{P}}^{\mu}(G)$, there exist $a_{\mathbf{v}}\in\mathbb{Z}$ such that
$\mathbf{u}_{i}-\mathbf{u}_{j}=\sum_{\mathbf{v}\in
I}a_{\mathbf{v}}\mathbf{v}$. Without loss of generality, we may take $i=1,j=2$
for instance. For every $\mathbf{v}\in I$, let
$p_{\mathbf{v}}=\max\\{a_{\mathbf{v}},0\\}$ and
$q_{\mathbf{v}}=\max\\{-a_{\mathbf{v}},0\\}$. Hence

$\displaystyle\mathbf{u}_{1}-\mathbf{u}_{2}=\sum_{\mathbf{v}\in
I}(p_{\mathbf{v}}-q_{\mathbf{v}})\mathbf{v}\quad i.e.,\quad\sum_{\mathbf{v}\in
I}{q_{\mathbf{v}}}\mathbf{v}+\mathbf{u}_{1}=\sum_{\mathbf{v}\in
I}{p_{\mathbf{v}}}\mathbf{v}+\mathbf{u}_{2}.$ (2)

By comparing the sums of all the coordinates from two sides of either equation
in (2), we obtain that $\sum_{\mathbf{v}\in
I}{p_{\mathbf{v}}}=\sum_{\mathbf{v}\in I}{q_{\mathbf{v}}}=:C$.

Next, by choosing
$\frac{1}{n}\ll\beta^{\prime},\frac{1}{t^{\prime}}\ll\beta,\mu,\frac{1}{C},\frac{1}{t},\frac{1}{h}$,
we shall show that every two vertices $x\in V_{1}$ and $y\in V_{2}$ are
$(H,\beta^{\prime}n,t^{\prime})$-reachable. Let $x$ and $y$ be given as above
and $W\subset V(G)\setminus\\{x,y\\}$ be any vertex set of size
$\beta^{\prime}n$. Since every $h$-vector $\mathbf{v}\in I$ is $(H,\mu
n)$-robust and $\beta^{\prime}\ll\mu$, we can greedily select, outside
$W\cup\\{x,y\\}$, a collection of $p_{\mathbf{v}}+q_{\mathbf{v}}$ vertex-
disjoint compatible copies of $H$ with index vector $\mathbf{v}$ for every
$\mathbf{v}\in I$. This is possible as during the process we need to avoid at
most $|W|+2+h\sum_{\mathbf{v}\in
I}(p_{\mathbf{v}}+q_{\mathbf{v}})<\frac{\mu}{2}n$ vertices. This gives rise to
two disjoint families $\mathcal{F}^{p}$ and $\mathcal{F}^{q}$, where
$\mathcal{F}^{p}$ consists of $p_{\mathbf{v}}$ vertex-disjoint compatible
copies of $H$ with index vector $\mathbf{v}$ for every $\mathbf{v}\in I$, and
$\mathcal{F}^{q}$ consists of $q_{\mathbf{v}}$ vertex-disjoint compatible
copies of $H$ with index vector $\mathbf{v}$ for every $\mathbf{v}\in I$.

By equality (2), we have $|V(\mathcal{F}^{p})|=|V(\mathcal{F}^{q})|=hC$ and
$\mathbf{i}(V(\mathcal{F}^{q}))+\mathbf{u}_{1}=\mathbf{i}(V(\mathcal{F}^{p}))+\mathbf{u}_{2}$.
This implies that we may write $V(\mathcal{F}^{p})=\\{x_{1},\dots,x_{hC}\\}$,
$V(\mathcal{F}^{q})=\\{y_{1},\dots,y_{hC}\\}$ such that $x_{1}\in V_{1}$,
$y_{1}\in V_{2}$, and for $i\geq 2$, $x_{i}$ and $y_{i}$ are from the same
part of $\mathcal{P}$. Since each $V_{i}$ is $(H,\beta n,t)$-closed for each
$i\in[\ell]$, we greedily pick a collection $\\{S_{2},S_{3},\ldots,S_{hC}\\}$
of vertex disjoint subsets in $V(G)\setminus(W\cup
V(\mathcal{F}^{p}\cup\mathcal{F}^{q})\cup\\{x,y\\})$ such that every $S_{j}$
is an $H$-connector for $x_{j},y_{j}$ with $|S_{j}|\leq ht-1$ for $2\leq j\leq
hC$. Indeed, by the choice that
$\frac{1}{n}\ll\beta^{\prime}\ll\beta,\frac{1}{C},\frac{1}{h}$, we need to
avoid at most

$\left|\left(\bigcup_{j=2}^{hC}S_{j}\right)\cup W\cup
V(\mathcal{F}^{p}\cup\mathcal{F}^{q})\cup\\{x,y\\}\right|\leq\frac{\beta}{2}n$

vertices and therefore we are able to select every $S_{j}$ as $x_{j}$ and
$y_{j}$ are $(H,\beta n,t)$-reachable for $2\leq j\leq hC$. Similarly, we
additionally choose two $H$-connectors vertex disjoint from each other and all
other previously chosen vertices, say $S_{0}$ and $S_{1}$ for $x,x_{1}$ and
$y,y_{1}$, respectively. At this point, we shall verify that the set
$\hat{S}:=\bigcup_{j=0}^{hC}S_{j}\cup V(\mathcal{F}^{p}\cup\mathcal{F}^{q})$
is an $H$-connector for $x,y$ with size at most $h(t+C+thC)-1$. In fact, to
build a compatible $H$-factor for $G[\hat{S}\cup\\{x\\}]$ (leaving $y$
uncovered), we can take $H$-tilings in $G[S_{0}\cup\\{x\\}]$,
$G[V(\mathcal{F}^{p})]$ and $G[S_{j}\cup\\{y_{j}\\}]$ for $j\in[hC]$, which
altogether form an $H$-tiling as desired. Similarly, one can observe that
$G[\hat{S}\cup\\{y\\}]$ also admits a compatible $H$-factor. Hence $x$ and $y$
are $\left(H,\beta^{\prime}n,t^{\prime}\right)$-reachable by taking
$t^{\prime}=t+C+thC$.

∎

##  5 Acknowledgement

The authors would like to thanks Jie Han, Laihao Ding and Guanghui Wang for
stimulating discussions and valuable comments.

Note added before submission. While preparing this paper, we learnt that
Yangyang Cheng and Laihao Ding proved various Turán-type results in the
incompatibility systems.

## References

  * [1] N. Alon and G. Gutin.  Properly colored Hamilton cycles in edge-colored complete graphs.  Random Structures & Algorithms, 11(2):179–186, 1997.
  * [2] N. Alon, T. Jiang, Z. Miller, and D. Pritikin.  Properly colored subgraphs and rainbow subgraphs in edge-colorings with local constraints.  Random Structures & Algorithms, 23(4):409–433, 2003.
  * [3] N. Alon and B. Sudakov.  Increasing the chromatic number of a random graph.  arXiv preprint arXiv:1002.1748, 2010.
  * [4] N. Alon and R. Yuster.  $H$-factors in dense graphs.  Journal of Combinatorial Theory, Series B, 66(2):269–282, 1996\.
  * [5] J. Balogh, B. Csaba, and W. Samotij.  Local resilience of almost spanning trees in random graphs.  Random Structures & Algorithms, 38(1-2):121–139, 2011.
  * [6] J. Beck.  Random graphs and positional games on the complete graph.  North-Holland Mathematics Studies, 118:7–13, 1985.
  * [7] S. Ben-Shimon, M. Krivelevich, and B. Sudakov.  On the resilience of Hamiltonicity and optimal packing of Hamilton cycles in random graphs.  SIAM Journal on Discrete Mathematics, 25(3):1176–1193, 2011.
  * [8] B. Bollobás and P. Erdős.  Alternating Hamiltonian cycles.  Israel Journal of Mathematics, 23(2):126–131, 1976.
  * [9] B. Bollobás and A. Papaioannou.  A biased Hamiltonian game.  Congressus Numerantium, 35:105–115, 1982.
  * [10] J. Bondy.  Paths and cycles.  in Handbook of Combinatorics, (edited by R. Graham, M. Grotschel, and L. Lovász) 1:5–110, 1995.
  * [11] F. Chang, J. Han, J. Kim, G. Wang, and D. Yang.  Embedding clique-factors in graphs with low $\ell$-independence number.  arXiv preprint arXiv:2111.10512, 2021.
  * [12] Y. Chang, J. Han, Y. Kohayakawa, P. Morris, and G. O. Mota.  Factors in randomly perturbed hypergraphs.  arXiv preprint arXiv:2008.01031, 2020.
  * [13] C. Chen and D. E. Daykin.  Graphs with Hamiltonian cycles having adjacent lines different colors.  Journal of Combinatorial Theory, Series B, 21(2):135–139, 1976\.
  * [14] V. Chvátal and P. Erdős.  Biased positional games.  Annals of Discrete Mathematics, 2:221–229, 1978.
  * [15] O. Cooley, D. Kühn, and D. Osthus.  Perfect packings with complete graphs minus an edge.  European Journal of Combinatorics, 28(8):2143–2155, 2007.
  * [16] M. Coulson, P. Keevash, G. Perarnau, and L. Yepremyan.  Rainbow factors in hypergraphs.  Journal of Combinatorial Theory, Series A, 172:105184, 2020.
  * [17] M. Coulson and G. Perarnau.  Rainbow matchings in dirac bipartite graphs.  Random Structures & Algorithms, 55(2):271–289, 2019.
  * [18] M. Coulson and G. Perarnau.  A rainbow Dirac’s theorem.  SIAM Journal on Discrete Mathematics, 34(3):1670–1692, 2020.
  * [19] D. Dellamonica Jr, Y. Kohayakawa, M. Marciniszyn, and A. Steger.  On the resilience of long cycles in random graphs.  The Electronic Journal of Combinatorics, 15(1):R32, 2008.
  * [20] R. Diestel.  Extremal graph theory.  In Graph Theory, pages 173–207. Springer, 2017.
  * [21] G. A. Dirac.  Some theorems on abstract graphs.  Proceedings of the London Mathematical Society, 3(1):69–81, 1952\.
  * [22] S. Ehard, S. Glock, and F. Joos.  A rainbow blow-up lemma for almost optimally bounded edge-colourings.  Forum of Mathematics, Sigma, 8, 2020.
  * [23] P. Erdős and J. Spencer.  Lopsided lovász local lemma and latin transversals.  Discrete Applied Mathematics, 30(2-3):151–154, 1991.
  * [24] S. Glock and F. Joos.  A rainbow blow-up lemma.  Random Structures & Algorithms, 56(4):1031–1069, 2020.
  * [25] A. Hajnal and E. Szemerédi.  Proof of a conjecture of P. Erdős.  Combinatorial Theory and Its Applications, 2:601–623, 1970.
  * [26] J. Han.  Decision problem for perfect matchings in dense $k$-uniform hypergraphs.  Transactions of the American Mathematical Society, 369(7):5197–5218, 2017.
  * [27] J. Han, P. Morris, G. Wang, and D. Yang.  A Ramsey–Turán theory for tilings in graphs.  arXiv preprint arXiv:2106.09688, 2021.
  * [28] J. Han, C. Zang, and Y. Zhao.  Minimum vertex degree thresholds for tiling complete 3-partite 3-graphs.  Journal of Combinatorial Theory. Series A, 149:115–147, 2017.
  * [29] K.-i. Kawarabayashi.  $K^{-}_{4}$-factor in a graph.  Journal of Graph Theory, 39(2):111–128, 2002.
  * [30] P. Keevash, F. Knox, and R. Mycroft.  Polynomial-time perfect matchings in dense hypergraphs.  Advances in Mathematics, 269:265–334, 2015.
  * [31] J. Kim, D. Kühn, A. Kupavskii, and D. Osthus.  Rainbow structures in locally bounded colorings of graphs.  Random Structures & Algorithms, 56(4):1171–1204, 2020.
  * [32] J. Komlós.  Tiling Turán theorems.  Combinatorica, 20(2):203–218, 2000.
  * [33] J. Komlós, G. Sárközy, and E. Szemerédi.  Proof of the Alon–Yuster conjecture.  Discrete Mathematics, 235(1-3):255–269, 2001.
  * [34] J. Komlós, G. N. Sárközy, and E. Szemerédi.  Blow-up lemma.  Combinatorica, 17(1):109–123, 1997.
  * [35] J. Komlós and M. Simonovits.  Szemerédi’s Regularity Lemma and its applications in graph theory.  Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), 1996.
  * [36] A. Kotzig.  Moves without forbidden transitions in a graph.  Matematickỳ časopis, 18(1):76–80, 1968.
  * [37] M. Krivelevich.  The critical bias for the Hamiltonicity game is $(1+o(1))n/\ln n$.  Journal of the American Mathematical Society, 24(1):125–131, 2011\.
  * [38] M. Krivelevich, C. Lee, and B. Sudakov.  Resilient pancyclicity of random and pseudorandom graphs.  SIAM Journal on Discrete Mathematics, 24(1):1–16, 2010.
  * [39] M. Krivelevich, C. Lee, and B. Sudakov.  Robust Hamiltonicity of Dirac graphs.  Transactions of the American Mathematical Society, 366(6):3095–3130, 2014.
  * [40] M. Krivelevich, C. Lee, and B. Sudakov.  Compatible Hamilton cycles in random graphs.  Random Structures & Algorithms, 49(3):533–557, 2016.
  * [41] M. Krivelevich, C. Lee, and B. Sudakov.  Compatible Hamilton cycles in Dirac graphs.  Combinatorica, 37(4):697–732, 2017.
  * [42] M. Krivelevich and T. Szabó.  Biased positional games and small hypergraphs with large covers.  The Electronic Journal of Combinatorics, R70, 2008.
  * [43] D. Kühn and D. Osthus.  The minimum degree threshold for perfect graph packings.  Combinatorica, 29(1):65–107, 2009.
  * [44] A. Lo.  Properly coloured Hamiltonian cycles in edge-coloured complete graphs.  Combinatorica, 36(4):471–492, 2016.
  * [45] A. Lo and K. Markström.  $F$-factors in hypergraphs via absorption.  Graphs and Combinatorics, 31(3):679–712, 2015.
  * [46] R. Montgomery.  Spanning trees in random graphs.  Advances in Mathematics, 356:106–793, 2019.
  * [47] R. Montgomery, A. Pokrovskiy, and B. Sudakov.  Embedding rainbow trees with applications to graph labelling and decomposition.  Journal of the European Mathematical Society, 22(10):3101–3132, 2020.
  * [48] R. Nenadov and Y. Pehova.  On a Ramsey–Turán variant of the Hajnal–Szemerédi theorem.  SIAM Journal on Discrete Mathematics, 34(2):1001–1010, 2020.
  * [49] V. Rödl, A. Ruciński, and E. Szemerédi.  Perfect matchings in large uniform hypergraphs with large minimum collective degree.  Journal of Combinatorial Theory, Series A, 116(3):613–636, 2009\.
  * [50] J. Shearer.  A property of the colored complete graph.  Discrete Mathematics, 25(2):175–178, 1979.
  * [51] A. Shokoufandeh and Y. Zhao.  Proof of a tiling conjecture of Komlós.  Random Structures & Algorithms, 23(2):180–205, 2003.
  * [52] B. Sudakov.  Robustness of graph properties.  Surveys in combinatorics, 440(2017):372, 2017.
  * [53] B. Sudakov and V. H. Vu.  Local resilience of graphs.  Random Structures & Algorithms, 33(4):409–433, 2008.
  * [54] R. Yuster.  Rainbow $H$-factors.  The Electronic Journal of Combinatorics, R13, 2006.

##  Appendix A Proofs of Lemma 4.1 and Lemma 4.3

The proof of Lemma 4.1 can be easily derived by the following result.

######  Lemma A.1.

_[12]_ Let $F$ be a $k$-graph with $b$ vertices. Let $\gamma>0$ and
$0<\varepsilon<\min\\{1/3,\gamma/2\\}$. Then there exists $\xi=\xi(b,\gamma)$
such that the following holds for every sufficiently large $n$. Suppose
$\mathcal{G}$ is an $n$-vertex $k$-graph such that, there exists $V_{0}\subset
V(\mathcal{G})$ of size at most $\varepsilon n$ such that for every $b$-subset
$S$ of $V(\mathcal{G})\setminus V_{0}$, there are at least $\gamma n$ vertex-
disjoint $S$-absorbers, and for every vertex $v\in V(\mathcal{G})$, there are
at least $\gamma n$ copies of $F$ containing $v$, where each pair of these
copies only intersects at vertex $v$. Then $\mathcal{G}$ contains a subset
$A\subseteq V(\mathcal{G})$ of size at most $\gamma n$ such that, for every
subset $R\subseteq V(\mathcal{G})\setminus A$ with $|R|\leq\xi n$ such that
$b$ divides $|A|+|R|$, the $k$-graph $\mathcal{G}[A\cup R]$ contains an
$F$-factor.

###### Proof of Lemma 4.1.

Given $h,t\in\mathbb{N}$, an $h$-vertex graph $H$ and $\gamma>0$, we shall
choose $\frac{1}{n}\ll\xi\ll\frac{1}{t},\frac{1}{h},\gamma$. Let
$(G,\mathcal{F})$ be an incompatibility system with $|V(G)|=n$ such that for
every $S\in{V(G)\choose h}$ there is a family of at least $\gamma n$ vertex-
disjoint $(H,t)$-absorbers. We construct an $h$-graph $\mathcal{G}$ on vertex
set $V(G)$ where $E(\mathcal{G})$ consists of every compatible copy of $H$ in
$(G,\mathcal{F})$. Let $F$ be an $h$-graph with exactly one edge. Then by
definition, every $S\in{V(\mathcal{G})\choose h}$ has at least $\gamma n$
vertex-disjoint $(F,t)$-absorbers. By applying Lemma A.1 on $\mathcal{G}$ with
$b=h$ and $V_{0}=\emptyset$, we obtain a subset $A\subseteq V(\mathcal{G})$ of
size at most $\gamma n$ such that, for every subset $R\subseteq
V(\mathcal{G})\setminus A$ with $|R|\leq\xi n$ such that $h$ divides
$|A|+|R|$, the $k$-graph $\mathcal{G}[A\cup R]$ contains an $F$-factor. Then
$A$ is a desired $\xi$-absorbing set in $(G,\mathcal{F})$. ∎

###### Proof of Lemma 4.3.

For positive integers $h,t$ with $h\geq 3$ and $\beta>0$, let
$G,H,\mathcal{F}$ be given as in the assumption such that $V(G)$ is $(H,\beta
n,t)$-closed. Then for every $h$-set $S\subset V(G)$, we shall greedily
construct as many pairwise disjoint $(H,t)$-absorbers for $S$ as possible. Let
$\mathcal{A}=\\{A_{1},A_{2},\ldots,A_{\ell}\\}$ be a maximal family of vertex-
disjoint $(H,t)$-absorbers as above. Suppose to the contrary that
$\ell<\tfrac{\beta}{h^{3}t}n,$. Then
$|\cup_{\mathcal{A}}A_{i}|\leq\tfrac{\beta}{h}n$ as each such $A_{i}$ has size
at most $h^{2}t$ (see Definition 2.1).

As $V(G)$ is $(H,\beta n,t)$-closed and $|\cup_{\mathcal{A}}A_{i}\cup
S|\leq\beta n$, we can pick a compatible copy of $H$ inside
$V(G)\setminus(\cup_{\mathcal{A}}A_{i}\cup S)$ whose vertex set is denoted by
$T$. Write $S=\\{s_{1},s_{2},\ldots,s_{h}\\}$ and
$T=\\{t_{1},t_{2},\dots,t_{h}\\}$. We now greedily pick a collection
$\\{S_{1},S_{2},\ldots,S_{h}\\}$ of vertex disjoint subsets in
$V(G)\setminus(\bigcup_{\mathcal{A}}A_{i}\cup S\cup T)$ such that each $S_{i}$
is an $H$-connector for $s_{i},t_{i}$ with $|S_{i}|\leq ht-1$. Indeed, since

$\left|\bigcup_{i=1}^{\ell}A_{i}\cup\left(\bigcup_{i=1}^{k^{\prime}}S_{i}\right)\cup
S\cup T\right|\leq\beta n,$

for any $0\leq k^{\prime}\leq h$ (using that $n$ is sufficiently large), it is
possible pick each $S_{i}$ one by one because $s_{i}$ and $t_{i}$ are
$(H,\beta n,t)$-reachable. At this point, it is easy to verify that
$\bigcup_{i=1}^{h}S_{i}\cup T$ is actually an $(H,t)$-absorber for $S$,
contrary to the maximality of $\ell$. ∎

##  Appendix B Proof of Lemma 4.7

We begin with a simple result as follows.

######  Lemma B.1.

Let $s_{1},s_{2}\in\mathbb{N},\beta_{1},\beta_{2}>0$ and $H$ be an $h$-vertex
graph. The following holds for any sufficiently large $n$. Let
$(G,\mathcal{F})$ be an incompatibility system with $|V(G)|=n$, $u,v\in V(G)$
and $Z\subseteq V(G)$ with $|Z|=cn$ for some positive constant $c$. If $u$ is
$(H,\beta_{1}n,s_{1})$-reachable to every vertex in $Z$, while $v$ is
$(H,\beta_{2}n,s_{2})$-reachable to every vertex in $Z$, then $u,v$ are
$(H,\beta_{3}n,s_{1}+s_{2})$-reachable, where
$\beta_{3}n=\min\\{cn-1,\beta_{1}n/2,\beta_{2}n/2\\}$.

###### Proof.

Let $W$ be an arbitrary subset of $G$ with $|W|\leq\beta_{3}n$. Since
$|W|\leq\min\\{cn-1,\beta_{1}n/2\\}$, we can find a vertex $u_{1}\in
Z\setminus W$ and an $H$-connector $S_{1}$ for $u,u_{1}$ in
$V(G)\setminus(W\cup\\{u,u_{1},v\\})$ with $|S_{1}|\leq ht_{1}-1$. Meanwhile,
since $|W|\leq\beta_{2}n/2$, we can also find an $H$-connector $S_{2}$ for
$u_{1},v$ in $V(G)\setminus(W\cup\\{u,u_{1},v\\}\cup S_{1})$ with $|S_{2}|\leq
ht_{2}-1$. Hence, $u,v$ are $(H,\beta_{3}n,t_{1}+t_{2})$-reachable as both
$G[S_{1}\cup S_{2}\cup\\{u_{1},u\\}]$ and $G[S_{1}\cup
S_{2}\cup\\{u_{1},v\\}]$ contain compatible $H$-factors. ∎

###### Proof of Lemma 4.7.

Write $r_{0}=\lceil 1/\gamma_{1}\rceil+1$, $t_{j}=2^{r_{0}+1-j}$ for each
$j\in[r_{0}+1]$ and choose constants
$\frac{1}{n}\ll\lambda_{1}\ll\lambda_{2}\ll\lambda_{3}\cdots\ll\lambda_{r_{0}+1}=\beta_{1},\gamma_{1},\frac{1}{r_{0}}$.
Let $(G,\mathcal{F})$ be an incompatibility system with $|G|=n$ such that
every vertex in $V(G)$ is $(H,\beta_{1}n,1)$-reachable to at least
$\gamma_{1}n$ other vertices.

Assume that there are two vertices that are not
$(H,\lambda_{2}n,t_{2})$-reachable, as otherwise we just output
$\mathcal{P}=\\{V(G)\\}$ as the desired partition. Observe also that every set
of $r_{0}$ vertices must contain two vertices that are
$(H,\lambda_{r_{0}}n,t_{r_{0}})$-reachable to each other. Indeed, by the
inclusion-exclusion principle we obtain a pair of vertices, say $u,v$, which
are $(H,\beta_{1}n,1)$-reachable to a set of at least $\delta^{\prime}n$
vertices for some $\delta^{\prime}\geq\gamma_{1}/\binom{r_{0}}{2}$. Thus, by
Lemma B.1 with $s_{1}=s_{2}=1$, we deduce that $u$ and $v$ are
$(H,\lambda_{r_{0}}n,t_{r_{0}})$-reachable as
$\lambda_{r_{0}}\ll\beta_{1},\gamma_{1},\frac{1}{r_{0}}$ and $t_{r_{0}}=2$.

Let $d$ be the largest integer such that there are $d$ vertices
$v_{1},\dots,v_{d}$ in $G$ which are pairwise _not_
$(H,\lambda_{d}n,t_{d})$-reachable. Note that $d$ exists and $2\leq d\leq
r_{0}-1$. Indeed, we assumed above that there are $2$ vertices that are not
$(H,\lambda_{2}n,t_{2})$-reachable and if $d=r_{0}$, then there would be
$r_{0}$ vertices in $G$ which are pairwise not
$(H,\lambda_{r_{0}}n,t_{r_{0}})$-reachable, contrary to the observation above.
Let $S=\\{v_{1},\dots,v_{d}\\}$. Note that $v_{1},\dots,v_{d}$ are also
pairwise not $(H,\lambda_{d+1}n,t_{d+1})$-reachable.

For a vertex $v$ and every $j\in[r_{0}+1]$, we write $\tilde{N}_{j}(v)$ for
the set of vertices which are $(H,\lambda_{j}n,t_{j})$-reachable to $v$. For
the sets $\tilde{N}_{d+1}(v_{i})$, $i\in[d]$, we conclude that

(1)

any vertex $v\in V(G)\setminus\\{v_{1},\dots,v_{d}\\}$ must be in
$\tilde{N}_{d+1}(v_{i})$ for some $i\in[d]$. Otherwise, $v,v_{1},\dots,v_{d}$
are pairwise not $(H,\lambda_{d+1}n,t_{d+1})$-reachable, contradicting the
maximality of $d$.

(2)

$|\tilde{N}_{d+1}(v_{i})\cap\tilde{N}_{d+1}(v_{j})|<\lambda_{d+1}n$ for any
distinct $i,j\in[d]$. Otherwise Lemma B.1 applied with $s_{1}=s_{2}=t_{d+1}$
implies that $v_{i},v_{j}$ are $(H,\lambda_{d}n,t_{d})$-reachable to each
other, a contradiction to the choice of vertices $v_{i},i\in[d]$ (using that
$\lambda_{d}\ll\lambda_{d+1}$ and $2t_{d+1}=t_{d}$).

For $i\in[d]$, let

$U_{i}=(\tilde{N}_{d+1}(v_{i})\cup\\{v_{i}\\})\setminus\bigcup_{j\not=i}\tilde{N}_{d+1}(v_{j}).$

Then we claim that each $U_{i}$ is $(H,\lambda_{d+1}n,t_{d+1})$-closed. Indeed
otherwise, there exist $u_{1},u_{2}\in U_{i}$ that are not
$(H,\lambda_{d+1}n,t_{d+1})$-reachable to each other. Then
$\\{u_{1},u_{2}\\}\cup\\{v_{1},\dots,v_{d}\\}\setminus\\{v_{i}\\}$ contradicts
the maximality of $d$.

Let $U_{0}=V(G)\setminus(U_{1}\cup\dots\cup U_{d})$. We have
$|U_{0}|<d^{2}\lambda_{d+1}n$ due to (2) above. In order to obtain the desired
reachability partition, we now drop every vertex of $U_{0}$ back into some
$U_{i}$ for $i\in[d]$ as follows. Since each $v\in U_{0}$ is
$(H,\beta_{1}n,1)$-reachable (i.e.
$(H,\lambda_{r_{0}+1}n,t_{r_{0}+1})$-reachable) to at least $\gamma_{1}n$
vertices, it follows from the fact
$\lambda_{d+1}\ll\gamma_{1},\frac{1}{r_{0}}$ that

$|\tilde{N}_{r_{0}+1}(v)\setminus
U_{0}|\geq\gamma_{1}n-|U_{0}|\geq\gamma_{1}n-d^{2}\lambda_{d+1}n>d\lambda_{d+1}n.$

Therefore by the pigeonhole principle there exists some $i\in[d]$ such that
$v$ is $(H,\lambda_{r_{0}+1}n,t_{r_{0}+1})$-reachable to at least
$\lambda_{d+1}n+1$ vertices in $U_{i}$. Lemma B.1 (using that
$\lambda_{d}\ll\lambda_{d+1}\ll\lambda_{r_{0}+1}$) implies that $v$ is
$(H,\lambda_{d}n,t_{d})$-reachable to every vertex in $U_{i}$.

Recall that $2\leq d\leq r_{0}-1$. Now partition $U_{0}$ as $U_{0}=\cup_{i\in
d}R_{i}$ where for each $i\in[d]$, $R_{i}$ denotes a set of vertices $v\in
U_{0}$ that are $(H,\lambda_{d}n,t_{d})$-reachable to every vertex in $U_{i}$.
Again by Lemma B.1 with $s_{1}=s_{2}=t_{d}$, for every $i\in[d]$, every two
vertices in $R_{i}$ (if any) are $(H,\lambda_{d-1}n,t_{d-1})$-reachable to
each other. Let $\mathcal{P}=\\{V_{1},\dots,V_{d}\\}$ be the final partition
by setting $V_{i}=R_{i}\cup U_{i}$. Then each $V_{i}$ is
$(H,\lambda_{d-1}n,t_{d-1})$-closed. Also, for each $i\in[d]$, it holds that

$|V_{i}|\geq|U_{i}|\geq|\tilde{N}_{d+1}(v_{i})|-d^{2}\lambda_{d+1}n\geq|\tilde{N}_{r_{0}+1}(v_{i})|-\tfrac{\gamma_{1}}{2}n\geq\tfrac{\gamma_{1}}{2}n.$

This completes the proof by taking $\beta_{2}=\lambda_{d-1}$ and $t=t_{d-1}$.
∎