# Dirac-type results for tilings and coverings in ordered graphs

Andrea Freschi  and  Andrew Treglown

###### Abstract.

A recent paper of Balogh, Li and Treglown [3] initiated the study of Dirac-
type problems for ordered graphs. In this paper we prove a number of results
in this area. In particular, we determine asymptotically the minimum degree
threshold for forcing

  * (i)

a perfect $H$-tiling in an ordered graph, for any fixed ordered graph $H$ of
interval chromatic number at least $3$;

  * (ii)

an $H$-tiling in an ordered graph $G$ covering a fixed proportion of the
vertices of $G$ (for any fixed ordered graph $H$);

  * (iii)

an $H$-cover in an ordered graph (for any fixed ordered graph $H$).

The first two of these results resolve questions of Balogh, Li and Treglown
whilst (iii) resolves a question of Falgas-Ravry. Note that (i) combined with
a result from [3] completely determines the asymptotic minimum degree
threshold for forcing a perfect $H$-tiling. Additionally, we prove a result
that combined with a theorem of Balogh, Li and Treglown, asymptotically
determines the minimum degree threshold for forcing an almost perfect
$H$-tiling in an ordered graph (for any fixed ordered graph $H$). Our work
therefore provides ordered graph analogues of the seminal tiling theorems of
Kühn and Osthus [Combinatorica 2009] and of Komlós [Combinatorica 2000]. Each
of our results exhibits some curious, and perhaps unexpected, behaviour. Our
solution to (i) makes use of a novel absorbing argument.

AF: School of Mathematics, University of Birmingham, United Kingdom,
<EMAIL_ADDRESS>
AT: School of Mathematics, University of Birmingham, United Kingdom,
<EMAIL_ADDRESS>research supported by EPSRC grant EP/V002279/1.

##  1\. Introduction

In recent years there has been a significant effort to develop both Turán and
Ramsey theories in the setting of _vertex ordered graphs_. A _(vertex) ordered
graph_ or _labelled graph_ $H$ on $h$ vertices is a graph whose vertices have
been labelled with $[h]:=\\{1,\dots,h\\}$. An ordered graph $G$ with vertex
set $[n]$ _contains_ an ordered graph $H$ on $[h]$ if (i) there is an
injection $\phi:[h]\rightarrow[n]$ such that $\phi(i)<\phi(j)$ for all $1\leq
i<j\leq h$ and (ii) $\phi(i)\phi(j)$ is an edge in $G$ whenever $ij$ is an
edge in $H$.

Turán-type problems concern edge density conditions that force a fixed graph
$H$ as a subgraph in a host graph $G$. Whilst the Erdős–Stone–Simonovits
theorem [8, 9] determines, up to a quadratic error term, the number of edges
in the densest $H$-free $n$-vertex graph, there is still active interest in
the Turán problem for bipartite $H$. Indeed, for bipartite $H$ the error term
in the Erdős–Stone–Simonovits theorem is in fact the dominant term, so more
refined results are sought. Similarly, a result of Pach and Tardos [24]
determines asymptotically the number of edges an ordered graph requires to
force a copy of a fixed ordered graph $H$ with so-called interval chromatic
number $\chi_{<}(H)$ at least $3$. Therefore, again there is significant
interest in the ‘bipartite’ case of this problem (i.e., when $\chi_{<}(H)=2$);
see Tardos [28] for a recent survey on such results.

The study of Ramsey theory for ordered graphs has also gained significant
traction. For example, results of Conlon, Fox, Lee and Sudakov [5], and of
Balko, Cibulka, Král and Kynčl [2] demonstrate that there are ordered graphs
$H$ for which the behaviour of the Ramsey number is vastly different to their
underlying unordered graph.

Other than Turán and Ramsey problems, another central branch of extremal graph
theory concerns Dirac-type results; that is, minimum degree conditions that
force fixed (spanning) structures in graphs. In a recent paper, Balogh, Li and
the second author [3] initiated the study of Dirac-type results for ordered
graphs. Their main focus was on _perfect $H$-tilings_, though they also raised
other Dirac-type problems (see [3, Section 8]). In both the ordered and
unordered settings, an _$H$ -tiling_ in a graph $G$ is a collection of vertex-
disjoint copies of $H$ contained in $G$. An $H$-tiling is _perfect_ if it
covers all the vertices of $G$. Perfect $H$-tilings are also often referred to
as _$H$ -factors_, _perfect $H$-packings_ or _perfect $H$-matchings_.
$H$-tilings can be viewed as generalisations of both the notion of a matching
(which corresponds to the case when $H$ is a single edge) and the Turán
problem (i.e., a copy of $H$ in $G$ is simply an $H$-tiling of size one).

Balogh, Li and Treglown [3] raised the following question.

######  Problem 1.1.

[3] Given any ordered graph $H$ and any $n\in\mathbb{N}$ divisible by $|H|$,
determine the smallest integer $\delta_{<}(H,n)$ such that every $n$-vertex
ordered graph $G$ with $\delta(G)\geq\delta_{<}(H,n)$ contains a perfect
$H$-tiling.

The analogous problem in the (unordered) graph setting had been studied since
the 1960s (see, e.g., [1, 6, 13, 17, 20, 21]) and forty-five years later a
complete solution, up to an additive constant term, was obtained via a theorem
of Kühn and Osthus [21]. We will discuss this result further when comparing
this problem with Problem 1.1.

In [3, Theorem 1.9], Balogh, Li and Treglown asymptotically resolved Problem
1.1 for $H$ with $\chi_{<}(H)=2$. Further, they developed approaches to the
absorbing and regularity methods for ordered graphs, including providing
general absorbing and almost perfect tiling lemmas. In this paper we build on
their results to asymptotically resolve Problem 1.1 in all remaining cases
(i.e., for all $H$ with interval chromatic number at least $3$). Our main
result shows that Problem 1.1 does exhibit a somewhat different behaviour when
$\chi_{<}(H)\geq 3$ compared to when $\chi_{<}(H)=2$; we discuss this further
in Section 1.3.

In addition to this result, we also resolve the Dirac-type problems for _$H$
-covers_ in ordered graphs (see Section 1.2) and $H$-tilings covering a fixed
proportion $x$ of the vertices of an ordered graph for $x\in(0,1)$ (see
Section 1.4).

###  1.1. A Dirac-type theorem for perfect $H$-tilings

In this subsection we state Theorem 1.8, which asymptotically resolves Problem
1.1 when $\chi_{<}(H)\geq 3$. This result will depend on several definitions
and parameters which we now introduce.

######  Definition 1.2 (Interval chromatic number).

Given $r\in\mathbb{N}$, an _interval $r$-colouring_ of an ordered graph $H$ is
a partition of the vertex set $[h]$ of $H$ into $r$ intervals so that no two
vertices belonging to the same interval are adjacent in $H$. The interval
chromatic number $\chi_{<}(H)$ of an ordered graph $H$ is the smallest
$r\in\mathbb{N}$ such that there exits an interval $r$-colouring of $H$.

One can think of the interval chromatic number as the natural ordered analogue
of the chromatic number of a graph. Moreover, whilst the
Erdős–Stone–Simonovits theorem [8, 9] asserts that $1-1/(\chi(H)-1)+o(1)$ is
the edge density threshold for ensuring a copy of a graph $H$ in $G$, the
_Erdős–Stone–Simonovits theorem for ordered graphs_ due to Pach and Tardos
[24] asserts the corresponding threshold in the ordered graph setting is
$1-1/(\chi_{<}(H)-1)+o(1)$.

The next definition is the relevant parameter for studying _almost_ perfect
$H$-tilings in graphs.

######  Definition 1.3 (Critical chromatic number).

The critical chromatic number $\chi_{cr}(F)$ of an unordered graph $F$ is
defined as

$\chi_{cr}(F):=(\chi(F)-1)\frac{|F|}{|F|-\sigma(F)},$

where $\sigma(F)$ denotes the size of the smallest possible colour class in
any $\chi(F)$-colouring of $F$.

Note that $\chi(H)-1<\chi_{cr}(H)\leq\chi(H)$ for all graphs $H$, and
$\chi_{cr}(H)=\chi(H)$ precisely when every $\chi(H)$-colouring of $H$ has
colour classes of equal size.

We informally refer to an $H$-tiling in an $n$-vertex (ordered) graph $G$ as
an _almost perfect $H$-tiling_ if it covers all but at most $o(n)$ vertices of
$G$. Komlós [16] proved that $(1-1/\chi_{cr}(H))n$ is the minimum degree
threshold for forcing an almost perfect $H$-tiling in an $n$-vertex graph $G$.
In fact, it was later shown [26] that such graphs $G$ contain $H$-tilings
covering all but a constant number of the vertices in $G$. In the setting of
ordered graphs, a related parameter $\chi^{*}_{cr}(H)$ turns out to be the
relevant parameter for forcing an almost perfect $H$-tiling. To introduce this
parameter we need the following definitions.

For two subsets $X,Y$ of $[n]$, we write $X<Y$ if $x<y$ for all $x\in X$ and
$y\in Y$. Let $B$ be a complete $k$-partite unordered graph with parts
$U_{1},\ldots,U_{k}$, and $\sigma$ be a permutation of the set $[k]$. An
interval labelling of $B$ with respect to $\sigma$ is a bijection
$\phi:V(B)\rightarrow[|B|]$ such that $\phi(U_{i})<\phi(U_{j})$ if
$\sigma(i)<\sigma(j)$; that is,

$\phi(U_{\sigma^{-1}(1)})<\cdots<\phi(U_{\sigma^{-1}(k)}).$

For brevity, we will usually drop $\phi$ and just write
$U_{\sigma^{-1}(1)}<\cdots<U_{\sigma^{-1}(k)}.$ Given $t\in\mathbb{N}$, write
$B(t)$ for the _blow-up of $B$_ with vertex set $\bigcup_{x\in V(B)}V_{x}$,
where the $V_{x}$’s are sets of $t$ independent vertices; so there are all
possible edges between $V_{x}$ and $V_{y}$ in $B(t)$ if $xy\in E(B)$. Let
$(B(t),\phi)$ be the ordered graph obtained from $B(t)$ by equipping $V(B(t))$
with a vertex ordering, satisfying $V_{x}<V_{y}$ for every $x,y\in V(B)$ with
$\phi(x)<\phi(y)$. We refer to $(B(t),\phi)$ as an ordered blow-up of $B$.

######  Definition 1.4 (Bottlegraph).

For an ordered graph $H$, we say that a complete $k$-partite unordered graph
$B$ is a bottlegraph of $H$, if for every permutation $\sigma$ of $[k]$ and
every interval labelling $\phi$ of $B$ with respect to $\sigma$, there exists
a constant $t=t(B,H,\phi)$ such that the ordered blow-up $(B(t),\phi)$
contains a perfect $H$-tiling. We say that $B$ is a simple bottlegraph of $H$
if for any choice of $\sigma$ and $\phi$ we can take $t=1$.

Note that in Definition 1.4 we did not impose any restriction on the size of
the parts of a bottlegraph. However, as we will see in Proposition 5.1 below,
it suffices to consider bottlegraphs $B^{\prime}$ where all parts are of the
same size except for perhaps one smaller part. More precisely, given any
bottlegraph $B$ of $H$, there is another bottlegraph $B^{\prime}$ with this
structure such that $\chi_{cr}(B^{\prime})=\chi_{cr}(B)$. This bottle-like
structure is where the name bottlegraph is derived, and was first use by
Komlós [16] in the setting of unordered graphs.

######  Definition 1.5 (Ordered critical chromatic number).

The ordered critical chromatic number $\chi^{*}_{cr}(F)$ of an ordered graph
$F$ is defined as

$\chi_{cr}^{*}(F):=\inf\\{\chi_{cr}(B):B\text{ is a bottlegraph of }F\\}.$

We say a bottlegraph $B$ of $F$ is _optimal_ if
$\chi_{cr}(B)=\chi_{cr}^{*}(F)$.

Notice that $\chi_{<}(H)-1\leq\chi_{cr}^{*}(H)$ for all ordered graphs $H$ as
each bottlegraph $B$ of $H$ must have chromatic number at least $\chi_{<}(H)$
and so $\chi_{<}(H)-1<\chi_{cr}(B)$. In fact, Proposition 2.6 in Section 2
yields a stronger lower bound on $\chi_{cr}^{*}(H)$. On the other hand, (in
contrast to $\chi_{cr}(F)$ for unordered graphs $F$) we will also see examples
of ordered graphs where $\chi_{cr}^{*}(H)$ is much larger than $\chi_{<}(H)$.
Note though that $\chi_{cr}^{*}(H)\leq h$ for any ordered graph $H$ on $[h]$
as $K_{h}$ is a bottlegraph of $H$. In fact, this upper bound is attained when
$H$ is such that $1$ and $2$ are adjacent or $h-1$ and $h$ are adjacent; this
is an immediate consequence of Proposition 11.1 below. To aid the reader’s
intuition, in Section 3.3 we give examples of ordered graphs $H$ where we
compute $\chi^{*}_{cr}(H)$. Various bounds on $\chi^{*}_{cr}(H)$ are given in
Section 11.

The next result, a simple corollary of [3, Theorem 4.3], shows that
$\chi^{*}_{cr}(H)$ is a relevant parameter for forcing an almost perfect
$H$-tiling in an ordered graph.111The reader may not immediately see why
Theorem 1.6 is a corollary of Theorem 4.3 from [3] as there is an error term
in the minimum degree condition in the latter theorem. However, a standard
trick (see, e.g., the proof of Corollary 6.6 in [7]) always allows one to omit
an error term in a minimum degree condition that forces an almost perfect
$H$-tiling.

######  Theorem 1.6 (Balogh, Li and Treglown [3]).

Let $H$ be an ordered graph. Then for every $\eta>0$, there exists an integer
$n_{0}=n_{0}(H,\eta)$ so that every ordered graph $G$ on $n\geq n_{0}$
vertices with

$\delta(G)\geq\left(1-\frac{1}{\chi^{*}_{cr}(H)}\right)n$

contains an $H$-tiling covering all but at most $\eta n$ vertices.

At first sight it is not clear if the minimum degree threshold in Theorem 1.6
is best possible. However, Theorem 12.1 in Section 12 shows that Theorem 1.6
is best possible in the sense that one cannot replace the
$1-{1}/{\chi^{*}_{cr}(H)}$ term in the minimum degree condition with any other
fixed constant term $a<1-{1}/{\chi^{*}_{cr}(H)}$. Thus, Theorem 12.1 and
Theorem 1.6 provide an analogue of Komlós’ theorem in the ordered setting.

Unusually, in the proof of Theorem 12.1, for most ordered graphs $H$ we do not
simply produce an explicit extremal example. Indeed, if one has not explicitly
computed the value of $\chi^{*}_{cr}(H)$ and the ‘reason’ why it takes this
value, then it seems difficult to produce such an explicit extremal example.
Instead, the proof splits into a few cases and uses various tools and results
that we introduce in the paper.

At this point the reader may wonder if the conclusion of Theorem 1.6 can be
strengthened to ensure a _perfect_ $H$-tiling. For some ordered graphs $H$
this is possible. However, for other ordered graphs one will require a
significantly higher minimum degree condition. The following definition is the
critical concept for articulating this dichotomy for $H$ with $\chi_{<}(H)\geq
3$.

######  Definition 1.7 (Local barrier).

Let $H$ be an ordered graph on $[h]$ with $r:=\chi_{<}(H)\geq 2$. We say that
$H$ has a _local barrier_ if for some fixed $i\neq j\in[r+1]$ the following
condition holds. Given any interval $(r+1)$-colouring of $H$ with colour
classes $V_{1}<\cdots<V_{r+1}$ such that $V_{i}=\\{v\\}$ is a singleton class,
there is at least one edge between $v$ and $V_{j}$ in $H$.

Note that in this definition we may have that a colour class $V_{k}$ is empty.
If $H$ is the ordered complete graph on $r$ vertices then $H$ does not have a
local barrier; it is also easy to check that $\chi^{*}_{cr}(H)=\chi_{<}(H)=r$.
Given $r\geq 2,$ let $H^{\prime}$ be any complete $r$-partite (unordered)
graph with at least $2$ vertices in each colour class. Let $H$ be any ordered
graph obtained from $H^{\prime}$ by assigning an interval labelling to
$H^{\prime}$; so $\chi_{<}(H)=r$. Then one can check that $H$ has a local
barrier with parameters $i=1$ and $j=r+1$ as in Definition 1.7.

We are now able to state our main result which resolves Problem 1.1 for all
ordered graphs $H$ with $\chi_{<}(H)\geq 3$.

######  Theorem 1.8.

Let $H$ be an ordered graph with $\chi_{<}(H)\geq 3$. Given any $\eta>0$,
there exists an integer $n_{0}=n_{0}(H,\eta)$ so that if $n\geq n_{0}$ and
$|H|$ divides $n$ then

  * (i)

$\left(1-\frac{1}{\chi^{*}_{cr}(H)}\right)n\leq\delta_{<}(H,n)\leq\left(1-\frac{1}{\chi^{*}_{cr}(H)}+\eta\right)n$
if $\chi^{*}_{cr}(H)\geq\chi_{<}(H)$;

  * (ii)

$\left(1-\frac{1}{\chi_{<}(H)}\right)n<\delta_{<}(H,n)\leq\left(1-\frac{1}{\chi_{<}(H)}+\eta\right)n$
if $\chi^{*}_{cr}(H)<\chi_{<}(H)$ and $H$ has a local barrier;

  * (iii)

$\left(1-\frac{1}{\chi^{*}_{cr}(H)}\right)n\leq\delta_{<}(H,n)\leq\left(1-\frac{1}{\chi^{*}_{cr}(H)}+\eta\right)n$
if $\chi^{*}_{cr}(H)<\chi_{<}(H)$ and $H$ has no local barrier.

Therefore Problem 1.1 is now asymptotically resolved. The reader might find it
hard to see why the value of $\delta_{<}(H,n)$ behaves as in Theorem 1.8, and
indeed, it took the authors quite some time to discover the correct behaviour
of this problem. In Section 1.3 we give further intuition on this result. In
Section 3 we give examples of $H$ in each case (i)–(iii) of the theorem. In
Section 2 we give the extremal constructions for Theorem 1.8. In particular,
in cases (i) and (iii) the extremal examples are ‘bottlegraphs’ – complete
multipartite ordered graphs where each part has the same size except at most
one smaller part; in Section 11 we explicitly compute the value of
$\chi^{*}_{cr}(H)$ for a range of $H$, and thus the minimum degree threshold
in Theorem 1.8 also. The explanation for why these extremal ‘bottlegraphs’ do
not have perfect $H$-tilings revolve around ‘space barrier’ constraints,
(i.e., one runs out of space in some subset of vertices in the extremal
bottlegraph).222See [15] for a discussion on space barriers. However, the
‘reason’ for obtaining a space barrier can be somewhat involved (and unlike
any other space barrier extremal example we have ever seen before); we discuss
this in Section 3.1.

The proof of Theorem 1.8 applies an absorbing theorem from [3, Theorem 4.1]
and Theorem 1.6 above. The main novelty is to prove an absorbing theorem for
ordered graphs $H$ as in Theorem 1.8(iii). Whilst our argument makes use of a
lemma of Lo and Markström [23], and seems rather natural, it is different to
any absorbing proof we have previously seen (in particular, we do not use
_local-global absorbing_ as in [3]). See Section 9 for an overview of our
absorbing strategy.

###  1.2. A Dirac-type theorem for vertex covers

Given (ordered) graphs $H$ and $G$, we say that $G$ has an _$H$ -cover_ if
every vertex in $G$ lies in a copy of $H$. Note that the notion of an
$H$-cover is an ‘intermediate’ between seeking a single copy of $H$ and a
perfect $H$-tiling; in particular, a perfect $H$-tiling in $G$ is itself an
$H$-cover. Given any $n\in\mathbb{N}$ and any (ordered) graph $H$, let
$\delta_{\text{cov}}(H,n)$ denote the smallest integer $k$ such that every
$n$-vertex (ordered) graph $G$ with $\delta(G)\geq k$ contains an $H$-cover.
As noted in [22], an easy application of Szemerédi’s regularity lemma
asymptotically determines $\delta_{\text{cov}}(H,n)$ for all graphs $H$.

######  Proposition 1.9.

[22, Proposition 6] For every graph $H$ and every $\eta>0$, there exists an
integer $n_{0}=n_{0}(H,\eta)$ so that if $n\geq n_{0}$ then

$\left(1-\frac{1}{\chi(H)-1}\right)n-1\leq\delta_{\text{cov}}(H,n)\leq\left(1-\frac{1}{\chi(H)-1}+\eta\right)n.$

Proposition 1.9 implies that, asymptotically, the minimum degree threshold for
ensuring an $H$-cover in a graph $G$ is the same as the minimum degree
threshold for ensuring a _single copy_ of $H$ in $G$. In [22, Theorem 5],
Kühn, Osthus and Treglown asymptotically determined the Ore-type degree
condition that forces an $H$-cover for any fixed graph $H$. There has also
been several recent papers concerning minimum $\ell$-degree conditions that
force $H$-covers in $k$-uniform hypergraphs; see, e.g., [11, 12, 14].

Falgas-Ravry [10] raised the question of determining
$\delta_{\text{cov}}(H,n)$ for all ordered graphs $H$. Our next result
asymptotically answers this question.

######  Theorem 1.10.

Let $H$ be an ordered graph and $\eta>0$. Then there exists an integer
$n_{0}=n_{0}(H,\eta)$ so that if $n\geq n_{0}$ then

  * (i)

$\left(1-\frac{1}{\chi_{<}(H)-1}\right)n<\delta_{\text{cov}}(H,n)\leq\left(1-\frac{1}{\chi_{<}(H)-1}+\eta\right)n$
if $H$ has no local barrier;

  * (ii)

$\left(1-\frac{1}{\chi_{<}(H)}\right)n<\delta_{\text{cov}}(H,n)\leq\left(1-\frac{1}{\chi_{<}(H)}+\eta\right)n$
if $H$ has a local barrier.

Theorem 1.10 is a direct consequence of some of the auxiliary results we use
in the proof of Theorem 1.8. Note that the behaviour of the threshold in
Theorem 1.10 is perhaps unexpected. Indeed, unlike in the unordered setting,
Theorem 1.10 and the Erdős–Stone–Simonovits theorem for ordered graphs imply
that the asymptotic minimum degree thresholds for forcing a copy of $H$ and an
$H$-cover are different if $H$ has a local barrier.

Furthermore, a key moral of the Erdős–Stone–Simonovits theorem (and
Proposition 1.9) is that once a graph $G$ is dense enough (or has large enough
minimum degree) so as to ensure a copy of $K_{r}$ (or a $K_{r}$-cover) then
$G$ must contain every fixed graph $H$ (or an $H$-cover) for every $H$ of
chromatic number $r$. An intuition for this comes from Szemerédi’s regularity
lemma. However, the analogous moral is not true for $H$-covers in ordered
graphs. Indeed, if $H$ is an ordered complete graph on $r$ vertices (so
$\chi_{<}(H)=r$ and $H$ has no local barrier) then Theorem 1.10 tells us the
minimum degree threshold for forcing an $H$-cover in an $n$-vertex ordered
graph is $(1-\frac{1}{r-1}+o(1))n$ whilst the corresponding threshold for any
‘blow-up’ $H^{\prime}$ of $H$ (so $\chi_{<}(H^{\prime})=\chi_{<}(H)=r$ and $H$
has a local barrier) is significantly higher, namely $(1-\frac{1}{r}+o(1))n$.
This should hint to the reader that the regularity method behaves differently
in the ordered setting; in particular, if $H$ has a local barrier this
provides an obstruction when applying the regularity lemma. More discussion on
the regularity method for ordered graphs can be found in [3, Section 3.1].

###  1.3. Intuition behind the threshold in Theorem 1.8

In this subsection we build up further intuition behind the threshold in
Theorem 1.8. For this it will be useful to first take a step back and consider
perfect $H$-tilings in unordered graphs. In this setting the Dirac-type
threshold is governed by two factors:

  * $(C1)$

The minimum degree needs to be large enough to force an almost perfect
$H$-tiling.

  * $(C2)$

The minimum degree must be large enough to prevent ‘divisibility’ barriers
within the host graph that constrain us from turning an almost perfect
$H$-tiling into a perfect $H$-tiling.

This is made precise by the following theorem of Kühn and Osthus [21].

######  Theorem 1.11 (Kühn and Osthus [21]).

Let $\delta(H,n)$ denote the smallest integer $k$ such that every graph $G$
whose order $n$ is divisible by $|H|$ and with $\delta(G)\geq k$ contains a
perfect $H$-tiling. For every unordered graph $H$,

$\delta(H,n)=\left(1-\frac{1}{\chi^{*}(H)}\right)n+O(1),$

where $\chi^{*}(H):=\chi_{cr}(H)$ if $\text{hcf}(H)=1$ and
$\chi^{*}(H):=\chi(H)$ otherwise.

Recall that every graph $H$ satisfies $\chi_{cr}(H)\leq\chi(H)$. So by Komlós’
aforementioned almost perfect tiling theorem [16], the minimum degree
condition in Theorem 1.11 is enough to ensure $(C1)$ holds. Meanwhile those
graphs $H$ with $\text{hcf}(H)=1$ are precisely the graphs for which, at the
almost perfect tiling threshold, $(C2)$ is satisfied. Furthermore, for graphs
$H$ with $\text{hcf}(H)\neq 1$, $(C2)$ is only guaranteed to be satisfied once
the $n$-vertex host graph has minimum degree around $(1-1/\chi(H))n$.

We do not state the precise definition of $\text{hcf}(H)=1$ here; see [21,
Section 1.2]. However, the following example is instructive. Let $H$ be any
connected bipartite graph and let $n\in\mathbb{N}$ be divisible by $|H|$.
Consider the $n$-vertex graph $G$ that consists of two disjoint cliques whose
sizes are as equal as possible so that neither is divisible by $|H|$. Then
whilst $G$ contains an almost perfect $H$-tiling, the divisibility constraint
on the clique sizes prevents a perfect $H$-tiling. Thus all such $H$ are
examples of graphs with $\text{hcf}(H)\neq 1$. In particular,
$\delta(G)=n/2-O(1)=(1-1/\chi(H))n-O(1)$, so $G$ is an extremal example for
Theorem 1.11 in this case.

As mentioned earlier, another necessary condition for a Dirac-type threshold
for perfect $H$-tilings is the following:

  * $(C3)$

The minimum degree needs to be large enough to force an $H$-cover.

Condition $(C3)$, however, does not factor into the statement of Theorem 1.11
as Proposition 1.9 shows that one can ensure an $H$-cover ‘earlier’ than an
almost perfect $H$-tiling (recall that $\chi(H)-1<\chi_{cr}(H)$).

Interestingly, the opposite is true in the ordered graph setting when $H$ has
a local barrier and $\chi_{<}(H)\geq 3$ is such that
$\chi_{<}(H)>\chi_{cr}^{*}(H)$. Indeed, in this case, Theorem 1.8(ii)
essentially states that the $H$-cover condition is the ‘last’ of conditions
$(C1)$–$(C3)$ to be satisfied. In particular, Extremal Example 1 in Section 2
shows that for every $H$ satisfying Definition 1.7, there are $n$-vertex
ordered graphs with $\delta(G)>(1-1/\chi_{<}(H))n-1$ for which a certain
vertex does not lie in a copy of $H$.

In all other cases when $\chi_{<}(H)\geq 3$, Theorem 1.8 essentially states
that the almost perfect tiling condition is the ‘last’ of conditions
$(C1)$–$(C3)$ to be satisfied. Therefore, surprisingly (at least to the
authors!), divisibility barriers play no role in Problem 1.1 for $H$ with
$\chi_{<}(H)\geq 3$. In contrast, Theorem 1.9 in [3] shows that in the case
when $\chi_{<}(H)=2$, each of $(C1)$, $(C2)$ and $(C3)$ can be the condition
that governs the Dirac-type threshold for perfect $H$-tiling, depending on the
choice of $H$.

###  1.4. A Dirac-type theorem for $H$-tilings

In addition to determining the Dirac-type threshold for almost perfect tilings
in unordered graphs, Komlós [16] provided a best-possible minimum degree
condition for forcing an $H$-tiling covering a certain proportion of the
vertices in a graph $G$.

######  Definition 1.12 ($(x,H)$-tilings).

Let $G$ and $H$ be (ordered) graphs and $x\in[0,1]$. An _$(x,H)$ -tiling in
$G$_ is an $H$-tiling covering at least $x|G|$ vertices. So a $(1,H)$-tiling
is simply a perfect $H$-tiling.

######  Theorem 1.13 (Komlós [16]).

Let $H$ be a graph and $x\in(0,1)$. Define

$g(x,H):=\left(1-\frac{1}{\chi(H)-1}\right)(1-x)+\left(1-\frac{1}{\chi_{cr}(H)}\right)x.$

Given any $\eta>0$, there exists some $n_{0}=n_{0}(x,H,\eta)\in\mathbb{N}$
such that if $G$ is a graph on $n$ vertices where $n\geq n_{0}$ and
$\delta(G)\geq g(x,H)\cdot n$ then there exists an $(x-\eta,H)$-tiling in $G$.

Note that the minimum degree condition in Theorem 1.13 is best possible in the
sense that given any fixed $H$ and $x\in(0,1)$, one cannot replace $g(x,H)$
with any fixed $g^{\prime}(x,H)<g(x,H)$ (see [16, Theorem 7] for a proof of
this).

The function $g(x,H)$ is quite well-behaved. Indeed, for fixed $H$, $g(x,H)$
grows linearly in $x$. Note that $g(0,H)\cdot n$ and $g(1,H)\cdot n$ are the
asymptotic minimum degree thresholds for ensuring an $n$-vertex graph contains
a copy of $H$ and an almost perfect $H$-tiling respectively. From this
prospective, the function $g(x,H)$ can be viewed as a linear interpolation of
these two thresholds.

The question of obtaining an ordered graph analogue of Theorem 1.13 was raised
in [3, Question 8.2]. We provide an answer to this problem; for this we
require the following definitions.

######  Definition 1.14 ($x$-bottlegraphs).

Let $H$ be an ordered graph and $x\in(0,1]$. An unordered graph $B$ is an _$x$
-bottlegraph of $H$_ if it satisfies the following properties:

  * (i)

$B$ is a complete $k$-partite graph with parts $U_{1},U_{2},\dots,U_{k}$, for
some $k\in\mathbb{N}$.

  * (ii)

There exists some $m\in\mathbb{N}$ such that $|U_{1}|\leq m$ and $|U_{i}|=m$
for every $i>1$.

  * (iii)

Given any permutation $\sigma$ of $[k]$ and any interval labelling of $B$ with
respect to $\sigma$, the resulting ordered graph contains an $(x,H)$-tiling.

######  Definition 1.15.

Let $H$ be an ordered graph and $x\in(0,1]$. We define $\chi_{cr}^{*}(x,H)$ as

$\chi_{cr}^{*}(x,H):=\inf\\{\chi_{cr}(B)\,:\,B\,\text{is an $x$-bottlegraph of
$H$}\\}.$

Given any ordered graph $H$, if $B$ is an $x$-bottlegraph of $H$ then
$\chi(B)\geq\chi_{<}(H)$. This implies that $\chi_{cr}(B)>\chi_{<}(H)-1$ and
so

(1) $\displaystyle\chi^{*}_{cr}(x,H)\geq\chi_{<}(H)-1.$

An application of Theorem 1.13 together with a tool from [3, Lemma 6.2] yields
the following minimum degree condition for the existence of $(x,H)$-tilings in
ordered graphs.

######  Theorem 1.16.

Let $H$ be an ordered graph, $x\in(0,1)$ and define

$f(x,H):=\left(1-\frac{1}{\chi_{cr}^{*}(x,H)}\right).$

Given any $\eta>0$, there exists some $n_{0}=n_{0}(x,H,\eta)\in\mathbb{N}$
such that if $G$ is an ordered graph on $n$ vertices with $n\geq n_{0}$ and
$\delta(G)\geq(f(x,H)+\eta)n$ then $G$ contains an $(x,H)$-tiling.

The minimum degree condition in Theorem 1.16 is best possible in the following
sense. Let $H$ and $x\in(0,1)$ be fixed. Given any
$0<a<1-1/\chi_{cr}^{*}(x,H)$, and any sufficiently large $n\in\mathbb{N}$,
consider any $n$-vertex graph $B$ that satisfies (i) and (ii) of Definition
1.14 for some choice of $k,m\in\mathbb{N}$ and where

$an<\delta(B)=n-m=\left(1-\frac{1}{\chi_{cr}(B)}\right)n<f(x,H)\cdot n.$

So $\chi_{cr}(B)<\chi_{cr}^{*}(x,H)$. (Note such a graph $B$ exists for any
choice of $0<a<1-1/\chi_{cr}^{*}(x,H)$.) Then by definition of
$\chi_{cr}^{*}(x,H)$ there is a permutation $\sigma$ of $[k]$ and an interval
labelling $\phi$ of $B$ with respect to $\sigma$, such the resulting ordered
graph $(B,\phi)$ does not contain an $(x,H)$-tiling.

A draw-back of Theorem 1.16 is that it seems hard to compute
$\chi_{cr}^{*}(x,H)$ in general. However, in Section 14 we describe the
behaviour of the function $f(x,H)$ for some fixed ordered graphs $H$. In
particular, akin to Theorem 1.13, if $H$ has $\chi_{<}(H)=2$ then $f(x,H)$ is
linear in $x$. Perhaps surprisingly though, there are ordered graphs where
$f(x,H)$ is only piecewise linear. We also compute $f(x,H)$ for every ordered
graph $H$ and every $x$ that is not too big.

###  1.5. Organisation of the paper

The paper is organised as follows. In Section 2 we give the extremal
constructions for Theorems 1.8 and 1.10. In Section 3 we give some examples of
ordered graphs $H$ that fall into each of the three cases of Theorem 1.8. In
Section 4 we state a new absorbing theorem (Theorem 4.2) and an absorbing
theorem from [3] and combine them with Theorem 1.6 to prove Theorem 1.8. The
subsequent sections therefore build up tools for the proof of Theorem 4.2: in
Section 5 we state a couple of useful properties of bottlegraphs; in Section 6
we introduce Szemerédi’s regularity lemma and related useful results; some
tools for absorbing are given in Section 7; Section 8 contains several results
which give flexibility in how one can interval colour certain ordered graphs
$H$.

In Section 9 we give a sketch of the proof of Theorem 4.2 before proving it
and Theorem 1.10 in Section 10. In Section 11 we give general upper and lower
bounds on $\chi^{*}_{cr}(H)$ and also compute $\chi^{*}_{cr}(H)$ for a few
general classes of ordered graphs $H$.

In Section 12 we prove that the minimum degree condition in Theorem 1.6 is
best possible. The proof of Theorem 1.16 is given in Section 13; in the
subsequent section we describe the behaviour of the function $f(x,H)$ for some
choices of $H$. We conclude the paper with some open problems in Section 15.

###  1.6. Notation

Given $n\in\mathbb{N}$, let $[n]:=\\{1,\ldots,n\\}$. A _nearly balanced
interval partition_ of $[n]$ is a partition of $[n]$ into intervals
$W_{1}<\dots<W_{t}$ where $||W_{i}|-|W_{j}||\leq 1$ for every $1\leq i,j\leq
t$. Similarly, a $t$-partite graph with vertex classes $V_{1},\ldots,V_{t}$ is
nearly balanced if $||V_{i}|-|V_{j}||\leq 1$ for every $1\leq i,j\leq t$.

If $G$ is an (ordered) graph, $|G|$ denotes the size of its vertex set, and
$e(G)$ denotes the number of edges in $G$. Given $A\subseteq V(G)$, the
_induced subgraph $G[A]$_ is the subgraph of $G$ whose vertex set is $A$ and
whose edge set consists of all of the edges of $G$ with both endpoints in $A$.
We define $G\setminus A:=G[V(G)\setminus A]$. For two disjoint subsets
$A,B\subseteq V(G)$, the _induced bipartite subgraph $G[A,B]$_ is the subgraph
of $G$ whose vertex set is $A\cup B$ and whose edge set consists of all of the
edges of $G$ with one endpoint in $A$ and the other endpoint in $B$. We write
$e(A,B):=e(G[A,B])$.

For an (ordered) graph $G$ and a vertex $x\in V(G)$, we define $N_{G}(x)$ as
the set of neighbours of $x$ in $G$ and $d_{G}(x):=|N_{G}(x)|$. For
$X\subseteq V(G)$ we define $d_{G}(x,X):=|N_{G}(x)\cap X|$. Given (ordered)
graphs $G$ and $H$ and $X\subseteq V(G)$ we say that $G[X]$ _spans a copy of
$H$ in $G$_ if $H$ is a spanning subgraph of $G[X]$.

Given an ordered graph $G$ we say that _$V_{1} <\dots<V_{r}$ is an interval
$r$-colouring of $G$_ to mean that there is an interval $r$-colouring of $G$
with colour classes $V_{1}<\dots<V_{r}$. We say that an ordered graph $G$ is
_complete $r$-partite_ if there exists an interval $r$-colouring
$V_{1}<\cdots<V_{r}$ such that $xy\in E(G)$ for every $x\in V_{i}$ and $y\in
V_{j}$ with $i\not=j$. We refer to the $V_{i}$’s as the _parts_ of $G$.

Given an unordered graph $G$ and a positive integer $t$, let $G(t)$ be the
graph obtained from $G$ by replacing every vertex $x\in V(G)$ by a set $V_{x}$
of $t$ vertices spanning an independent set, and joining $u\in V_{x}$ to $v\in
V_{y}$ precisely when $xy$ is an edge in $G$; that is, we replace the edges of
$G$ by copies of $K_{t,t}$. We will refer to $G(t)$ as a blown-up copy of $G$.
If $U_{i}$ is a vertex class in $G$ then we write $U_{i}(t)$ for the
corresponding vertex class in $G(t)$. We use analogous notation when
considering blown-up copies of complete $k$-partite ordered graphs. In
particular, given a complete $k$-partite ordered graph $B$ with parts
$B_{1}<\dots<B_{k}$, the _ordered blow-up $B(t)$ of $B$_ consists of parts
$B_{1}(t)<\dots<B_{k}(t)$ where $|B_{i}(t)|=t|B_{i}|$ for all $i\in[k]$.

Throughout the paper, we omit all floor and ceiling signs whenever these are
not crucial. The constants in the hierarchies used to state our results are
chosen from right to left. For example, if we claim that a result holds
whenever $0<a\ll b\ll c\leq 1$, then there are non-decreasing functions
$f:(0,1]\to(0,1]$ and $g:(0,1]\to(0,1]$ such that the result holds for all
$0<a,b,c\leq 1$ with $b\leq f(c)$ and $a\leq g(b)$. Note that $a\ll b$ implies
that we may assume in the proof that, e.g., $a<b$ or $a<b^{2}$.

##  2\. Extremal constructions

In this section we provide the extremal examples for Theorems 1.8 and 1.10.
First, consider the case when $H$ has a local barrier. We now construct an
$n$-vertex ordered graph which does not contain an $H$-cover (and thus no
perfect $H$-tiling), and whose minimum degree is more than
$(1-1/\chi_{<}(H))n-1$, thereby giving the lower bounds in Theorem 1.8(ii) and
Theorem 1.10(ii).

######  Extremal Example 1.

Let $n,r\in\mathbb{N}$ and $i,j\in[r+1]$ with $i\not=j$. Let $F_{1}(n,r,i,j)$
be an $n$-vertex ordered graph consisting of vertex classes
$U_{1}<\cdots<U_{r+1}$ which satisfy the following conditions:

  * •

$U_{i}=\\{u\\}$ is a singleton class while the remaining vertex classes are as
equally sized as possible, and in particular,
$|U_{j}|=\left\lfloor\frac{n-1}{r}\right\rfloor$;

  * •

$F_{1}(n,r,i,j)\setminus\\{u\\}$ is a complete $r$-partite ordered graph with
parts $U_{1},\dots,U_{i-1},U_{i+1},\dots U_{r+1}$;

  * •

$u$ is adjacent to all other vertices except those in $U_{j}$.

Note that

(2)
$\displaystyle\delta(F_{1}(n,r,i,j))=n-1-|U_{j}|=n-1-\left\lfloor\frac{n-1}{r}\right\rfloor>\left(1-\frac{1}{r}\right)n-1.$

Furthermore, we now prove that $F_{1}(n,r,i,j)$ does not contain an $H$-cover
(nor a perfect $H$-tiling) provided that $\chi_{<}(H)=r$ and $H$ has a local
barrier with respect to parameters $i,j\in[r+1]$.

######  Lemma 2.1.

Let $H$ be an ordered graph, let $r:=\chi_{<}(H)$ and let $n\in\mathbb{N}$. If
$H$ has a local barrier then there exist $i,j\in\mathbb{N}$, with $i\not=j$,
and a vertex $u\in F_{1}(n,r,i,j)$ such that there is no copy of $H$ in
$F_{1}(n,r,i,j)$ covering the vertex $u$. In particular, $F_{1}(n,r,i,j)$ does
not contain an $H$-cover nor a perfect $H$-tiling.

###### Proof.

Suppose $H$ has a local barrier with respect to $i\neq j\in[r+1]$, as defined
in Definition 1.7. Let $u$ be the vertex in the singleton class $U_{i}$ of
$F_{1}(n,r,i,j)$. Suppose there is a copy of $H$ in $F_{1}(n,r,i,j)$ covering
the vertex $u$. Then the interval $(r+1)$-colouring $U_{1}<\cdots<U_{r+1}$ of
$F_{1}(n,r,i,j)$ induces an interval $(r+1)$-colouring $V_{1}<\cdots<V_{r+1}$
of $H$ such that $V_{i}=\\{v\\}$ is a singleton class and there is no edge
between $v$ and $V_{j}$. This contradicts the assumption that $H$ has a local
barrier with respect to $i,j$; thus, there is no copy of $H$ in
$F_{1}(n,r,i,j)$ covering the vertex $u$.  $\square$

We immediately obtain the following corollary of Lemma 2.1 and (2).

######  Corollary 2.2.

Let $H$ be an ordered graph and let $n\in\mathbb{N}$. If $H$ has a local
barrier then

$\delta_{cov}(H,n)>\left(1-\frac{1}{\chi_{<}(H)}\right)n$

and, if $|H|$ divides $n$

$\delta_{<}(H,n)>\left(1-\frac{1}{\chi_{<}(H)}\right)n.$

∎

Next we prove a general lower bound on $\delta_{<}(H,n)$ which is
asymptotically sharp if the ordered graph $H$ does not have a local barrier.
Similarly to before, we construct an $n$-vertex ordered graph which does not
contain a perfect $H$-tiling and whose minimum degree is at least
$(1-1/\chi_{cr}^{*}(H))n-1$, thereby giving the lower bound in cases (i) and
(iii) of Theorem 1.8.

######  Extremal Example 2.

Let $H$ be an ordered graph and $n\in\mathbb{N}$. Set
$\ell:=\left\lfloor\frac{n}{\chi_{cr}^{*}(H)}+1\right\rfloor$. Define
$F_{2}(H,n)$ to be the unordered complete $\lceil n/\ell\rceil$-partite graph
on $n$ vertices such that all classes have size $\ell$ except for one class of
size at most $\ell$.

It is easy to check that the minimum degree of $F_{2}(H,n)$ is

(3)
$\displaystyle\delta(F_{2}(H,n))=n-\ell=n-\left\lfloor\frac{n}{\chi_{cr}^{*}(H)}+1\right\rfloor\geq\left(1-\frac{1}{\chi_{cr}^{*}(H)}\right)n-1.$

Additionally, there exists a certain ordering of the vertices of $F_{2}(H,n)$
such that the resulting ordered graph does not contain a perfect $H$-tiling:

######  Lemma 2.3.

Let $H$ be an ordered graph and $n\in\mathbb{N}$ such that $|H|$ divides $n$.
There exists an interval labelling $\phi$ of $F_{2}(H,n)$ such that the
ordered graph $(F_{2}(H,n),\phi)$ does not contain a perfect $H$-tiling.

###### Proof.

The critical chromatic number of $F_{2}(H,n)$ is

$\chi_{cr}(F_{2}(H,n))=\frac{n}{\ell}<\frac{n}{n/\chi_{cr}^{*}(H)}=\chi_{cr}^{*}(H).$

It follows that $F_{2}(H,n)$ is not a bottlegraph of $H$. Hence, by
definition, there exists a permutation $\sigma$ of $[\lceil n/\ell\rceil]$ and
an interval labelling $\phi$ of $F_{2}(H,n)$ with respect to $\sigma$ such
that $(F_{2}(H,n),\phi)$ does not contain a perfect $H$-tiling.  $\square$

Lemma 2.3 and (3) immediately imply the following corollary.

######  Corollary 2.4.

Let $H$ be an ordered graph. Then given any $n\in\mathbb{N}$ divisible by
$|H|$,

$\delta_{<}(H,n)\geq\delta(F_{2}(H,n))+1\geq\left(1-\frac{1}{\chi_{cr}^{*}(H)}\right)n.$

∎

Next we give a general lower bound for $\delta_{cov}(H,n)$ which is
asymptotically sharp if the ordered graph $H$ does not have a local barrier,
thereby giving the lower bound in Theorem 1.10(i).

######  Extremal Example 3.

Let $H$ be an ordered graph and $n\in\mathbb{N}$. Let $F_{3}(H,n)$ be the
complete $(\chi_{<}(H)-1)$-partite ordered graph on $n$ vertices with parts of
size as equal as possible.

It is easy to check that the minimum degree of $F_{3}(H,n)$ is

$\delta(F_{3}(H,n))=n-\left\lceil\frac{n}{\chi_{<}(H)-1}\right\rceil>\left(1-\frac{1}{\chi_{<}(H)-1}\right)n-1.$

As $\chi_{<}(F_{3}(H,n))<\chi_{<}(H)$, $F_{3}(H,n)$ does not contain a copy of
$H$ and thus does not contain an $H$-cover. We therefore obtain the following
result.

######  Lemma 2.5.

Let $H$ be an ordered graph and $n\in\mathbb{N}$. Then

$\delta_{cov}(H,n)\geq\delta(F_{3}(H,n))+1>\left(1-\frac{1}{\chi_{<}(H)-1}\right)n.$

∎

For $n$ divisible by $\chi_{<}(H)-1$, $F_{3}(H,n)$ also shows that the minimum
degree threshold that ensures an almost perfect $H$-tiling in an $n$-vertex
ordered graph is more than $(1-1/(\chi_{<}(H)-1))n$. Thus, combined with
Theorem 1.6 this immediately implies that, for all ordered graphs $H$,

(4) $\displaystyle\chi_{<}(H)-1<\chi^{*}_{cr}(H).$

Actually, we close the section by proving an even stronger lower bound on
$\chi_{cr}^{*}(H)$.

######  Proposition 2.6 (A lower bound for $\chi_{cr}^{*}(H)$).

Let $H$ be an ordered graph on $h$ vertices and $r:=\chi_{cr}^{*}(H)$. Then,

$\chi_{cr}^{*}(H)\geq(r-1)+\frac{r-1}{h-1}.$

###### Proof.

Let $B$ be an arbitrary bottlegraph of $H$. It suffices to show that
$\chi_{cr}(B)\geq(r-1)+\frac{r-1}{h-1}$. If $\chi_{cr}(B)\geq r$ then we are
done (since $h\geq r$), so for the rest of the proof we assume that
$\chi_{cr}(B)<r$. In particular, $B$ has exactly $r$ parts. Let $B_{1}$ denote
the part of $B$ of smallest size. Pick any interval labelling $\phi$ of $B$;
then there exists some $t\in\mathbb{N}$ such that the ordered blow-up
$(B(t),\phi)$ contains a perfect $H$-tiling $\mathcal{H}$. Since $B$ has
exactly $r$ parts, it follows that every copy of $H$ in $(B(t),\phi)$
intersects all parts of $B$. Hence,

$|B_{1}(t)|\geq|\mathcal{H}|=\frac{|B(t)|}{|H|}=t|B|/h\implies|B_{1}|\geq|B|/h,$

and so

$\chi_{cr}(B)=(r-1)\frac{|B|}{|B|-|B_{1}|}\geq(r-1)\frac{|B|}{|B|-|B|/h}=(r-1)+\frac{r-1}{h-1}.$

$\square$

In Section 3.3 we give a family of ordered graphs $H$ for which the lower
bound on $\chi_{cr}^{*}(H)$ in Proposition 2.6 is tight.

##  3\. Motivating examples

###  3.1. An example for Theorem 1.8(i)

Recall that Extremal Example 2 yields the lower bound in cases (i) and (iii)
of Theorem 1.8. The argument in Lemma 2.3 is rather straightforward. This is
because of the definition of $\chi^{*}_{cr}(H)$; if one takes a complete
multipartite graph $G$ with $\chi_{cr}(G)<\chi^{*}_{cr}(H)$, then by
definition there is a vertex labelling of $G$ so that the resulting ordered
graph does not contain a perfect $H$-tiling.

Therefore, if one provides an argument that justifies why a bottlegraph of $H$
is optimal, this equivalently can be translated into an argument which
explains why an ordered graph is an extremal example for cases (i) and (iii)
of Theorem 1.8. In this way, one can view $\chi^{*}_{cr}(H)$ as ‘encoding’
properties of the extremal example.

In Section 11 we will compute $\chi^{*}_{cr}(H)$ for various classes of
ordered graphs $H$. Often these arguments will be somewhat involved; thus, in
these cases the reason why the extremal example for Theorem 1.8 does not
contain a perfect $H$-tiling is also ‘involved’. That is, in general the
reason why extremal examples do not contain perfect $H$-tilings is not as
immediate as Lemma 2.3 might suggest. We illustrate this point through the
following example.

######  Example 3.1 (An example for Theorem 1.8(i)).

Let $\ell\geq 2$ and let $H$ be the complete $3$-partite ordered graph with
parts $H_{1}<H_{2}<H_{3}$ of size $\ell,1,\ell$ respectively.

For $H$ as in Example 3.1, we have that
$\chi_{cr}^{*}(H)=(4\ell^{2}-1)/\ell^{2}>3=\chi_{<}(H)$. (In fact, in
Proposition 11.5 below we compute $\chi_{cr}^{*}(F)$ for all complete
$3$-partite ordered graphs $F$.) Thus, for such $H$ we are in case (i) of
Theorem 1.8 and so

$\delta_{<}(H,n)=\left(1-\frac{\ell^{2}}{4\ell^{2}-1}+o(1)\right)n.$

We now describe an extremal example for Theorem 1.8 for such $H$. Let
$n\in\mathbb{N}$ such that $|H|$ divides $n$ and $n\geq 20$. Let $G$ be the
complete $4$-partite ordered graph on $n$ vertices with parts
$G_{1}<G_{2}<G_{3}<G_{4}$ where

$|G_{1}|=|G_{2}|=|G_{3}|=\left\lfloor\frac{n\ell^{2}}{4\ell^{2}-1}\right\rfloor+1\quad\text{and}\quad|G_{4}|=n-3\left\lfloor\frac{n\ell^{2}}{4\ell^{2}-1}\right\rfloor-3.$

Note that $G_{4}$ is the smallest part since $|G_{i}|\geq n/4$ for $i=1,2,3$
and $|G_{4}|\leq n/4$. In particular,

$\displaystyle\delta(G)=n-\left\lfloor\frac{n\ell^{2}}{4\ell^{2}-1}\right\rfloor-1\geq
n-\frac{n\ell^{2}}{4\ell^{2}-1}-1=\left(1-\frac{\ell^{2}}{4\ell^{2}-1}\right)n-1.$

Suppose for a contradiction that $G$ contains a perfect $H$-tiling
$\mathcal{H}$. Let $\mathcal{A}\subseteq\mathcal{H}$ be the set of copies of
$H$ in $\mathcal{H}$ which have exactly $\ell$ vertices in $G_{1}$ and set
$\mathcal{B}:=\mathcal{H}\setminus\mathcal{A}$. This immediately implies

(5) $\displaystyle|G_{1}|\geq\ell|\mathcal{A}|.$

Note that if $H^{\prime}\in\mathcal{A}$ then $H^{\prime}$ has at most $\ell+1$
vertices in $G_{1}\cup G_{2}$ while if $H^{\prime}\in\mathcal{B}$ then
$H^{\prime}$ has at most $\ell$ vertices in $G_{1}\cup G_{2}$. It follows that

(6) $\displaystyle|G_{1}|+|G_{2}|\leq(\ell+1)|\mathcal{A}|+\ell|\mathcal{B}|.$

Combining (5) and (6) yields the following:

$\displaystyle|\mathcal{A}|+|\mathcal{B}|\stackrel{{\scriptstyle(\ref{eqAB1})}}{{\geq}}$
$\displaystyle\frac{|G_{1}|+|G_{2}|-|\mathcal{A}|}{\ell}\stackrel{{\scriptstyle(\ref{eqAB2})}}{{\geq}}\frac{\ell|G_{1}|+\ell|G_{2}|-|G_{1}|}{\ell^{2}}$
$\displaystyle=$
$\displaystyle\frac{2\ell-1}{\ell^{2}}\left(\left\lfloor\frac{n\ell^{2}}{4\ell^{2}-1}\right\rfloor+1\right)>\frac{2\ell-1}{\ell^{2}}\left(\frac{n\ell^{2}}{4\ell^{2}-1}\right)=\frac{n}{2\ell+1}.$

The above is a contradiction since

$|\mathcal{A}|+|\mathcal{B}|=|\mathcal{H}|=\frac{|G|}{|H|}=\frac{n}{2\ell+1}.$

Hence, $G$ does not contain a perfect $H$-tiling.

Note that $G$ is a ‘space barrier’ construction as our argument tells us that
$G_{1}\cup G_{2}$ is ‘too big’ to ensure a perfect $H$-tiling in $G$;
moreover, the reason why $G_{1}\cup G_{2}$ is ‘too big’, whilst not difficult,
is not at first sight, obvious (i.e., we needed to consider how two types of
copies of $H$ intersect $G_{1}\cup G_{2}$).

Space barrier constructions occur in many other settings too (e.g., the
Kühn–Osthus perfect tiling theorem [20]). However, all previous graph space
barrier constructions we are aware of have a different flavour to the above
space barrier $G$. Indeed, previously known examples fail to contain the
desired substructure due to some very immediate property that means _one_
vertex class is ‘too small’ or ‘too big’.

In Section 11 we compute $\chi^{*}_{cr}(H)$ precisely for several classes of
ordered graphs. In particular, we give other ordered graphs $H$ that fall into
case (i) of Theorem 1.8, namely all complete $3$-partite ordered graphs and
all complete $r$-partite ordered graphs whose smallest part is the first or
last part (see Propositions 11.3 and 11.5).

###  3.2. An example for Theorem 1.8(ii)

The next example provides a family of ordered graphs that fall into case (ii)
of Theorem 1.8.

######  Example 3.2 (An example for Theorem 1.8(ii)).

Let $r,k\geq 3$ and let $H$ be the ordered graph with vertex set
$V(H)=[(r-1)k+2]$ and edge set
$E(H)=\\{(1,(r-1)k+2)\\}\cup\\{((s-1)k+2,sk+2):s\in[r-1]\\}$ (see Figure 1).
So $\chi_{<}(H)=r$.

$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$ Figure 1. The ordered graph $H$ as in
Example 3.2 for $r=4$ and $k=3$.

Let $B$ the complete $r$-partite graph with parts $B_{1},\dots,B_{r}$ where
$|B_{i}|=k$ for $i\in[r-1]$ and $|B_{r}|=2$. Observe that
$\chi_{cr}(B)=(r-1)+2/k$. It is straightforward to check that for any
permutation $\sigma$ of $[r]$ and any interval labelling $\phi$ of $B$ with
respect to $\sigma$, the ordered graph $(B,\phi)$ contains a spanning copy of
$H$; hence $B$ is a simple bottlegraph of $H$. It follows that

$\chi_{cr}^{*}(H)\leq\chi_{cr}(B)=(r-1)+\frac{2}{k}<r=\chi_{<}(H).$

Furthermore, $H$ has a local barrier: for any interval $(r+1)$-colouring
$\\{1\\}<V_{1}<\cdots<V_{r}$ of $H$ we have that $(r-1)k+2\in V_{r}$ and thus
there is one edge between $\\{1\\}$ and $V_{r}$.

###  3.3. An example for Theorem 1.8(iii)

Next we consider a family of ordered graphs which fall into case (iii) of
Theorem 1.8.

######  Example 3.3 (An example for Theorem 1.8(iii)).

Let $r,k\geq 2$ and let $H$ be the ordered graph with vertex set
$V(H)=[(r-1)k+1]$ and edge set $E(H)=\\{((s-1)k+1,sk+1):s\in[r-1]\\}$. So $H$
is the path $(1)(k+1)(2k+1)\dots((r-1)k+1)$ and $\chi_{<}(H)=r$ (see Figure
2).

$1$$2$$3$$4$$5$$6$$7$ Figure 2. The ordered graph $H$ as in Example 3.3 for
$r=4$ and $k=2$.

We will explicitly compute $\chi^{*}_{cr}(H)$. In particular, we prove that
$\chi^{*}_{cr}(H)<\chi_{<}(H)$ and that $H$ does not have a local barrier. We
first construct a bottlegraph of $H$. Let $B$ denote the complete $r$-partite
graph with parts $B_{1},\dots,B_{r}$ where $|B_{i}|=k$ for $i\in[r-1]$ and
$|B_{r}|=1$. Observe that $\chi_{cr}(B)=(r-1)+1/k$. It is straightforward to
check that for any permutation $\sigma$ of $[r]$ and any interval labelling
$\phi$ of $B$ with respect to $\sigma$, the ordered graph $(B,\phi)$ contains
a spanning copy of $H$. Thus, $B$ is a simple bottlegraph of $H$ and so
$\chi_{cr}^{*}(H)\leq\chi_{cr}(B)=(r-1)+1/k$. Moreover, Proposition 2.6
implies that in fact $\chi_{cr}^{*}(H)=(r-1)+1/k$.

Finally, we show that $H$ does not have a local barrier. Let
$i\not=j\in[r+1]$. If $i\not\in\\{1,r+1\\}$, there exists an interval
$(r+1)$-colouring $V_{1}<\cdots<V_{r+1}$ of $H$ such that $V_{i}=\\{x\\}$ with
$x\not=(s-1)k+1$ for every $s\in[r]$. Then $x$ is isolated in $H$ and so
clearly there is no edge between $x$ and $V_{j}$. If $i=1$, there exists an
interval $(r+1)$-colouring $V_{1}<\cdots<V_{r+1}$ of $H$ such that
$V_{i}=\\{1\\}$ and $V_{j}=\emptyset$; so again, there is no edge between
$V_{i}$ and $V_{j}$. The case $i=r+1$ is analogous; we take
$V_{i}=\\{(r-1)k+1\\}$ and $V_{j}=\emptyset$.

##  4\. Proof of Theorem 1.8

In this section we present some intermediate results and explain how they
imply Theorem 1.8. Crucial to our approach will be the use of the _absorbing
method_ , a technique that was introduced systematically by Rödl, Ruciński and
Szemerédi [25], but that has roots in earlier work (see, e.g., [19]). Given
ordered graphs $G,H$ and a set $W\subseteq V(G)$, a set $S\subseteq V(G)$ is
called an _$H$ -absorbing set for $W$_ if both $G[S]$ and $G[W\cup S]$ contain
perfect $H$-tilings. In [3, Theorem 4.1], Balogh, Li and the second author
provided a minimum degree condition that ensures an ordered graph $G$ contains
a set $Abs$ that is an $H$-absorbing set for every not too large set
$W\subseteq V(G)\setminus Abs$.

######  Theorem 4.1 (Balogh, Li and Treglown [3]).

Let $H$ be an ordered graph on $h$ vertices and let $\eta>0$. Then there
exists an $n_{0}\in\mathbb{N}$ and $0<\nu\ll\eta$ so that the following holds.
Suppose that $G$ is an ordered graph on $n\geq n_{0}$ vertices and

$\delta(G)\geq\left(1-\frac{1}{\chi_{<}(H)}+\eta\right)n.$

Then $V(G)=[n]$ contains a set $Abs$ so that

  * •

$|Abs|\leq\nu n$;

  * •

$Abs$ is an $H$-absorbing set for every $W\subseteq V(G)\setminus Abs$ such
that $|W|\in h\mathbb{N}$ and $|W|\leq\nu^{3}n$.

Theorems 1.6 and 4.1 can be combined to yield a minimum degree condition that
forces a perfect $H$-tiling. Indeed, let $G$ and $H$ be ordered graphs and
suppose that

$\delta(G)\geq\left(1-\frac{1}{\max\\{\chi_{<}(H),\chi_{cr}^{*}(H)\\}}+o(1)\right)n.$

We first invoke Theorem 4.1 to find a set $Abs\subseteq V(G)$ which is an
$H$-absorbing set for any not too large set $W\subseteq V(G)\setminus Abs$.
Then we apply Theorem 1.6 to $G\setminus Abs$ to find an $H$-tiling
$\mathcal{M}_{1}$ which covers all but a small proportion of vertices in
$G\setminus Abs$. Let $W$ denote the set of such vertices in $G\setminus Abs$.
Since $W$ is relatively small, $Abs$ is an $H$-absorbing set for $W$, and thus
$G[W\cup Abs]$ contains a perfect $H$-tiling $\mathcal{M}_{2}$. Finally,
observe that $\mathcal{M}_{1}\cup\mathcal{M}_{2}$ is a perfect $H$-tiling in
$G$.

Thus we have proven that

$\delta_{<}(H,n)\leq\left(1-\frac{1}{\max\\{\chi_{<}(H),\chi_{cr}^{*}(H)\\}}+o(1)\right)n.$

In particular, this is asymptotically sharp if
$\chi_{cr}^{*}(H)\geq\chi_{<}(H)$ (by Corollary 2.4) or if
$\chi_{cr}^{*}(H)<\chi_{<}(H)$ and $H$ has a local barrier (by Corollary 2.2),
therefore proving cases (i) and (ii) of Theorem 1.8. However, if
$\chi_{cr}^{*}(H)<\chi_{<}(H)$ and $H$ does not have a local barrier then this
minimum degree condition can be substantially lowered. To achieve this, we
need a new absorbing result:

######  Theorem 4.2 (Absorbing theorem for non-local barriers).

Let $H$ be an ordered graph on $h$ vertices with $\chi_{<}(H)\geq 3$ and let
$\eta>0$. If $H$ does not have a local barrier and
$\chi_{cr}^{*}(H)<\chi_{<}(H)$, then there exists an $n_{0}\in\mathbb{N}$ and
$0<\nu\ll\eta$ so that the following holds. Suppose that $G$ is an ordered
graph on $n\geq n_{0}$ vertices and

$\delta(G)\geq\left(1-\frac{1}{\chi_{<}(H)-1}+\eta\right)n.$

Then $V(G)=[n]$ contains a set $Abs$ so that

  * •

$|Abs|\leq\nu n$;

  * •

$Abs$ is an $H$-absorbing set for every $W\subseteq V(G)\setminus Abs$ such
that $|W|\in h\mathbb{N}$ and $|W|\leq\nu^{3}n$.

Note that the statement of Theorem 4.2 is false if one allows $\chi_{<}(H)=2$;
indeed, the conclusion of the theorem fails for so-called divisibility
barriers $H$.333More precisely, here _divisibility barrier_ means an ordered
graph $H$ with $\chi_{<}(H)=2$ that satisfies Property B as defined in [3,
Page 3]. However, one can adapt our proof and relax the hypothesis of Theorem
4.2 to $\chi_{<}(H)\geq 2$ if one additionally assumes $H$ is not a
divisibility barrier. We will not do this in this paper, however, as [3,
Theorem 1.9] already resolves the perfect $H$-tiling problem for ordered
graphs $H$ with $\chi_{<}(H)=2$.

We postpone the proof of Theorem 4.2 to Section 10. With Theorem 4.2 at hand,
we can now give the proof of Theorem 1.8.

Proof of Theorem 1.8.  First note that the lower bounds in parts (i)–(iii) of
the theorem follow immediately from Corollary 2.4 (for (i) and (iii)) and
Corollary 2.2 (for (ii)). Thus it remains to prove the upper bounds.

Let $H$ be an ordered graph with $\chi_{<}(H)\geq 3$ and let $\eta>0$. Let
$n\in\mathbb{N}$ be sufficiently large and such that $|H|$ divides $n$. Let
$G$ be an ordered graph on $n$ vertices with minimum degree so that

  * (i)

$\delta(G)\geq\left(1-\frac{1}{\chi^{*}_{cr}(H)}+\eta\right)n$ if
$\chi^{*}_{cr}(H)\geq\chi_{<}(H)$;

  * (ii)

$\delta(G)\geq\left(1-\frac{1}{\chi_{<}(H)}+\eta\right)n$ if
$\chi^{*}_{cr}(H)<\chi_{<}(H)$ and $H$ has a local barrier;

  * (iii)

$\delta(G)\geq\left(1-\frac{1}{\chi^{*}_{cr}(H)}+\eta\right)n$ if
$\chi^{*}_{cr}(H)<\chi_{<}(H)$ and $H$ has no local barrier.

Recall that $\chi^{*}_{cr}(H)>\chi_{<}(H)-1$. Thus, by Theorem 4.1 (for cases
(i) and (ii)) and Theorem 4.2 (for case (iii)), there exists some
$0<\nu\ll\eta$ and a set $Abs\subseteq V(G)$ such that

  * •

$|Abs|\leq\nu n$;

  * •

$Abs$ is an $H$-absorbing set for every $W\subseteq V(G)\setminus Abs$ such
that $|W|\in|H|\mathbb{N}$ and $|W|\leq\nu^{3}n$.

Let $G^{\prime}:=G\setminus Abs$. In all cases we have that
$\delta(G^{\prime})\geq(1-{1}/{\chi^{*}_{cr}(H)})|G^{\prime}|.$

Since $n$ was chosen to be sufficiently large, by Theorem 1.6 there exists an
$H$-tiling $\mathcal{M}_{1}$ in $G^{\prime}$ covering all but at most
$\nu^{3}n$ vertices. Let $W\subseteq V(G^{\prime})$ denote the set of vertices
which are not covered by $\mathcal{M}_{1}$. Since $|H|$ divides $n$,
$|V(\mathcal{M}_{1})|$ and $|Abs|$ we have that $|H|$ divides $|W|$ too. Also,
$|W|\leq\nu^{3}n$, hence $G^{\prime}[W\cup Abs]$ contains a perfect $H$-tiling
$\mathcal{M}_{2}$. Finally, observe that $\mathcal{M}_{1}\cup\mathcal{M}_{2}$
is a perfect $H$-tiling of $G$, as desired.∎

##  5\. Bottlegraphs

In the following proposition we show that it suffices to consider bottlegraphs
where all parts are of the same size except for perhaps one smaller part.

######  Proposition 5.1.

Let $H$ be an ordered graph and $B$ be a bottlegraph of $H$. There exists a
bottlegraph $B^{\prime}$ of $H$ and an integer $m\in\mathbb{N}$ such that
$\chi_{cr}(B^{\prime})=\chi_{cr}(B)$ and all parts of $B^{\prime}$ have size
$m$ except for one part with size at most $m$.

###### Proof.

Let $B$ be a bottlegraph of $H$; so $B$ is a complete $k$-partite unordered
graph with parts $B_{1},\dots,B_{k}$ for some $k\in\mathbb{N}$. Without loss
of generality, we may assume that $|B_{1}|\leq|B_{i}|$ for every $i>1$. Let
$B^{\prime}$ be the complete $k$-partite unordered graph with parts
$B^{\prime}_{1},\dots,B^{\prime}_{k}$ where

$|B^{\prime}_{i}|=\begin{cases}(k-1)|B_{1}|&\text{ if $i=1$}\\\
|B|-|B_{1}|&\text{ otherwise.}\end{cases}$

So $|B^{\prime}|=(k-1)|B|$. Furthermore, we have

$|B^{\prime}_{1}|=(k-1)|B_{1}|=k|B_{1}|-|B_{1}|\leq|B|-|B_{1}|=|B^{\prime}_{i}|$

for every $i>1$. It follows that

$\chi_{cr}(B^{\prime})=\frac{(k-1)|B^{\prime}|}{|B^{\prime}|-|B^{\prime}_{1}|}=\frac{(k-1)^{2}|B|}{(k-1)|B|-(k-1)|B_{1}|}=\frac{(k-1)|B|}{|B|-|B_{1}|}=\chi_{cr}(B).$

It remains to show that $B^{\prime}$ is a bottlegraph of $H$. Observe that the
vertices in $B^{\prime}_{1}$ can be partitioned into $(k-1)$ sets of size
$|B_{1}|$ while the vertices in $B^{\prime}_{i}$ can be partitioned into
$(k-1)$ sets of sizes $|B_{2}|,\dots,|B_{k}|$ respectively, for every $i>1$.
This implies that $B^{\prime}$ contains a perfect $B$-tiling consisting of
$(k-1)$ copies of $B$.

Let $\\{C_{1},\dots,C_{k-1}\\}$ be a perfect $B$-tiling in $B^{\prime}$ (i.e.,
each $C_{i}$ is a copy of $B$ in $B^{\prime}$). Let $\sigma$ be a permutation
of $[k]$ and let $\phi$ be an interval labelling of $B^{\prime}$ with respect
to $\sigma$. For every $C_{i}$, $\phi$ induces an interval labelling
$\phi_{i}$ of $C_{i}$ with respect to some permutation $\sigma_{i}$ of $[k]$.
Since $B$ is a bottlegraph, given any $i\in[k-1]$, there exists some
$t_{i}\in\mathbb{N}$ such that the ordered blow-up $(C_{i}(t_{i}),\phi_{i})$
contains a perfect $H$-tiling. Set $t:=t_{1}t_{2}\dots t_{k-1}$. Then the
ordered blow-up $(C_{i}(t),\phi_{i})$ contains a perfect $H$-tiling
$\mathcal{M}_{i}$, for each $i\in[k-1]$.

Finally, $\mathcal{M}_{1}\cup\cdots\cup\mathcal{M}_{k-1}$ is a perfect
$H$-tiling of the ordered blow-up $(B^{\prime}(t),\phi)$. Since $\sigma,\phi$
were arbitrary, $B^{\prime}$ is a bottlegraph of $H$.  $\square$

Note that the notion of a bottlegraph of $H$ (Definition 1.4) and
$1$-bottlegraph (Definition 1.14) are not quite the same. However, the next
result implies that $\chi^{*}_{cr}(H)=\chi^{*}_{cr}(1,H)$.

######  Proposition 5.2.

Let $H$ be an ordered graph. Then $\chi^{*}_{cr}(H)=\chi^{*}_{cr}(1,H)$.

###### Proof.

Let $\mathcal{X}:=\\{\chi_{cr}(B):\ B\text{ is a bottlegraph of }H\\}$ and
$\mathcal{X}_{1}:=\\{\chi_{cr}(B):\ B\text{ is a $1$-bottlegraph of $H$}\\}.$
Thus, $\inf\mathcal{X}=\chi^{*}_{cr}(H)$ and
$\inf\mathcal{X}_{1}=\chi^{*}_{cr}(1,H)$. By definition of a bottlegraph and
$1$-bottlegraph we have that $\mathcal{X}_{1}\subseteq\mathcal{X}$; so to
prove the proposition it suffices to show that
$\mathcal{X}\subseteq\mathcal{X}_{1}$.

Given any bottlegraph $B$ of $H$, let $B^{\prime}$ be the bottlegraph of $H$
obtained by applying Proposition 5.1. So $B^{\prime}$ satisfies conditions (i)
and (ii) in the definition of a $1$-bottlegraph of $H$ and
$\chi_{cr}(B^{\prime})=\chi_{cr}(B)$. As $B^{\prime}$ is a bottlegraph of $H$,
there is some $t\in\mathbb{N}$ so that $B^{\prime}(t)$ satisfies condition
(iii) of the definition of a $1$-bottlegraph of $H$. Then $B^{\prime}(t)$ is a
$1$-bottlegraph of $H$ with
$\chi_{cr}(B^{\prime}(t))=\chi_{cr}(B^{\prime})=\chi_{cr}(B)$. Thus,
$\mathcal{X}\subseteq\mathcal{X}_{1}$, as desired.

$\square$

##  6\. The regularity lemma

In the proof of Theorem 4.2 we will make use of the regularity method. In this
section we state a multipartite version of Szemerédi’s regularity lemma and
some other related tools. First, we introduce some basic notation.

The _density_ of an (ordered) bipartite graph with vertex classes $A$ and $B$
is defined to be

$d(A,B):=\frac{e(A,B)}{|A||B|}.$

Given $\varepsilon>0$, a graph $G$ and two disjoint sets $A,B\subset V(G)$, we
say that the pair $(A,B)_{G}$ (or simply $(A,B)$ when the underlying graph is
clear) is _$\varepsilon$ -regular_ if for all sets $X\subseteq A$ and
$Y\subseteq B$ with $|X|\geq\varepsilon|A|$ and $|Y|\geq\varepsilon|B|$, we
have $|d(A,B)-d(X,Y)|<\varepsilon$. Given $d\in[0,1]$, the pair $(A,B)_{G}$ is
_$(\varepsilon,d)$ -regular_ if $G$ is $\varepsilon$-regular, and $d(A,B)\geq
d$.

We now state some well-known properties of $\varepsilon$-regular pairs. The
first (see, e.g., [18, Fact 1.5]) implies that one can delete many vertices
from an $(\varepsilon,d)$-regular pair and still retain such a regularity
property.

######  Lemma 6.1 (Slicing lemma).

Let $(A,B)_{G}$ be an $\varepsilon$-regular pair of density $d$, and for some
$\alpha>\varepsilon$, let $A^{\prime}\subseteq A$, $B^{\prime}\subseteq B$
with $|A^{\prime}|\geq\alpha|A|$ and $|B^{\prime}|\geq\alpha|B|$. Then
$(A^{\prime},B^{\prime})_{G}$ is
$(\varepsilon^{\prime},d-\varepsilon)$-regular with
$\varepsilon^{\prime}:=\max\\{\varepsilon/\alpha,2\varepsilon\\}$.

The following theorem is a multipartite version of Szemerédi’s regularity
lemma [27] (presented, e.g., as Lemma 5.5 in [3]).

######  Theorem 6.2 (Multipartite regularity lemma).

Given any integer $t\geq 2$, any $\varepsilon>0$ and any
$\ell_{0}\in\mathbb{N}$ there exists
$L_{0}=L_{0}(\varepsilon,t,\ell_{0})\in\mathbb{N}$ such that for every
$d\in(0,1]$ and for every nearly balanced $t$-partite graph
$G=(W_{1},\dots,W_{t})$ on $n\geq L_{0}$ vertices, there exists an
$\ell\in\mathbb{N}$, a partition $W^{0}_{i},W^{1}_{i},\dots,W^{\ell}_{i}$ of
$W_{i}$ for each $i\in[t]$ and a spanning subgraph $G^{\prime}$ of $G$, such
that the following conditions hold:

  1. (1)

$\ell_{0}\leq\ell\leq L_{0}$;

  2. (2)

$d_{G^{\prime}}(x)\geq d_{G}(x)-(d+\varepsilon)n$ for every $x\in V(G)$;

  3. (3)

$|W^{0}_{i}|\leq\varepsilon n/t$ for every $i\in[t]$;

  4. (4)

$|W^{j}_{i}|=|W^{j^{\prime}}_{i^{\prime}}|$ for every $i,i^{\prime}\in[t]$ and
$j,j^{\prime}\in[\ell]$;

  5. (5)

for every $i,i^{\prime}\in[t]$ and $j,j^{\prime}\in[\ell]$ either
$(W^{j}_{i},W^{j^{\prime}}_{i^{\prime}})_{G^{\prime}}$ is an
$(\varepsilon,d)$-regular pair or
$G^{\prime}[W^{j}_{i},W^{j^{\prime}}_{i^{\prime}}]$ is empty.

We call the $W^{j}_{i}$ _clusters_ , the $W^{0}_{i}$ the _exceptional sets_
and the vertices in the $W^{0}_{i}$ _exceptional vertices_. We refer to
$G^{\prime}$ as the pure graph. The _reduced graph $R$ of $G$ with parameters
$\varepsilon$, $d$ and $\ell_{0}$_ is the graph whose vertices are the
$W^{j}_{i}$ (where $i\in[t]$ and $j\in[\ell])$ and in which
$W^{j}_{i}W^{j^{\prime}}_{i^{\prime}}$ is an edge precisely when
$(W^{j}_{i},W^{j^{\prime}}_{i^{\prime}})_{G^{\prime}}$ is
$(\varepsilon,d)$-regular. The following well-known corollary of the
regularity lemma shows that the reduced graph almost inherits the minimum
degree of the original graph.

######  Proposition 6.3.

Let $0<\varepsilon,d,k<1$ and let $G$ be an $n$-vertex graph with
$\delta(G)\geq kn$. If $R$ is the reduced graph of $G$ obtained by applying
Theorem 6.2 with parameters $\varepsilon,d,\ell_{0}$, then
$\delta(R)\geq(k-2\varepsilon-d)|R|$.

A useful tool to embed subgraphs into $G$ using the reduced graph $R$ is the
so-called _key lemma_.

######  Lemma 6.4 (Key lemma [18]).

Let $0<\varepsilon<d$ and $q,t\in\mathbb{N}$. Let $R$ be a graph with
$V(R)=\\{v_{1},\dots,v_{k}\\}$. We construct a graph $G$ as follows: replace
every vertex $v_{i}\in V(R)$ with a set $V_{i}$ of $q$ vertices and replace
each edge of $R$ with an $(\varepsilon,d)$-regular pair. For each $v_{i}\in
V(R)$, let $U_{i}$ denote the set of $t$ vertices in $R(t)$ corresponding to
$v_{i}$. Let $H$ be a subgraph of $R(t)$ on $h$ vertices with maximum degree
$\Delta$. Set $\delta:=d-\varepsilon$ and
$\varepsilon_{0}:=\delta^{\Delta}/(2+\Delta)$. If
$\varepsilon\leq\varepsilon_{0}$ and $t-1\leq\varepsilon_{0}q$ then there are
at least $(\varepsilon_{0}q)^{h}$ labelled copies of $H$ in $G$ so that if
$x\in V(H)$ lies in $U_{i}$ in $R(t)$, then $x$ is embedded into $V_{i}$ in
$G$.

As in [3], some of our applications of Lemma 6.4 will take the following form:
suppose within an ordered graph $G$ we have vertex classes
$V_{1}<\ldots<V_{k}$ so that each pair $(V_{i},V_{j})_{G}$ is
$(\varepsilon,d)$-regular. Then Lemma 6.4 tells us $G$ contains many copies of
any fixed size ordered graph $H$ with $\chi_{<}(H)=k$, where the $i$th vertex
class of each such copy of $H$ is embedded into $V_{i}$.

##  7\. Absorbing tools

In this section we state a couple of results which are useful for proving the
existence of $H$-absorbing sets. The first result is the following crucial
lemma of Lo and Markström [23]; we present the ordered version of their result
which appeared as Lemma 7.1 in [3].

######  Lemma 7.1 (Lo and Markström [23]).

Let $h,s\in\mathbb{N}$ and $\xi>0$. Suppose that $H$ is an ordered graph on
$h$ vertices. Then there exists an $n_{0}\in\mathbb{N}$ such that the
following holds. Suppose that $G$ is an ordered graph on $n\geq n_{0}$
vertices so that, for any $x,y\in V(G)$, there are at least $\xi n^{sh-1}$
$(sh-1)$-sets $X\subseteq V(G)$ such that both $G[X\cup\\{x\\}]$ and
$G[X\cup\\{y\\}]$ contain perfect $H$-tilings. Then $V(G)$ contains a set $M$
so that

  * •

$|M|\leq(\xi/2)^{h}n/4$;

  * •

$M$ is an $H$-absorbing set for any $W\subseteq V(G)\setminus M$ such that
$|W|\in h\mathbb{N}$ and $|W|\leq(\xi/2)^{2h}n/(32s^{2}h^{3})$.

Informally, we will sometimes refer to a set $X$ satisfying the assumptions of
Lemma 7.1 as a _chain_ of size $|X|$ between vertices $x$ and $y$. The next
lemma states that it is in some sense possible to concatenate chains.

######  Lemma 7.2.

Let $H$ be an (ordered) graph on $h$ vertices, let $\alpha,\beta,\gamma>0$ and
$s_{1},s_{2},n\in\mathbb{N}$ where

$0<1/n\ll\gamma\ll\alpha,\beta,1/h,1/s_{1},1/s_{2}.$

Let $G$ be an (ordered) graph on $n$ vertices, $x,y\in V(G)$ and $A\subseteq
V(G)\setminus\\{x,y\\}$ where $|A|\geq\alpha n$. Suppose that for every $z\in
A$ there exist at least $\beta n^{s_{1}h-1}$ $(s_{1}h-1)$-sets $X\subseteq
V(G)$ such that both $G[X\cup\\{x\\}]$ and $G[X\cup\\{z\\}]$ contain perfect
$H$-tilings and similarly there exist at least $\beta n^{s_{2}h-1}$
$(s_{2}h-1)$-sets $Y\subseteq V(G)$ such that both $G[Y\cup\\{y\\}]$ and
$G[Y\cup\\{z\\}]$ contain perfect $H$-tilings. Then there exist at least
$\gamma n^{(s_{1}+s_{2})h-1}$ $((s_{1}+s_{2})h-1)$-sets $Z\subseteq V(G)$ such
that both $G[Z\cup\\{x\\}]$ and $G[Z\cup\\{y\\}]$ contain perfect $H$-tilings.

###### Proof.

Let $z\in A$ and let $X,Y$ be an $(s_{1}h-1)$-set and an $(s_{2}h-1)$-set
respectively which satisfy the above properties, with $X,Y$ disjoint so that
$y\not\in X$ and $x\not\in Y$. Then $X\cup\\{z\\}\cup Y$ is an
$((s_{1}+s_{2})h-1)$-set and both $G[(X\cup\\{z\\}\cup Y)\cup\\{x\\}]$ and
$G[(X\cup\\{z\\}\cup Y)\cup\\{y\\}]$ contain perfect $H$-tilings. Thus, it is
enough to lower bound the number of such triples $(z,X,Y)$. There are at least
$\alpha n$ choices for $z$. Given a fixed choice of $z$ there are at least
$\beta n^{s_{1}h-1}-n^{s_{1}h-2}\geq\beta n^{s_{1}h-1}/2$ suitable choices for
$X$. For a fixed $X$ there are at least $\beta
n^{s_{2}h-1}-s_{1}hn^{s_{2}h-2}\geq\beta n^{s_{2}h-1}/2$ choices for $Y$.
Therefore, in total there are at least

$\frac{(\alpha n)\cdot(\beta n^{s_{1}h-1}/2)\cdot(\beta
n^{s_{2}h-1}/2)}{((s_{1}+s_{2})h-1)!}\geq\gamma n^{(s_{1}+s_{2})h-1}$

choices for $Z$, where the denominator here is because different choices of
the triple $(z,X,Y)$ can yield the same set $Z$.  $\square$

##  8\. Flexible colouring

In this section we prove several auxiliary results which will be particularly
important for the proofs of Theorem 4.2 and Theorem 12.1. We start with the
following definition.

######  Definition 8.1.

Let $H$ be an ordered graph and let $r:=\chi_{<}(H)$. We say that $H$ is
_flexible_ if, for every $i\in[r-1]$, there exists an interval
$(r+1)$-colouring

$V_{1}<\cdots<V_{i}<\\{x\\}<V_{i+1}<\cdots<V_{r}$

of $H$ such that both $V_{1}<\cdots<V_{i}\cup\\{x\\}<V_{i+1}<\cdots<V_{r}$ and
$V_{1}<\cdots<V_{i}<V_{i+1}\cup\\{x\\}<\cdots<V_{r}$ are interval
$r$-colourings of $H$.

In the next lemma we show that given a flexible ordered graph $H$, there
exists a complete $\chi_{<}(H)$-partite ordered graph $F$ such that $F$
contains a perfect $H$-tiling and any complete $r$-partite ordered graph
$F^{\prime}$, whose parts have approximately the same sizes as the
corresponding parts in $F$, contains a perfect $H$-tiling too.

######  Lemma 8.2.

Let $H$ be an ordered graph on $h$ vertices and let $r:=\chi_{<}(H)$. If $H$
is flexible then the following holds. For every $i\in[r-1]$, let
$V_{1}^{i}<\cdots<V_{i}^{i}<\\{x_{i}\\}<V_{i+1}^{i}<\cdots<V_{r}^{i}$ be an
interval $(r+1)$-colouring of $H$ as described in Definition 8.1. Let $F$ be
the complete $r$-partite ordered graph with parts $F_{1}<\cdots<F_{r}$ such
that

$|F_{k}|=\begin{cases}rh+2rh\cdot\sum\limits_{i=1}^{r-1}|V_{k}^{i}|\text{\quad
for $k\in\\{1,r\\};$}\\\
2rh+2rh\cdot\sum\limits_{i=1}^{r-1}|V_{k}^{i}|\text{\quad
otherwise.}\end{cases}$

Thus, $|F|=2r(r-1)h^{2}$. Let $s_{1},\dots,s_{r}\in\mathbb{Z}$ such that
$s_{1}+\cdots+s_{r}=0$ and $|s_{i}|\leq h$ for every $i\in[r]$. Let
$F^{\prime}$ be the complete $r$-partite ordered graph with parts
$F^{\prime}_{1}<\cdots<F^{\prime}_{r}$ such that
$|F^{\prime}_{k}|=|F_{k}|+s_{k}$ for every $k\in[r]$. Then both $F$ and
$F^{\prime}$ contain perfect $H$-tilings.

###### Proof.

First, we explicitly construct a perfect $H$-tiling in $F$. For every
$i\in[r-1]$, consider $rh$ copies of the interval $r$-colouring
$V_{1}^{i}<\cdots<V_{i}^{i}\cup\\{x_{i}\\}<V_{i+1}^{i}<\cdots<V_{r}^{i}$ of
$H$ and $rh$ copies of the interval $r$-colouring
$V_{1}^{i}<\cdots<V_{i}^{i}<V_{i+1}^{i}\cup\\{x_{i}\\}<\cdots<V_{r}^{i}$ of
$H$. For every $k\in[r]$ we take the union of all the $k$th colour classes
from the interval $r$-colourings above to obtain $r$ new classes. It is easy
to check that the size of the new $k$th class is exactly the size of $F_{k}$,
so we have just constructed a perfect $H$-tiling in $F$. In particular, as
there are $2r(r-1)h$ copies of $H$ in this tiling, $|F|=2r(r-1)h^{2}$.

Note that for every pair of consecutive classes $(F_{k},F_{k+1})$ we could
independently move $rh$ vertices from $F_{k}$ to $F_{k+1}$ to yield a new
complete $r$-partite ordered graph which still contains a perfect $H$-tiling;
similarly, we could move $rh$ vertices from $F_{k+1}$ to $F_{k}$ (these $2rh$
vertices fulfill the role of $x_{k}$ in their respective interval
$r$-colourings of $H$). We are going to use this observation to construct a
perfect $H$-tiling in $F^{\prime}$.

Set $t_{k}:=s_{1}+\cdots+s_{k}$ for $k\in[r]$ and $t_{0}:=0$. For every pair
of consecutive classes $(F_{k},F_{k+1})$, if $t_{k}\geq 0$ move $t_{k}$
vertices from $F_{k+1}$ to $F_{k}$, otherwise move $-t_{k}$ vertices from
$F_{k}$ to $F_{k+1}$. This is possible since
$|t_{k}|\leq|s_{1}|+\cdots+|s_{r}|\leq rh$ by assumption. Note that the size
of the new $k$th class is
$|F_{k}|+t_{k}-t_{k-1}=|F_{k}|+s_{k}=|F^{\prime}_{k}|$, hence we just
constructed a perfect $H$-tiling in $F^{\prime}$.  $\square$

Observe that the ordered graphs $F$ and $F^{\prime}$ in Lemma 8.2 have the
same number of vertices. In the next corollary we ease this restriction and
allow $F^{\prime}$ to have a few more vertices than $F$.

######  Corollary 8.3.

Let $H$ be an ordered graph on $h$ vertices and let $r:=\chi_{<}(H)$. If $H$
is flexible then the following holds. Let $F$ be the complete $r$-partite
ordered graph with parts $F_{1}<\cdots<F_{r}$ as in Lemma 8.2 and let
$t\in\mathbb{N}$. For any $s_{1},\dots,s_{r},\ell\in\mathbb{N}\cup\\{0\\}$
such that $s_{1}+\cdots+s_{r}=\ell h\leq th$ and any complete $r$-partite
ordered graph $F^{\prime}$ with parts $F^{\prime}_{1}<\cdots<F^{\prime}_{r}$
of size $|F^{\prime}_{k}|=t|F_{k}|+s_{k}$ for every $k\in[r]$, both $F(t)$ and
$F^{\prime}$ contain perfect $H$-tilings.

###### Proof.

By Lemma 8.2, $F$ contains a perfect $H$-tiling and thus clearly the ordered
blow-up $F(t)$ contains a perfect $H$-tiling too.

We prove that $F^{\prime}$ contains a perfect $H$-tiling by induction on
$\ell$. If $\ell=0$ then $F^{\prime}=F(t)$ and so $F^{\prime}$ contains a
perfect $H$-tiling.

Assume $\ell>0$. For every $k\in[r]$, let
$s^{\prime}_{k}\in\mathbb{N}\cup\\{0\\}$ such that $s^{\prime}_{k}\leq s_{k}$
and $s^{\prime}_{1}+\cdots+s^{\prime}_{r}=h$. Let $Q_{1}<\cdots<Q_{r}$ be an
interval $r$-colouring of $H$. Notice that $V(F^{\prime})$ can be partitioned
into four sets $X,Y,W,Z$ such that

$|X\cap F^{\prime}_{k}|=(t-\ell)|F_{k}|,\quad|Y\cap
F^{\prime}_{k}|=(\ell-1)|F_{k}|+(s_{k}-s^{\prime}_{k}),\quad|W\cap
F^{\prime}_{k}|=|Q_{k}|,\quad|Z|=|F_{k}|+s^{\prime}_{k}-|Q_{k}|,$

for every $k\in[r]$. Observe that

  * •

If non-empty then $F^{\prime}[X]$ is a copy of $F(t-\ell)$, thus
$F^{\prime}[X]$ contains a perfect $H$-tiling.

  * •

If $\ell=1$ then $s^{\prime}_{k}=s_{k}$ for every $k\in[r]$ and so
$F^{\prime}[Y]$ is the empty graph. Otherwise, $F^{\prime}[Y]$ contains a
perfect $H$-tiling by the inductive hypothesis since
$(s_{1}-s^{\prime}_{1})+\cdots+(s_{r}-s^{\prime}_{r})=(\ell-1)h$ and
$s_{k}-s^{\prime}_{k}\geq 0$ for every $k\in[r]$.

  * •

$F^{\prime}[W]$ spans a copy of $H$.

  * •

$F^{\prime}[Z]$ contains a perfect $H$-tiling by Lemma 8.2 since

$\sum_{k=1}^{r}(s^{\prime}_{k}-|Q_{k}|)=h-h=0$

and $|s^{\prime}_{k}-|Q_{k}||\leq h$ for every $k\in[r]$.

Altogether this clearly implies $F^{\prime}$ contains a perfect $H$-tiling.
$\square$

Our goal now is to show that if $\chi_{cr}^{*}(H)<\chi_{<}(H)$ then $H$ is
flexible. This property is crucial for the proof of Theorem 4.2, and is a
corollary of the following lemma.

######  Lemma 8.4.

Let $H$ be an ordered graph with vertex set $[h]$ and let $r:=\chi_{<}(H)$. If
$H$ is not flexible, there exist some $i\in[r-1]$ such that the number of
vertices lying in the first $i$ intervals of any given interval $r$-colouring
of $H$ is fixed.

###### Proof.

Since $H$ is not flexible, there exist some $i\in[r-1]$ such that there is no
interval $(r+1)$-colouring $V_{1}<\cdots<V_{i}<\\{x\\}<V_{i+1}<\cdots<V_{r}$
of $H$ such that both $V_{1}<\cdots<V_{i}\cup\\{x\\}<V_{i+1}<\cdots<V_{r}$ and
$V_{1}<\cdots<V_{i}<V_{i+1}\cup\\{x\\}<\cdots<V_{r}$ are interval
$r$-colourings of $H$.

Let $U_{1}<\cdots<U_{r}$ be an interval $r$-colouring of $H$. Let $y$ be the
largest vertex in $U_{i}$ and let $z$ be the smallest vertex in $U_{i+1}$; so
$z=y+1$. Note that $y$ must be adjacent to some vertex in $U_{i+1}$, as
otherwise the interval $(r+1)$-colouring
$U_{1}<\cdots<U_{i}\setminus\\{y\\}<\\{y\\}<U_{i+1}<\cdots<U_{r}$ satisfies
the flexibility property, a contradiction. Let $y^{\prime}$ be the smallest
vertex in $U_{i+1}$ adjacent to $y$. Similarly, let $z^{\prime}$ be the
largest vertex in $U_{i}$ adjacent to $z$.

######  Claim 8.5.

Given any $r$-colouring $Q_{1}<\cdots<Q_{r}$ of $H$, $y\in Q_{i}$ and $z\in
Q_{i+1}.$

Fix an arbitrary interval $r$-colouring $Q_{1}<\cdots<Q_{r}$ of $H$; say that
$z^{\prime}$ lies in the $k$th interval $Q_{k}$. Note that
$Q_{1}<\cdots<Q_{k}\cap[z^{\prime}]<(U_{i}\setminus[z^{\prime}])<U_{i+1}<\cdots<U_{r}$
is an interval colouring of $H$. If (i) $k<i-1$ or (ii) $k=i-1$ and
$z^{\prime}=y$ then $\chi_{<}(H)<r$, a contradiction. If $k=i-1$ and
$z^{\prime}\not=y$ then the interval $(r+1)$-colouring
$Q_{1}<\cdots<Q_{i-1}\cap[z^{\prime}]<(U_{i}\setminus[z^{\prime}])<\\{z\\}<U_{i+1}\setminus\\{z\\}<\cdots<U_{r}$
satisfies the flexibility property, a contradiction to our initial assumption
in the proof. Thus, $k\geq i$, which implies that $z$ is contained in the
$(i+1)$th interval $Q_{i+1}$ or above since $z$ and $z^{\prime}$ are adjacent.
Similarly, we can show that $y$ is contained in the $i$th interval $Q_{i}$ or
below. This implies that, since $y,z$ are consecutive vertices in $H$, $y$
lies in $Q_{i}$ and $z$ in $Q_{i+1}$. This completes the proof of the claim.

By the claim above, the number of vertices in the first $i$ intervals of any
given interval $r$-colouring of $H$ is exactly $y$, yielding the required
result.  $\square$

######  Corollary 8.6.

Let $H$ be an ordered graph with vertex set $[h]$. If
$\chi_{cr}^{*}(H)<\chi_{<}(H)$, then $H$ is flexible.

###### Proof.

Let $r:=\chi_{<}(H)$. Suppose for a contradiction that $H$ is not flexible. By
Lemma 8.4, there exist some $i\in[r-1]$ such that the number of vertices lying
in the first $i$ intervals of any given interval $r$-colouring of $H$ is, say,
$y$ for some fixed $y\in\mathbb{N}$. Consider a bottlegraph $B$ of $H$ with
$\chi_{cr}(B)<r$ (which exists by definition of $\chi^{*}_{cr}(H)$ and as
$\chi^{*}_{cr}(H)<r$); note that $B$ must consist of precisely $r$ parts. By
Proposition 5.1 we may assume that $B$ has parts $B_{1},\dots,B_{r}$ where
$|B_{1}|<m$ and $|B_{i}|=m$ for some $m\in\mathbb{N}$. Let $\sigma$ be a
permutation of $[r]$ and $\phi$ be an interval labelling of $B$ with respect
to $\sigma$. Recall that the ordered graph $(B,\phi)$ has parts
$B_{\sigma^{-1}(1)}<\cdots<B_{\sigma^{-1}(r)}$. Then, there exists some
$t\in\mathbb{N}$ such that the ordered blow-up $(B(t),\phi)$ contains a
perfect $H$-tiling. In particular, this perfect $H$-tiling consists of
$t|B|/h$ copies of $H$. By assumption, each copy of $H$ has exactly $y$
vertices lying in the first $i$ parts of $(B(t),\phi)$ which implies that the
first $i$ parts contain exactly $yt|B|/h$ vertices; that is, the total number
of vertices in these parts is independent of the choice of $\sigma$. This is
clearly a contradiction as if we pick $\sigma$ such that $\sigma^{-1}(1)=1$
then there are fewer than $itm$ vertices in the first $i$ parts of
$(B(t),\phi)$, while if $\sigma^{-1}(r)=1$ then there are precisely $itm$
vertices in the first $i$ parts of $(B(t),\phi)$.  $\square$

Note that one does really require $\chi^{*}_{cr}(H)<\chi_{<}(H)$ in the
statement of Corollary 8.6; consider, e.g., when $H$ is a complete balanced
$r$-partite ordered graph with parts of size at least $2$.

##  9\. Proof sketch of Theorem 4.2

In this section we briefly present the main ideas behind the proof of Theorem
4.2 before giving a rigorous argument in Section 10.1. Throughout this section
we set $r:=\chi_{<}(H)\geq 3$.

Let $H$ be an ordered graph such that $\chi_{cr}^{*}(H)<\chi_{<}(H)=r$ and $H$
has no local barrier. Let $G$ be an $n$-vertex graph with $n$ sufficiently
large and minimum degree

$\delta(G)\geq\left(1-\frac{1}{r-1}+o(1)\right)n.$

Our ultimate goal is to construct many chains between any given pair of
vertices $x,y\in V(G)$; then Lemma 7.1 will conclude the proof.

To achieve this, we first divide $[n]$ into many nearly balanced intervals,
remove all edges in $G$ which lie completely in some interval and then apply
the multipartite version of the regularity lemma to obtain a reduced graph
$R$. This preconditioning process will make it convenient to work with cliques
in the reduced graph: if two clusters $W$ and $W^{\prime}$ are adjacent in $R$
then by construction either $W<W^{\prime}$ or $W>W^{\prime}$.

We then show that given an arbitrary pair of clusters $W$ and $W^{\prime}$ in
$R$, for _almost_ every pair of vertices $x\in W$ and $y\in W^{\prime}$ we can
find many chains between $x$ and $y$. We achieve this gradually through
various steps:

  * •

Given a copy $T$ of $K_{r}$ in the reduced graph $R$ and an arbitrary cluster
$W$ in $T$, we prove that for _almost_ every pair of vertices $x,y\in W$ we
can find many chains between $x$ and $y$. This is quite straightforward and
the only property of $H$ we use is that $\chi_{<}(H)=r$.

  * •

Given a copy $T$ of $K_{r}$ in the reduced graph $R$ and two arbitrary
clusters $W,W^{\prime}$ in $T$, we prove that for _almost_ every pair of
vertices $x\in W$ and $y\in W^{\prime}$ we can find many chains between $x$
and $y$. The “flexibility” guaranteed by the condition
$\chi_{<}(H)<\chi_{cr}^{*}(H)$, formally stated in Corollary 8.6, will be the
main ingredient here.

  * •

Finally, we show that given any two arbitrary clusters $W$ and $W^{\prime}$,
for _almost_ every pair of vertices $x\in W$ and $y\in W^{\prime}$ we can find
many chains between $x$ and $y$. Since $r\geq 3$, this fairly
straightforwardly follows from the minimum degree of $R$ and the previous
point.

Next, given an arbitrary vertex $x\in V(G)$, we use the minimum degree
condition to find a particular structure $\mathcal{L}$ in $G$ containing $x$
and resembling an extremal construction for graphs which have a local barrier,
namely Extremal Example 1; in particular, the vertex classes of Extremal
Example 1 are replaced by some of the clusters in $R$. Assuming $H$ does not
have a local barrier, and using Corollary 8.3, we find many chains between $x$
and _almost_ every vertex lying in a certain cluster $W$ in $\mathcal{L}$.

Analogously, given an arbitrary $y\in V(G)\setminus\\{x\\}$, we find many
chains between $y$ and _almost_ every vertex lying in a certain cluster
$W^{\prime}$. By the previous steps, there exist many chains between almost
every vertex in $W$ and almost every vertex in $W^{\prime}$. By concatenation,
this ensures many chains between $x$ and $y$ and so the hypothesis of Lemma
7.1 is satisfied, thereby yielding Theorem 4.2.

##  10\. Proof of Theorem 4.2 and Theorem 1.10

###  10.1. Proof of Theorem 4.2

Let $H$ be an ordered graph on $h$ vertices such that
$\chi_{cr}^{*}(H)<\chi_{<}(H)$, $\chi_{<}(H)\geq 3$ and $H$ has no local
barrier. Set $r:=\chi_{<}(H)$.

Given any $\eta>0$, define additional constants
$d,\varepsilon_{1},\varepsilon_{2},\varepsilon_{3}\in\mathbb{R}$ and
$\ell_{0}\in\mathbb{N}$ so that

(7) $\displaystyle
0<1/\ell_{0}\ll\varepsilon_{1}\ll\varepsilon_{2}\ll\varepsilon_{3}\ll
d\ll\eta,1/(rh).$

Set $t:=\lceil 4/\eta\rceil$ and let
$L_{0}=L_{0}(\varepsilon_{1},t,\ell_{0})\geq\ell_{0}$ be as in Theorem 6.2.
Additionally, let $\xi_{1},\xi_{2},\xi_{3},\xi_{4},\xi_{5}\in\mathbb{R}$ and
$n\in\mathbb{N}$ so that

(8) $\displaystyle 0<1/n\ll\xi_{5}\ll\xi_{4}\ll\xi_{3}\ll\xi_{2}\ll\xi_{1}\ll
1/L_{0}.$

Define $\nu:=(\xi_{5}/2)^{h}/4$ and $s:=2r(r-1)h+1$.

Let $G$ be an ordered graph on $n\geq L_{0}$ vertices with minimum degree

$\delta(G)\geq\left(1-\frac{1}{r-1}+\eta\right)n.$

Let $W_{1}<\cdots<W_{t}$ be a nearly balanced interval partition of $[n]$. Let
$G^{\prime}$ be the ordered graph obtained by deleting all edges lying in each
$W_{i}$ from $G$. As $t=\lceil 4/\eta\rceil$ we have that
$|W_{i}|\leq\lceil\eta n/4\rceil$ for all $i\in[t]$ and so

(9)
$\displaystyle\delta(G^{\prime})\geq\left(1-\frac{1}{r-1}+\frac{\eta}{2}\right)n.$

Apply Theorem 6.2 to $G^{\prime}$ with parameters $\varepsilon_{1},t,\ell_{0}$
and $d$ to obtain a pure graph $G^{\prime\prime}$ and a partition
$W^{0}_{i},\dots,W^{\ell}_{i}$ for every $W_{i}$, where $\ell_{0}\leq\ell\leq
L_{0}$. All non-exceptional clusters $W^{j}_{i}$ have size $m$ where

(10) $\displaystyle
m\geq\frac{1}{\ell}\left(\left\lfloor\frac{n}{t}\right\rfloor-\frac{\varepsilon_{1}n}{t}\right)\geq\frac{\eta
n}{5L_{0}}.$

Let $R$ be the corresponding reduced graph of $G^{\prime}$. By (9),
Proposition 6.3 implies that

(11)
$\displaystyle\delta(R)\geq\left(1-\frac{1}{r-1}+\frac{\eta}{3}\right)|R|.$

Crucially, observe that if $W_{i}^{j}W_{i^{\prime}}^{j^{\prime}}$ is an edge
in $R$ then, by construction of $G^{\prime}$, $i\not=i^{\prime}$ and so either
$W_{i}^{j}<W_{i^{\prime}}^{j^{\prime}}$ or
$W_{i}^{j}>W_{i^{\prime}}^{j^{\prime}}$.

First, we prove that given a copy $T$ of $K_{r}$ in $R$ and an arbitrary
cluster $W$ in $T$, for _almost_ every pair of vertices $x,y\in W$ there exist
many chains between $x$ and $y$.

######  Claim 10.1.

Let $T_{1}<\cdots<T_{r}$ be $r$ clusters which form a copy of $K_{r}$ in $R$.
Given any $i\in[r]$, there exists a set $A_{i}\subseteq T_{i}$ of size
$|A_{i}|\geq(1-\varepsilon_{1}r)|T_{i}|$ such that the following holds: for
every $x\in A_{i}$ there exists a set $C_{x}\subseteq T_{i}$ of size
$|C_{x}|\geq(1-2\varepsilon_{2}r)|T_{i}|$ such that for every $y\in C_{x}$
there are at least $\xi_{1}n^{h-1}$ $(h-1)$-sets $X\subseteq V(G)$ so that
both $G[X\cup\\{x\\}]$ and $G[X\cup\\{y\\}]$ contain a copy of $H$.

###### Proof.

Fix $i\in[r]$. For every $k\not=i$, let

$L_{k}:=\\{v\in
T_{i}:d_{G^{\prime\prime}}(v,T_{k})\leq(d-\varepsilon_{1})|T_{k}|\\}.$

Observe that $d_{G^{\prime\prime}}(L_{k},T_{k})\leq d-\varepsilon_{1}$ for
every $k\not=i$. Suppose $|L_{k_{0}}|\geq\varepsilon|T_{i}|$ for some
$k_{0}\not=i$. Since $(T_{i},T_{k_{0}})_{G^{\prime\prime}}$ is
$(\varepsilon_{1},d)$-regular then

$|d_{G^{\prime\prime}}(L_{k_{0}},T_{k_{0}})-d_{G^{\prime\prime}}(T_{i},T_{k_{0}})|<\varepsilon_{1}$

and so $d_{G^{\prime\prime}}(L_{k_{0}},T_{k_{0}})>d-\varepsilon_{1}$, a
contradiction. Thus $|L_{k}|<\varepsilon_{1}|T_{i}|$ for every $k\not=i$. In
particular,

$|L_{1}\cup\cdots\cup
L_{r}|<\varepsilon_{1}(r-1)|T_{i}|<\varepsilon_{1}r|T_{i}|.$

Let $A_{i}:=T_{i}\setminus(L_{1}\cup\cdots\cup L_{r})$. It follows from the
previous inequality that

$|A_{i}|\geq(1-\varepsilon_{1}r)|T_{i}|.$

Let $x\in A_{i}$. Define $T^{\prime}_{k}:=T_{k}\cap N_{G^{\prime\prime}}(x)$
for every $k\not=i$ and $T^{\prime}_{i}:=T_{i}\setminus\\{x\\}$. By the
slicing lemma (Lemma 6.1), the pair
$(T^{\prime}_{a},T^{\prime}_{b})_{G^{\prime\prime}}$ is
$(\varepsilon_{2},d/2)$-regular for every $a\not=b\in[r]$. For every
$k\not=i$, let

$L^{\prime}_{k}:=\\{v\in
T^{\prime}_{i}:d_{G^{\prime\prime}}(v,T^{\prime}_{k})\leq(d/2-\varepsilon_{2})|T^{\prime}_{k}|\\}.$

By the same argument as before,

$|L^{\prime}_{1}\cup\cdots\cup
L^{\prime}_{r}|<\varepsilon_{2}r|T^{\prime}_{i}|.$

Let $C_{x}:=T^{\prime}_{i}\setminus(L^{\prime}_{1}\cup\cdots\cup
L^{\prime}_{r})$. The above inequality implies that

$|C_{x}|\geq(1-\varepsilon_{2}r)|T^{\prime}_{i}|\geq(1-2\varepsilon_{2}r)|T_{i}|.$

Let $y\in C_{x}$. Define $T^{\prime\prime}_{k}:=T^{\prime}_{k}\cap
N_{G^{\prime\prime}}(y)=T_{k}\cap N_{G^{\prime\prime}}(x)\cap
N_{G^{\prime\prime}}(y)$ for every $k\not=i$ and
$T^{\prime\prime}_{i}:=T^{\prime}_{i}\setminus\\{y\\}=T_{i}\setminus\\{x,y\\}$.
By the slicing lemma, the pair
$(T^{\prime\prime}_{a},T^{\prime\prime}_{b})_{G^{\prime\prime}}$ is
$(\varepsilon_{3},d/3)$-regular for every $a\not=b\in[r]$. Furthermore, by
construction, $x$ and $y$ are adjacent to all vertices in
$T^{\prime\prime}_{k}$ for every $k\not=i$.

Let $V_{1}<\cdots<V_{r}$ be an interval $r$-colouring of $H$. Pick any $v\in
V_{i}$ and let $H^{\prime}$ be the complete $r$-partite ordered graph with
parts $V_{1}<\cdots<V_{i}\setminus\\{v\\}<\cdots<V_{r}$. Using (7), (8) and
(10), the key lemma (Lemma 6.4) implies that there exist at least
$\xi_{1}n^{h-1}$ vertex sets $X$ in $G$ so that $G[X]$ spans a copy of
$H^{\prime}$ where $V_{k}\subseteq T^{\prime\prime}_{k}$ for every $k\not=i$
and $V_{i}\setminus\\{v\\}\subseteq T^{\prime\prime}_{i}$. Because $x$ and $y$
are adjacent to all vertices in $T^{\prime\prime}_{k}$ for every $k\not=i$,
both $G[X\cup\\{x\\}]$ and $G[X\cup\\{y\\}]$ are spanned by a copy of $H$.
$\square$

We now prove that given a copy $T$ of $K_{r}$ in the reduced graph $R$ and two
arbitrary clusters $W$ and $W^{\prime}$ in $T$, for _almost_ every pair of
vertices $x\in W$ and $y\in W^{\prime}$ there exist many chains between $x$
and $y$. Recall $s=2r(r-1)h+1$.

######  Claim 10.2.

Let $T_{1}<\cdots<T_{r}$ be $r$ clusters which form a copy of $K_{r}$ in $R$.
For every $i,j\in[r]$, there exist sets $A_{i}\subseteq T_{i}$ and
$A_{j}\subseteq T_{j}$ of size $|A_{i}|\geq(1-\varepsilon_{1}r)|T_{i}|$ and
$|A_{j}|\geq(1-\varepsilon_{1}r)|T_{j}|$ such that for every $x\in A_{i}$ and
$y\in A_{j}$ there are at least $\xi_{2}n^{sh-1}$ $(sh-1)$-sets $X\subseteq
V(G)$ for which both $G[X\cup\\{x\\}]$ and $G[X\cup\\{y\\}]$ contain perfect
$H$-tilings.

###### Proof.

Fix $i,j\in[r]$. As in the proof of Claim 10.1, for every $k\not=i$, we define

$L_{k}:=\\{v\in
T_{i}:d_{G^{\prime\prime}}(v,T_{k})\leq(d-\varepsilon_{1})|T_{k}|\\}$

and set $A_{i}:=T_{i}\setminus(L_{1}\cup\cdots\cup L_{r})$. In the proof of
Claim 10.1 we saw that

$|L_{1}\cup\cdots\cup
L_{r}|<\varepsilon_{1}(r-1)|T_{i}|<\varepsilon_{1}r|T_{i}|\ \ \text{and thus}\
\ |A_{i}|\geq(1-\varepsilon_{1}r)|T_{i}|.$

Let $x\in A_{i}$. As in the proof of Claim 10.1, we define
$T^{\prime}_{k}:=T_{k}\cap N_{G^{\prime\prime}}(x)$ for every $k\not=i$ and
$T^{\prime}_{i}:=T_{i}\setminus\\{x\\}$. The pair
$(T^{\prime}_{a},T^{\prime}_{b})_{G^{\prime\prime}}$ is
$(\varepsilon_{2},d/2)$-regular for every $a\not=b\in[r]$.

For every $k\not=j$, let

$L^{\prime}_{k}:=\\{v\in
T^{\prime}_{j}:d_{G^{\prime\prime}}(v,T^{\prime}_{k})\leq(d/2-\varepsilon_{2})|T^{\prime}_{k}|\\}.$

Note that $L^{\prime}_{k}$ is not quite the same as the corresponding set
given in the proof of Claim 10.1 (it is defined it terms of $j$ not $i$);
however, as in the proof of Claim 10.1 we have that

$|L^{\prime}_{1}\cup\cdots\cup
L^{\prime}_{r}|<\varepsilon_{2}r|T^{\prime}_{j}|.$

Let $C:=T^{\prime}_{j}\setminus(L^{\prime}_{1}\cup\cdots\cup L^{\prime}_{r})$.
The previous inequality implies that

(12)
$\displaystyle|C|\geq(1-\varepsilon_{2}r)|T^{\prime}_{j}|\geq(1-\varepsilon_{2}r)(d-\varepsilon_{1})|T_{j}|\stackrel{{\scriptstyle(\ref{hier1})}}{{\geq}}\frac{d}{2}|T_{j}|.$

Let $z\in C$. Define $T^{\prime\prime}_{k}:=T^{\prime}_{k}\cap
N_{G^{\prime\prime}}(z)$ for every $k\not=j$ and
$T^{\prime\prime}_{j}:=T^{\prime}_{j}\setminus\\{z\\}$. By the slicing lemma
and (7), the pair
$(T^{\prime\prime}_{a},T^{\prime\prime}_{b})_{G^{\prime\prime}}$ is
$(\varepsilon_{3},d/3)$-regular for every pair $a\not=b\in[r]$. Furthermore,
by construction, $x$ is adjacent to all vertices in $T^{\prime\prime}_{k}$ for
every $k\not=i$ while $z$ is adjacent to all vertices in
$T^{\prime\prime}_{k}$ for every $k\not=j$.

Since $\chi_{cr}^{*}(H)<\chi_{<}(H)$, by Corollary 8.6 $H$ is flexible. Let
$F$ be the complete $r$-partite ordered graph with parts $F_{1}<\cdots<F_{r}$
as defined in Lemma 8.2. Recall that $|F|=2r(r-1)h^{2}=(s-1)h$. Pick any $v\in
F_{i}$ and let $F^{*}$ be the ordered graph obtained by removing the vertex
$v$ from $F$. In particular, $F^{*}$ is a complete $r$-partite ordered graph
with parts $F_{1}<\cdots<F_{i}\setminus\\{v\\}<\cdots<F_{r}$. By (7), (8) and
(10), the key lemma (Lemma 6.4) implies that there exist at least
$\xi_{1}n^{|F|-1}$ vertex sets $Y$ in $G$ so that $G[Y]$ spans a copy of
$F^{*}$ where $F_{k}\subseteq T^{\prime\prime}_{k}$ for every $k\not=i$ and
$F_{i}\setminus\\{v\\}\subseteq T^{\prime\prime}_{i}$.

Given any such set $Y$, since $x$ is adjacent to all vertices in
$T^{\prime\prime}_{k}$ (for all $k\not=i$) then $G[Y\cup\\{x\\}]$ is spanned
by a copy of $F$ and thus it contains a perfect $H$-tiling. Similarly, since
$z$ is adjacent to all vertices in $T^{\prime\prime}_{k}$ (for all $k\not=j$)
then $G[Y\cup\\{z\\}]$ is spanned by a complete $r$-partite ordered graph
$F^{\prime}$ on $|F|$ vertices where each part of $F^{\prime}$ differs in size
by at most one compared to the corresponding part in $F$. Thus, Lemma 8.2
implies $G[Y\cup\\{z\\}]$ contains a perfect $H$-tiling.

Let $A_{j}\subseteq T_{j}$ be as in the statement of Claim 10.1; so
$|A_{j}|\geq(1-\varepsilon_{1}r)|T_{j}|$. Let $y\in A_{j}$. By Claim 10.1,
there exists a set $C_{y}\subseteq T_{j}$ of size

(13) $\displaystyle|C_{y}|\geq(1-2\varepsilon_{2}r)|T_{j}|$

such that for any $z\in C_{y}$ there exist at least $\xi_{1}n^{h-1}$
$(h-1)$-sets $Z\subseteq V(G)$ so that both $G[Z\cup\\{y\\}]$ and
$G[Z\cup\\{z\\}]$ contain spanning copies of $H$.

In summary, given any $x\in A_{i}$ and $y\in A_{j}$, we have shown that for
every $z\in C\cap C_{y}$ there exist at least $\xi_{1}n^{|F|-1}$
$(|F|-1)$-sets $Y$ such that both $G[Y\cup\\{x\\}]$ and $G[Y\cup\\{z\\}]$
contain perfect $H$-tilings and similarly there exist at least
$\xi_{1}n^{h-1}$ $(h-1)$-sets $Z$ such that both $G[Z\cup\\{y\\}]$ and
$G[Z\cup\\{z\\}]$ contain perfect $H$-tilings. Furthermore, as
$C,C_{y}\subseteq T_{j}$ note that

$|C\cap C_{y}|=|C|+|C_{y}|-|C\cup
C_{y}|\geq|C|+|C_{y}|-|T_{j}|\stackrel{{\scriptstyle(\ref{hier1}),(\ref{Cbound}),(\ref{Cybound})}}{{\geq}}\varepsilon_{1}|T_{j}|=\varepsilon_{1}m\stackrel{{\scriptstyle(\ref{hier3})}}{{\geq}}\frac{\varepsilon_{1}\eta
n}{5L_{0}}.$

Applying Lemma 7.2 with $C\cap
C_{y},\varepsilon_{1}\eta/({5L_{0}}),\xi_{1},\xi_{2}$ playing the roles of
$A,\alpha,\beta,\gamma$, we conclude that there exist at least
$\xi_{2}n^{|F|+h-1}=\xi_{2}n^{sh-1}$ $(sh-1)$-sets $X\subseteq V(G)$ such that
both $G[X\cup\\{x\\}]$ and $G[X\cup\\{y\\}]$ contain perfect $H$-tilings, as
desired.  $\square$

In the next claim we show that given any arbitrary pair of clusters $W$ and
$W^{\prime}$ in the reduced graph $R$, for _almost_ every pair of vertices
$x\in W$ and $y\in W^{\prime}$ there exist many chains between $x$ and $y$.
The assumption $r\geq 3$ is crucial here.

######  Claim 10.3.

For every pair of clusters $W$ and $W^{\prime}$ in $R$, there exist sets
$A\subseteq W$ and $A^{\prime}\subseteq W^{\prime}$ of size
$|A|\geq(1-\varepsilon_{1}r)|W|$ and
$|A^{\prime}|\geq(1-\varepsilon_{1}r)|W^{\prime}|$ satisfying the following:
for every pair of vertices $x\in A$ and $y\in A^{\prime}$ there are at least
$\xi_{3}n^{2sh-1}$ $(2sh-1)$-sets $X\subseteq V(G)$, such that both
$G[X\cup\\{x\\}]$ and $G[X\cup\\{y\\}]$ contain perfect $H$-tilings.

###### Proof.

Recall the reduced graph $R$ has minimum degree

$\delta(R)\geq\left(1-\frac{1}{r-1}+\frac{\eta}{3}\right)|R|.$

Using the above minimum degree condition, given any two adjacent clusters in
$R$, one can greedily construct a copy of $K_{r}$ in $R$ containing them both.

Since $r\geq 3$, $\delta(R)>|R|/2$ and so the clusters $W$ and $W^{\prime}$
have a common neighbour $U$ in $R$. Let $K$ and $K^{\prime}$ be two copies of
$K_{r}$ in $R$ containing $W,U$ and $W^{\prime},U$ respectively.

Apply Claim 10.2 with $K$, $W$, $U$ playing the roles of $K_{r}$, $T_{i}$ and
$T_{j}$ to obtain sets $A\subseteq W$ and $D\subseteq U$ with
$|A|\geq(1-\varepsilon_{1}r)|W|$ and $|D|\geq(1-\varepsilon_{1}r)|U|$.
Similarly, apply Claim 10.2 with $K^{\prime}$, $W^{\prime}$, $U$ playing the
roles of $K_{r}$, $T_{i}$ and $T_{j}$ to obtain sets $A^{\prime}\subseteq
W^{\prime}$ and $D^{\prime}\subseteq U$ with
$|A^{\prime}|\geq(1-\varepsilon_{1}r)|W|$ and
$|D^{\prime}|\geq(1-\varepsilon_{1}r)|U|$.

By Claim 10.2, for any $x\in A$, $y\in A^{\prime}$ and $z\in D\cap
D^{\prime}$, there exist at least $\xi_{2}n^{sh-1}$ $(sh-1)$-sets $Y\subseteq
V(G)$ such that both $G[Y\cup\\{x\\}]$ and $G[Y\cup\\{z\\}]$ contain perfect
$H$-tilings and $\xi_{2}n^{sh-1}$ $(sh-1)$-sets $Z\subseteq V(G)$ such that
both $G[Z\cup\\{y\\}]$ and $G[Z\cup\\{z\\}]$ contain perfect $H$-tilings.

Furthermore, since $D,D^{\prime}\subseteq U$ then

$|D\cap
D^{\prime}|\geq|D|+|D^{\prime}|-|U|\geq(1-2\varepsilon_{1}r)|U|=(1-2\varepsilon_{1}r)m\stackrel{{\scriptstyle(\ref{hier3})}}{{\geq}}\frac{\eta
n}{6L_{0}}.$

Applying Lemma 7.2 with $D\cap D^{\prime},\eta/({6L_{0}}),\xi_{2},\xi_{3}$
playing the roles of $A,\alpha,\beta,\gamma$, we conclude that there exist at
least $\xi_{3}n^{2sh-1}$ $(2sh-1)$-sets $X\subseteq V(G)$ such that both
$G[X\cup\\{x\\}]$ and $G[X\cup\\{y\\}]$ contain perfect $H$-tilings, as
desired.  $\square$

In the next claim we use the minimum degree condition of the reduced graph $R$
to find a structure $\mathcal{L}$ containing an arbitrary vertex $x$ and
resembling the extremal construction for an ordered graph which has a local
barrier. Furthermore, we prove that there exist many chains between $x$ and
_almost_ every vertex in some cluster in $\mathcal{L}$.

######  Claim 10.4.

Let $x\in V(G)$. There exists some cluster $W\in V(R)$ and a set $A\subseteq
W$ of size $|A|\geq(1-\varepsilon_{2}r)|W|$ satisfying the following: for
every $y\in A$ there exist at least $\xi_{1}n^{sh-1}$ $(sh-1)$-sets
$X\subseteq V(G)$ such that both $G[X\cup\\{x\\}]$ and $G[X\cup\\{y\\}]$
contain perfect $H$-tilings.

###### Proof.

Let $x\in V(G)$ and define

$N^{*}(x):=\\{W^{i}_{j}\in
V(R):d_{G^{\prime}}(x,W^{i}_{j})\geq\eta|W^{i}_{j}|/100\\}.$

Recall that every non-exceptional cluster $W$ has size $m$. Hence, if $W\in
N^{*}(x)$ then there are at most $m$ neighbours of $x$ in $W$, while if
$W\not\in N^{*}(x)$ then there are at most $\eta m/100$ neighbours of $x$ in
$W$. Finally, there are at most $\varepsilon_{1}n$ vertices lying in
exceptional clusters. Therefore,

$\left(1-\frac{1}{r-1}+\frac{\eta}{2}\right)n\stackrel{{\scriptstyle(\ref{minG})}}{{\leq}}d_{G^{\prime}}(x)\leq
m\cdot|N^{*}(x)|+\eta n/100+\varepsilon_{1}n.$

and thus

(14) $\left(1-\frac{1}{r-1}+\frac{\eta}{3}\right)|R|\leq|N^{*}(x)|.$

Using (11) and (14), we can greedily find $r$ clusters $T_{1},\dots,T_{r}$ in
$R$ such that

  * •

the $T_{k}$’s span a copy of $K_{r}$ in $R$;

  * •

$T_{k}\in N^{*}(x)$ for every $k\in[r-1]$;

  * •

if $x\in W_{k_{0}}$ with $k_{0}\in[t]$ then $T_{k}\not\subseteq W_{k_{0}}$ for
all $k\in[r]$.

By the properties above, we may relabel indices so that there is an
$i\in[r+1]$ and $j\in[r]$ for which

$T_{1}<\cdots<T_{i-1}<x<T_{i}<\cdots<T_{r}$

and $T_{k}\in N^{*}(x)$ for every $k\not=j$.

Define $T^{\prime}_{k}:=T_{k}\cap N_{G^{\prime}}(x)$ for $k\not=j$ and
$T^{\prime}_{j}:=T_{j}$. By construction, $|T^{\prime}_{k}|\geq\eta m/100$ for
every $k\in[r]$. Thus, by the slicing lemma (Lemma 6.1),
$(T^{\prime}_{a},T^{\prime}_{b})_{G^{\prime\prime}}$ is
$(\varepsilon_{2},d/2)$-regular for every $a\not=b\in[r]$.

We will show that the cluster $W:=T_{j}$ is as desired for the claim. For
every $k\not=j$, let

$L_{k}:=\\{v\in
T^{\prime}_{j}:d_{G^{\prime\prime}}(v,T^{\prime}_{k})\leq(d/2-\varepsilon_{2})|T^{\prime}_{k}|\\}.$

It is easy to show that $|L_{k}|<\varepsilon_{2}|T^{\prime}_{j}|$. Let
$A:=T^{\prime}_{j}\setminus(L_{1}\cup\cdots\cup L_{r})$, then

$|A|\geq(1-\varepsilon_{2}r)|T^{\prime}_{j}|=(1-\varepsilon_{2}r)|T_{j}|.$

Let $y\in A$. Define $T^{\prime\prime}_{k}:=T^{\prime}_{k}\cap
N_{G^{\prime\prime}}(y)$ for every $k\not=j$ and
$T^{\prime\prime}_{j}=T^{\prime}_{j}\setminus\\{y\\}$. By the slicing lemma,
$(T^{\prime\prime}_{a},T^{\prime\prime}_{b})_{G^{\prime\prime}}$ is
$(\varepsilon_{3},d/3)$-regular for every $a\not=b\in[r]$. Furthermore, $x$
and $y$ are adjacent to all vertices in $T^{\prime\prime}_{k}$ for every
$k\not=j$ (see Figure 3).

$T_{1}\setminus\\{y\\}$$y$$T^{\prime\prime}_{2}$$x$$T^{\prime\prime}_{3}$
Figure 3. In this picture, we take $r=3$, $T_{1}<T_{2}<x<T_{3}$ and $j=1$.
Note that $(T_{1}\setminus\\{y\\},T^{\prime\prime}_{2})$,
$(T_{1}\setminus\\{y\\},T^{\prime\prime}_{3})$ and
$(T^{\prime\prime}_{2},T^{\prime}_{3})$ are regular pairs, while $x$ and $y$
are adjacent to all vertices in $T^{\prime\prime}_{2}$ and
$T^{\prime\prime}_{3}$.

Since $H$ has no local barrier, there exists an interval $(r+1)$-colouring

$V_{1}<\cdots<V_{i-1}<\\{v\\}<V_{i}<\cdots<V_{r}$

of $H$ such that there is no edge between $v$ and $V_{j}$. Furthermore, as
$\chi_{cr}^{*}(H)<\chi_{<}(H)$, $H$ is flexible by Corollary 8.6. Let $F$ be
the complete $r$-partite ordered graph with parts $F_{1}<\cdots<F_{r}$ as
defined in Lemma 8.2 and let $F^{\prime}$ be the complete $r$-partite ordered
graph with parts $F^{\prime}_{1}<\cdots<F^{\prime}_{r}$ where

$|F^{\prime}_{k}|=\begin{cases}|F_{k}|+|V_{k}|+1&\text{if $k=j$,}\\\
|F_{k}|+|V_{k}|&\text{otherwise.}\end{cases}$

Note that

$1+\sum_{k=1}^{r}|V_{k}|=1+(h-1)=h$

thus, both $F$ and $F^{\prime}$ contain perfect $H$-tilings by Corollary 8.3.

Pick any $u\in F^{\prime}_{j}$. Note that $F^{\prime}\setminus\\{u\\}$ is the
complete $r$-partite ordered graph such that the $k$th part has size
$|F_{k}|+|V_{k}|$ for every $k\in[r]$ and
$|F^{\prime}\setminus\\{u\\}|=|F|+h-1=sh-1$. By the key lemma (Lemma 6.4),
there exist at least $\xi_{1}n^{sh-1}$ $(sh-1)$-sets $X\subseteq V(G)$ such
that $G[X]$ spans a copy of $F^{\prime}\setminus\\{u\\}$ with
$F^{\prime}_{k}\subseteq T^{\prime\prime}_{k}$ for every $k\not=j$ and
$F^{\prime}_{j}\setminus\\{u\\}\subseteq T^{\prime\prime}_{j}$. It remains to
show that both $G[X\cup\\{x\\}]$ and $G[X\cup\\{y\\}]$ contain perfect
$H$-tilings.

First, we consider $G[X\cup\\{x\\}]$. Since $G[X]$ spans a copy of
$F^{\prime}\setminus\\{u\\}$ with $F^{\prime}_{k}\subseteq
T^{\prime\prime}_{k}$ for every $k\not=j$ and
$F^{\prime}_{j}\setminus\\{u\\}\subseteq T^{\prime\prime}_{j}$, then $X$ can
be partitioned into two sets $Y,Z$ such that

$|Y\cap T^{\prime\prime}_{k}|=|V_{k}|\ \ \text{and}\ \ |Z\cap
T^{\prime\prime}_{k}|=|F_{k}|$

for every $k\in[r]$. Note that $G[Z]$ spans a copy of $F$, thus $G[Z]$
contains a perfect $H$-tiling. On the other hand, $G[Y]$ spans a copy of
$H\setminus\\{v\\}$. Recall that $x$ is adjacent to all vertices in
$T^{\prime\prime}_{k}$ for every $k\not=j$ and
$T^{\prime\prime}_{i-1}<x<T^{\prime\prime}_{i}$. Thus, $G[Y\cup\\{x\\}]$ spans
a copy of $H$ in $G$ where $x$ plays the role of $v$. It follows that
$G[X\cup\\{x\\}]$ contains a perfect $H$-tiling.

Next, we consider $G[X\cup\\{y\\}]$. Since $y\in T_{j}$ and $y$ is adjacent to
all vertices in $T^{\prime\prime}_{k}$ for $k\not=j$, then $G[X\cup\\{y\\}]$
spans a copy of $F^{\prime}$ and so $G[X\cup\\{y\\}]$ contains a perfect
$H$-tiling.  $\square$

######  Remark 10.5.

Note that Claim 10.4 holds even if we relax the hypothesis of Theorem 4.2 to
allow $\chi_{<}(H)\geq 2$; that is, we did not use the condition that $r\geq
3$ anywhere in the proof of this claim. This fact will be useful in the proof
of Theorem 10.7 in the next subsection.

Our final claim states that given arbitrary vertices $x,y\in V(G)$ there exist
many chains of bounded size between $x$ and $y$.

######  Claim 10.6.

Let $x,y\in V(G)$. There exist at least $\xi_{5}n^{4sh-1}$ $(4sh-1)$-sets
$X\subseteq V(G)$ such that both $G[X\cup\\{x\\}]$ and $G[X\cup\\{y\\}]$
contain perfect $H$-tilings.

###### Proof.

By Claim 10.4 there exist clusters $W,W^{\prime}\in V(R)$ and sets $A\subseteq
W$, $A^{\prime}\subseteq W^{\prime}$ of size $|A|\geq(1-\varepsilon_{2}r)|W|$
and $|A^{\prime}|\geq(1-\varepsilon_{2}r)|W^{\prime}|$ such that for every
$z\in A$ and $z^{\prime}\in A^{\prime}$ there exist at least $\xi_{1}n^{sh-1}$
$(sh-1)$-sets $Y\subseteq V(G)$ such that both $G[Y\cup\\{x\\}]$ and
$G[Y\cup\\{z\\}]$ contain perfect $H$-tilings and at least $\xi_{1}n^{sh-1}$
$(sh-1)$-sets $Y^{\prime}\subseteq V(G)$ such that both
$G[Y^{\prime}\cup\\{y\\}]$ and $G[Y^{\prime}\cup\\{z^{\prime}\\}]$ contain
perfect $H$-tilings.

Furthermore, by Claim 10.3 there exist sets $D\subseteq W$,
$D^{\prime}\subseteq W^{\prime}$ of size $|D|\geq(1-\varepsilon_{1}r)|W|$ and
$|D^{\prime}|\geq(1-\varepsilon_{1}r)|W^{\prime}|$ such that for every $z\in
D$ and $z^{\prime}\in D^{\prime}$ there exist at least $\xi_{3}n^{2sh-1}$
$(2sh-1)$-sets $Z\subseteq V(G)$ such that both $G[Z\cup\\{z\\}]$ and
$G[Z\cup\\{z^{\prime}\\}]$ contain perfect $H$-tilings. Note that

$|A\cap
D|\geq(1-2\varepsilon_{2}r)|W|=(1-2\varepsilon_{2}r)m\stackrel{{\scriptstyle(\ref{hier3})}}{{\geq}}\frac{\eta
n}{6L_{0}},$ $|A^{\prime}\cap
D^{\prime}|\geq(1-2\varepsilon_{2}r)|W^{\prime}|=(1-2\varepsilon_{2}r)m\stackrel{{\scriptstyle(\ref{hier3})}}{{\geq}}\frac{\eta
n}{6L_{0}}.$

Apply Lemma 7.2 to $y$ and any $z\in A\cap D$ with $A^{\prime}\cap
D^{\prime},\eta/({6L_{0}}),\xi_{3},\xi_{4}$ playing the roles of
$A,\alpha,\beta,\gamma$; we conclude that there are at least
${\xi_{4}}n^{3sh-1}$ $(3sh-1)$-sets $X^{\prime}\subseteq V(G)$ such that both
$G[X^{\prime}\cup\\{z\\}]$ and $G[X^{\prime}\cup\\{y\\}]$ contain perfect
$H$-tilings.

Next apply Lemma 7.2 to $x$ and $y$, with $A\cap
D,\eta/({6L_{0}}),\xi_{4},\xi_{5}$ playing the roles of
$A,\alpha,\beta,\gamma$; this yields at least $\xi_{5}n^{4sh-1}$
$(4sh-1)$-sets $X\subseteq V(G)$ such that both $G[X\cup\\{x\\}]$ and
$G[X\cup\\{y\\}]$ contain perfect $H$-tilings, as desired.  $\square$

Observe that, by Claim 10.6, the hypothesis of Theorem 7.1 is satisfied with
$4s$ and $\xi_{5}$ playing the roles of $s$ and $\xi$. Thus, $V(G)$ contains a
set $Abs$ so that

  * •

$|Abs|\leq(\xi_{5}/2)^{h}n/4$;

  * •

$Abs$ is an $H$-absorbing set for any $W\subseteq V(G)\setminus Abs$ such that
$|W|\in h\mathbb{N}$ and $|W|\leq(\xi_{5}/2)^{2h}n/(512s^{2}h^{3})$.

Recall that $\nu=(\xi_{5}/2)^{h}/4$. Therefore we have that $|Abs|\leq\nu n$
and by (7) and (8) we have that $\nu^{3}<(\xi_{5}/2)^{2h}/(512s^{2}h^{3})$; so
$Abs$ is as desired. ∎

###  10.2. Proof of Theorem 1.10

By arguing as in Claim 10.4, we obtain the following result.

######  Theorem 10.7.

Let $H$ be an ordered graph that does not have a local barrier and let
$\eta>0$. There exists an $n_{0}\in\mathbb{N}$ so that the following holds. If
$G$ is an ordered graph on $n\geq n_{0}$ vertices with

$\delta(G)\geq\left(1-\frac{1}{\chi_{<}(H)-1}+\eta\right)n,$

then for any vertex $x\in V(G)$ there exists a copy of $H$ in $G$ covering the
vertex $x$.

###### Proof.

Let $r:=\chi_{<}(H)$. Given such an ordered graph $G$, define constants as in
(7) and (8). As in the proof of Theorem 4.2, apply the regularity lemma, and
then argue as in the proof of Claim 10.4 to obtain the following: given any
$x\in V(G)$, there are disjoint $T^{\prime}_{1},\dots,T^{\prime}_{r}\subseteq
V(G)$ where $|T^{\prime}_{k}|\geq\eta^{2}n/(500L_{0})$ and $i\in[r+1]$,
$j\in[r]$ such that

$T^{\prime}_{1}<\cdots<T^{\prime}_{i-1}<x<T^{\prime}_{i}<\cdots<T^{\prime}_{r};$

$(T^{\prime}_{a},T^{\prime}_{b})$ is $(\varepsilon_{2},d/2)$-regular for every
$a\not=b\in[r]$; $x$ is adjacent to all vertices in $T^{\prime}_{k}$ for any
$k\not=j$.

As $H$ does not have a local barrier, there exists an interval
$(r+1)$-colouring

$V_{1}<\cdots<V_{i-1}<\\{v\\}<V_{i}<\cdots<V_{r}$

of $H$ such that there is no edge between $v$ and $V_{j}$. By the key lemma,
there exists some set $X\subseteq V(G)$ such that $G[X]$ spans a copy of
$H\setminus\\{v\\}$ with $V_{k}\subseteq T^{\prime}_{k}$ for every $k\in[r]$.
Since $x$ is adjacent to all vertices in $T^{\prime}_{k}$ for every $k\not=j$,
$G[X\cup\\{x\\}]$ spans a copy of $H$ in $G$, as desired.  $\square$

We are now ready to prove Theorem 1.10 using Theorem 4.1 and Theorem 10.7.

Proof of Theorem 1.10.  Note that the lower bounds stated in Theorem 1.10
follow immediately from Corollary 2.2 and Lemma 2.5. It remains to prove the
upper bounds.

Let $H$ be an ordered graph and $\eta>0$. Let $G$ be an ordered graph on $n$
vertices with $n$ sufficiently large and minimum degree

  * (i)

$\delta(G)\geq\left(1-\frac{1}{\chi_{<}(H)}+\eta\right)n$ if $H$ has a local
barrier;

  * (ii)

$\delta(G)\geq\left(1-\frac{1}{\chi_{<}(H)-1}+\eta\right)n$ if $H$ does not
have a local barrier.

In case (ii) we obtain an $H$-cover by Theorem 10.7. In case (i), consider any
$x\in V(H)$. Let $y\in V(G)\setminus\\{x\\}$. By Theorem 4.1 there exists a
set $X\subseteq V(G)$ such that both $G[X\cup\\{x\\}]$ and $G[X\cup\\{y\\}]$
contain perfect $H$-tilings. In particular, there exists a copy of $H$ in $G$
covering $x$. Thus, $G$ has an $H$-cover, as desired. ∎

##  11\. Properties of $\chi^{*}_{cr}(H)$

In this section, we provide various bounds on the parameter
$\chi_{cr}^{*}(H)$. We start by showing some natural upper and lower bounds.

######  Proposition 11.1.

Let $H$ be an ordered graph on $h$ vertices and let $r:=\chi_{<}(H)$. Let
$\mathcal{C}$ denote the set of interval $r$-colourings of $H$. Define

$\ell_{-}(H):=\max_{(H_{1}<\cdots<H_{r})\in\mathcal{C}}|H_{1}|\ \ \
\text{and}\ \ \
\ell^{*}_{-}(H):=\max_{(H_{1}<\cdots<H_{r})\in\mathcal{C}}|H_{r}|.$

Then $\chi_{cr}^{*}(H)\geq h/\ell_{-}(H)$ and $\chi_{cr}^{*}(H)\geq
h/\ell^{*}_{-}(H)$.

###### Proof.

We only prove that $\chi_{cr}^{*}(H)\geq h/\ell_{-}(H)$ as the proof that
$\chi_{cr}^{*}(H)\geq h/\ell^{*}_{-}(H)$ is analogous. Let $B$ be a
bottlegraph of $H$ with parts $B_{1},\dots,B_{k}$ for some $k\in\mathbb{N}$.
Our aim is to show that $\chi_{cr}(B)\geq h/\ell_{-}(H)$. By Proposition 5.1,
we may assume there exists some $m\in\mathbb{N}$ such that

$|B_{k}|\leq m\quad\text{and}\quad|B_{i}|=m$

for every $i\in[k-1]$. Let $\phi$ be an interval labelling of $B$ such that
the ordered graph $(B,\phi)$ has parts $B_{1}<\cdots<B_{k}$. Since $B$ is a
bottlegraph, there exists a $t\in\mathbb{N}$ so that $(B(t),\phi)$ contains a
perfect $H$-tiling $\mathcal{H}$. Note $\mathcal{H}$ consists of $|B|t/h$
copies of $H$ and every copy of $H$ has at most $\ell_{-}(H)$ vertices in
$B_{1}$, thus

$mt=|B_{1}|t\leq\ell_{-}(H)|\mathcal{H}|=\ell_{-}(H)|B|t/h.$

Since $\chi_{cr}(B)=|B|/m$, the above implies $\chi_{cr}(B)\geq h/\ell_{-}(H)$
and so $\chi_{cr}^{*}(H)\geq h/\ell_{-}(H).$ $\square$

######  Proposition 11.2.

Let $H$ be an ordered graph on $h$ vertices and let $r:=\chi_{<}(H)$. Let
$\mathcal{C}$ denote the set of interval $r$-colourings of $H$. Define

$\ell_{+}(H):=\max_{(H_{1}<\cdots<H_{r})\in\mathcal{C}}\left\\{\min_{i\in[r]}|H_{i}|\right\\}.$

Then $\chi_{cr}^{*}(H)\leq h/\ell_{+}(H)$.

###### Proof.

Let $H_{1}<\cdots<H_{r}$ be an interval $r$-colouring of $H$ such that

$\ell_{+}(H)=\min_{i\in[r]}|H_{i}|.$

Let $k:=\lfloor h/\ell_{+}(H)\rfloor$ and let $B$ be the complete
$(k+1)$-partite unordered graph with parts $B_{1},\dots,B_{k+1}$ such that

$|B_{k+1}|=(h-k\ell_{+}(H))\cdot(h!)\quad\text{and}\quad|B_{s}|=\ell_{+}(H)\cdot(h!)$

for every $s\in[k]$. Note that $B_{k+1}$ is the smallest part and may be
empty. We have that $|B|=h\cdot h!$ and $\chi_{cr}(B)=h/\ell_{+}(H)$.

We will now prove that $B$ is a simple bottlegraph of $H$. Let $\sigma$ be a
permutation of $[k+1]$ and let $\phi$ be an interval labelling of $B$ with
respect to $\sigma$. Note that $V((B,\phi))=[h\cdot(h!)]$. Set $t_{0}:=0$ and

$t_{i}:=(|H_{1}|+\cdots+|H_{i}|)\cdot(h!)$

for every $i\in[r]$. For every $j\in[h!]$ and $i\in[r]$, let

$T_{j}^{i}:=[t_{i-1}+j|H_{i}|]\setminus[t_{i-1}+(j-1)|H_{i}|].$

Observe that the set of intervals $\\{T_{j}^{i}\\}_{j\in[h!]}$ is a partition
of $[t_{i}]\setminus[t_{i-1}]$ and in particular the set of all intervals
$T_{j}^{i}$ is a partition of $[h\cdot(h!)]$.

Relabel the parts of $(B,\phi)$ by $B^{\prime}_{1},\dots,B^{\prime}_{k+1}$ so
that $B^{\prime}_{1}<\dots<B^{\prime}_{k+1}$. Suppose that $T_{j}^{i}$
intersects both $B^{\prime}_{s}$ and $B^{\prime}_{s+1}$ for some $i\in[r]$,
$j\in[h!]$ and $s\in[k]$. Since $|T_{j^{\prime}}^{i}|=|H_{i}|$ for every
$j^{\prime}\in[h!]$, it follows that

$|(B^{\prime}_{1}\cup\cdots\cup B^{\prime}_{s})\setminus[t_{i-1}]|$

is not divisible by $|H_{i}|$, as otherwise no $T_{j^{\prime}}^{i}$ would
intersect both $B^{\prime}_{s}$ and $B^{\prime}_{s+1}$ for any
$j^{\prime}\in[h!]$, and in particular for $j^{\prime}=j$, contradicting our
assumption. However, $|B^{\prime}_{1}\cup\cdots\cup B^{\prime}_{s}|$ and
$t_{i-1}$ are both divisible by $h!$ and thus $|(B^{\prime}_{1}\cup\cdots\cup
B^{\prime}_{s})\setminus[t_{i-1}]|$ is divisible by $|H_{i}|$, reaching a
contradiction. Therefore, every $T_{j}^{i}$ is a subset of some
$B^{\prime}_{s}$.

Suppose $T_{j}^{i}$ and $T_{j}^{i+1}$ are both subsets of some
$B^{\prime}_{s}$, then

$\displaystyle|B^{\prime}_{s}|$
$\displaystyle\geq(t_{i}+j|H_{i+1}|)-(t_{i-1}+(j-1)|H_{i}|)=(h!-j+1)|H_{i}|+j|H_{i+1}|\geq(h!+1)\cdot\ell_{+}(H),$

again reaching a contradiction. It follows that the ordered graph $T_{j}$
spanned by $T_{j}^{1}<\cdots<T_{j}^{r}$ is a complete $r$-partite ordered
subgraph of $(B,\phi)$. Since $|T_{j}^{i}|=|H_{i}|$ then $T_{j}$ spans a copy
of $H$ in $(B,\phi)$ for every $j\in[h!]$. The $T_{j}$’s are disjoint and
cover all the vertices of $(B,\phi)$, thus they yield a perfect $H$-tiling.
Since $\sigma,\phi$ are arbitrary, $B$ is a simple bottlegraph of $H$. In
particular,

$\chi_{cr}^{*}(H)\leq\chi_{cr}(B)=h/\ell_{+}(H).$

$\square$

The next result follows easily from the previous bounds.

######  Proposition 11.3.

Let $H$ be a complete $r$-partite ordered graph on $h$ vertices with parts
$H_{1}<\cdots<H_{r}$ such that (i) $|H_{1}|\leq|H_{i}|$ for every $i\in[r]$ or
(ii) $|H_{r}|\leq|H_{i}|$ for every $i\in[r]$. Then
$\chi_{cr}^{*}(H)=h/|H_{1}|\geq\chi_{<}(H)$ in case (i) and
$\chi_{cr}^{*}(H)=h/|H_{r}|\geq\chi_{<}(H)$ in case (ii).

###### Proof.

For case (i), let $\ell_{-}(H)$ and $\ell_{+}(H)$ be as in Proposition 11.1
and Proposition 11.2 respectively. Note that
$\ell_{-}(H)=\ell_{+}(H)=|H_{1}|$, hence Propositions 11.1 and 11.2 imply that
$\chi_{cr}^{*}(H)=h/|H_{1}|$. Case (ii) follows similarly.  $\square$

In [3], Balogh, Li and the second author (implicitly) computed
$\chi_{cr}^{*}(H)$ for any $H$ such that $\chi_{<}(H)=2$. Their result can be
easily recovered using Propositions 11.1 and 11.2.

######  Proposition 11.4 (Balogh, Li and Treglown [3]).

Let $H$ be an ordered graph with vertex set $[h]$ such that $\chi_{<}(H)=2$.
Define $\alpha^{+}(H)$ to be the largest integer $t\in[h]$ so that $[1,t]$ is
an independent set in $H$; $\alpha^{-}(H)$ to be the largest integer $t\in[h]$
so that $[h-t+1,h]$ is an independent set in $H$;
$\alpha(H):=\min\\{\alpha^{+}(H),\alpha^{-}(H)\\}$. Then

$\chi_{cr}^{*}(H)=\frac{h}{\alpha(H)}.$

###### Proof.

Let $\ell_{-}(H),\ell_{-}^{*}(H),\ell_{+}(H)$ be as in Propositions 11.1 and
11.2.

Observe that both $[1,\alpha^{+}(H)]<[\alpha^{+}(H)+1,h]$ and
$[1,h-\alpha^{-}(H)]<[h-\alpha^{-}(H)+1,h]$ are interval $2$-colourings of
$H$. In particular,

$\ell_{-}(H)=\alpha^{+}(H)\quad\text{and}\quad\ell_{-}^{*}(H)=\alpha^{-}(H),$

and so $\chi_{cr}^{*}(H)\geq h/\alpha(H)$ by Proposition 11.1. It remains to
show that $\chi_{cr}^{*}(H)\leq h/\alpha(H)$. If $\alpha(H)\leq h/2$ then
$\ell_{+}(H)\geq\alpha(H)$444In fact, if $\alpha(H)\leq h/2$ then
$\ell_{+}(H)=\alpha(H)$. and so $\chi_{cr}^{*}(H)\leq h/\alpha(H)$ by
Proposition 11.2. If $\alpha(H)>h/2$, then both
$[1,\alpha(H)]<[\alpha(H)+1,h]$ and $[1,h-\alpha(H)]<[h-\alpha(H)+1,h]$ are
interval $2$-colourings of $H$. Therefore the complete bipartite graph $B$
with parts $U,V$ of size $|U|=\alpha(H)$ and $|V|=h-\alpha(H)$ is a simple
bottlegraph of $H$. We have $\chi_{cr}(B)=h/\alpha(H)$ and thus
$\chi_{cr}^{*}(H)\leq h/\alpha(H)$.  $\square$

If $\chi_{<}(H)=3$, finding a closed formula for $\chi_{cr}^{*}(H)$ already
proves challenging. In the next result we determine $\chi_{cr}^{*}(H)$ for any
complete $3$-partite ordered graph $H$.

######  Proposition 11.5.

Let $H$ be a complete $3$-partite ordered graph on $h$ vertices with parts
$H_{1}<H_{2}<H_{3}$ of size $h_{1},h_{2},h_{3}$ respectively and let

$g(H):=\left(2-\frac{\min\\{h_{1},h_{2},h_{3}\\}}{\min\\{h_{1},h_{3}\\}}\right)\cdot\frac{h}{\min\\{h_{1},h_{3}\\}}.$

Then $\chi^{*}_{cr}(H)=g(H)$.

###### Proof.

We may assume that $h_{1}\leq h_{3}$; the case $h_{1}\geq h_{3}$ follows by
the symmetry of the argument. If $h_{1}\leq h_{2}$ then
$\chi_{cr}^{*}(H)=h/h_{1}$ by Proposition 11.3 and the result follows. So for
the rest of the proof we assume $h_{2}<h_{1}\leq h_{3}$. Under these
assumptions, $g(H)=(2-h_{2}/h_{1})h/h_{1}>3$.

######  Claim 11.6.

$\chi_{cr}^{*}(H)\geq g(H)$.

Let $B$ be a bottlegraph of $H$ with parts $B_{1},\dots,B_{k}$ for some
$k\in\mathbb{N}$. Note that $k\geq 3$ since $H$ is $3$-partite. Our aim is to
show that $\chi_{cr}(B)\geq g(H)$. By Proposition 5.1, we may assume that
there exists some $m\in\mathbb{N}$ such that

$|B_{k}|\leq m\quad\text{and}\quad|B_{i}|=m$

for every $i\in[k-1]$. Pick an interval labelling $\phi$ of $B$ such that the
ordered graph $(B,\phi)$ has parts $B_{1}<B_{2}<\cdots<B_{k}$. By definition
there exists some $t\in\mathbb{N}$ such that the ordered blow-up $(B(t),\phi)$
contains a perfect $H$-tiling $\mathcal{M}$. Recall that we denote the parts
of $(B(t),\phi)$ by $B_{1}(t)<\cdots<B_{k}(t)$.

Let $\mathcal{M}_{1}$ be the set of copies of $H\in\mathcal{M}$ whose first
part $H_{1}$ lies completely in $B_{1}(t)$ and let
$\mathcal{M}_{2}:=\mathcal{M}\setminus\mathcal{M}_{1}$. Note that every copy
of $H\in\mathcal{M}_{1}$ has exactly $h_{1}$ vertices in $B_{1}(t)$ and at
most $h_{1}+h_{2}$ vertices in $B_{1}(t)\cup B_{2}(t)$, while every copy of
$H\in\mathcal{M}_{2}$ has at most $h_{1}$ vertices in $B_{1}(t)\cup B_{2}(t)$.
Since $|B_{1}(t)|=|B_{2}(t)|=mt$, it follows that

$mt\geq h_{1}\cdot|\mathcal{M}_{1}|\quad\text{and}\quad
2mt\leq(h_{1}+h_{2})\cdot|\mathcal{M}_{1}|+h_{1}\cdot|\mathcal{M}_{2}|.$

The above implies that

$|\mathcal{M}|=|\mathcal{M}_{1}|+|\mathcal{M}_{2}|\geq\left(2-\frac{h_{2}}{h_{1}}\right)\frac{mt}{h_{1}}.$

Since $\chi_{cr}(B)=|B|/m=|\mathcal{M}|h/(mt)$ then $\chi_{cr}(B)\geq g(H)$,
proving the claim.

######  Claim 11.7.

If $h_{1}=h_{3}$ then there exists a simple bottlegraph $B$ of $H$ with four
parts such that three parts of $B$ have size $h_{1}^{2}$; one part has size
$h_{1}^{2}-h_{2}^{2}$; $\chi_{cr}(B)=g(H)$.

Suppose $h_{1}=h_{3}$. Then

$g(H)=\left(2-\frac{h_{2}}{h_{1}}\right)\frac{h}{h_{1}}=4-\left(\frac{h_{2}}{h_{1}}\right)^{2}$

and so $3<g(H)<4$. Let $B$ be the complete $4$-partite graph with parts
$B_{1},B_{2},B_{3},B_{4}$ where

$|B_{1}|=h_{1}^{2}-h_{2}^{2}\quad\text{and}\quad|B_{i}|=h_{1}^{2}$

for every $i=2,3,4$. Note that $\chi_{cr}(B)=|B|/h_{1}^{2}=g(H)$. It remains
to show that $B$ is a simple bottlegraph of $H$.

Let $\sigma$ be a permutation of $[4]$ and $\phi$ an interval labelling of $B$
with respect to $\sigma$. Recall that the ordered graph $(B,\phi)$ has parts
$B_{\sigma^{-1}(1)}<B_{\sigma^{-1}(2)}<B_{\sigma^{-1}(3)}<B_{\sigma^{-1}(4)}$.
Either $\sigma^{-1}(1),\sigma^{-1}(2)\neq 1$ or
$\sigma^{-1}(3),\sigma^{-1}(4)\neq 1$. We will now deal with the former case.

Observe that $V(B)$ can be partitioned into two sets $X,Y$ of size
$|X|=h_{1}(2h_{1}+h_{2})$ and $|Y|=(h_{1}-h_{2})(2h_{1}+h_{2})$ such that

$|Y\cap B_{\sigma^{-1}(i)}|=\begin{cases}0&\text{if $i=1$,}\\\
h_{1}(h_{1}-h_{2})&\text{if $i=2$,}\\\ h_{2}(h_{1}-h_{2})&\text{if $i=3$,}\\\
h_{1}(h_{1}-h_{2})&\text{if $i=4$,}\end{cases}$

and

$|X\cap B_{\sigma^{-1}(i)}|=\begin{cases}h_{1}^{2}&\text{if $i=1$,}\\\
h_{1}h_{2}&\text{if $i=2$,}\\\
|B_{\sigma^{-1}(3)}|-h_{1}h_{2}+h_{2}^{2}&\text{if $i=3$,}\end{cases}$

and all remaining vertices of $X$ lie in $B_{\sigma^{-1}(4)}$.

In particular, (i) $|X\cap B_{\sigma^{-1}(1)}|=h^{2}_{1}$; $|X\cap
B_{\sigma^{-1}(2)}|=h_{1}h_{2}$; $|X\cap
B_{\sigma^{-1}(3)}|=h_{1}^{2}-h_{1}h_{2}+h_{2}^{2}$; $|X\cap
B_{\sigma^{-1}(4)}|=h_{1}h_{2}-h^{2}_{2}$ or (ii) $|X\cap
B_{\sigma^{-1}(1)}|=h^{2}_{1}$; $|X\cap B_{\sigma^{-1}(2)}|=h_{1}h_{2}$;
$|X\cap B_{\sigma^{-1}(3)}|=h_{1}^{2}-h_{1}h_{2}$; $|X\cap
B_{\sigma^{-1}(4)}|=h_{1}h_{2}.$ Thus, we have that $(B,\phi)[X]$ contains a
perfect $H$-tiling consisting of $h_{1}$ copies of $H$ where the first and
second parts $H_{1}$, $H_{2}$ of every such copy of $H$ lie in
$B_{\sigma^{-1}(1)}$ and $B_{\sigma^{-1}(2)}$ respectively. Further,
$(B,\phi)[Y]$ contains a perfect $H$-tiling consisting of $h_{1}-h_{2}$ copies
of $H$. The union of these two $H$-tilings yields a perfect $H$-tiling in
$(B,\phi)$.

The only remaining case is when $\sigma^{-1}(3),\sigma^{-1}(4)\neq 1$.
However, since $h_{1}=h_{3}$, this case will follow by a symmetric argument to
that of the previous case. Thus $B$ is a simple bottlegraph of $H$.

######  Claim 11.8.

If $g(H)$ is an integer then there exists a simple bottlegraph $B$ of $H$ such
that $\chi_{cr}(B)=g(H)$ (i.e., $B$ has $g(H)$ parts) and all parts of $B$
have size $h_{1}^{2}$.

Set $k:=g(H)$. Recall that $k>3$ and so $k\geq 4$ since $k\in\mathbb{N}$. Let
$B$ be the complete $k$-partite graph with parts $B_{1},\dots,B_{k}$ all of
size $h_{1}^{2}$. Notice $\chi_{cr}(B)=k$, so it remains to show that $B$ is a
simple bottlegraph of $H$.

Let $\sigma$ be a permutation of $[k]$ and $\phi$ an interval labelling of $B$
with respect to $\sigma$. Recall that the ordered graph $(B,\phi)$ has parts
$B_{\sigma^{-1}(1)}<\cdots<B_{\sigma^{-1}(k)}$. Let $X\subseteq V(B)$ be a set
of size $4h_{1}^{2}-h_{2}^{2}$ such that

$|X\cap B_{\sigma^{-1}(i)}|=\begin{cases}h_{1}^{2}&\text{if $i=1,2,3$},\\\
h_{1}^{2}-h_{2}^{2}&\text{if $i=4$}.\end{cases}$

Let $H^{\prime}$ be the complete $3$-partite ordered graph with parts
$H^{\prime}_{1}<H^{\prime}_{2}<H^{\prime}_{3}$ of size $h_{1},h_{2},h_{1}$
respectively. By Claim 11.7, $(B,\phi)[X]$ contains a perfect
$H^{\prime}$-tiling consisting of $2h_{1}-h_{2}$ copies of $H^{\prime}$.
Observe that by definition of $k$,

$|V(B)\setminus
X|=kh_{1}^{2}-(4h_{1}^{2}-h_{2}^{2})=(2h_{1}-h_{2})(h_{3}-h_{1}).$

Thus we can partition $V(B)\setminus X$ into $2h_{1}-h_{2}$ sets of size
$h_{3}-h_{1}$ and assign each set to a copy of $H^{\prime}$. Notice that every
copy of $H^{\prime}$ together with its assigned set forms a copy of $H$; so we
constructed a perfect $H$-tiling in $(B,\phi)$. Since $\sigma$ and $\phi$ are
arbitrary, $B$ is a simple bottlegraph of $H$.

######  Claim 11.9.

There exists a simple bottlegraph $B$ of $H$ such that $\chi_{cr}(B)=g(H)$.

Recall that $h_{2}<h_{1}\leq h_{3}$. We may assume that $g(H)$ is not an
integer as otherwise we are done by Claim 11.8. Given $t\in\mathbb{N}$ and
$\ell\in\mathbb{N}\cup\\{0\\}$, let $H(t,\ell)$ be the complete $3$-partite
ordered graph with parts $H^{\prime}_{1}<H^{\prime}_{2}<H^{\prime}_{3}$ of
size $th_{1},th_{2},th_{3}-\ell$ respectively.

Set $k:=\lfloor g(H)\rfloor$. We define $t,\ell,s$ and $B$ as follows:

  * •

If $g(H)\geq 4$, there exist $t,\ell\in\mathbb{N}$ such that

$\frac{\ell}{t}=\frac{(g(H)-k)h_{1}}{\left(2-{h_{2}}/{h_{1}}\right)},$

since the right hand side of the above inequality is a positive rational
number. Thus,

(15) $\displaystyle
k=g(H)-\left(2-\frac{h_{2}}{h_{1}}\right)\frac{\ell/t}{h_{1}}=\left(2-\frac{h_{2}}{h_{1}}\right)\frac{h-\ell/t}{h_{1}}=\left(2-\frac{th_{2}}{th_{1}}\right)\frac{th_{1}+th_{2}+th_{3}-\ell}{th_{1}}.$

Furthermore, we have

(16) $\displaystyle k\geq
4>4-\left(\frac{h_{2}}{h_{1}}\right)^{2}=\left(2-\frac{th_{2}}{th_{1}}\right)\frac{th_{1}+th_{2}+th_{1}}{th_{1}}.$

Equations (15) and (16) imply that $th_{3}-\ell>th_{1}$. Hence
$th_{2}<th_{1}<th_{3}-\ell$ and so

$g(H(t,\ell))=\left(2-\frac{th_{2}}{th_{1}}\right)\frac{th_{1}+th_{2}+th_{3}-\ell}{th_{1}}=k.$

Let $B$ be the simple bottlegraph of $H(t,\ell)$ as in Claim 11.8 and set
$s:=0$.

  * •

If $3<g(H)<4$, let $t:=1$ and $\ell:=h_{3}-h_{1}$. Observe that the parts
$H^{\prime}_{1}<H^{\prime}_{2}<H^{\prime}_{3}$ of $H(t,\ell)$ have size
$h_{1},h_{2},h_{1}$ respectively. Let $B$ be the simple bottlegraph of
$H(t,\ell)$ as in Claim 11.7. Set $s:=h_{1}^{2}-h_{2}^{2}$.

Note that in both cases, $B$ is a complete $(k+1)$-partite graph where each
part has size $(th_{1})^{2}$ except one smaller part of size $t^{2}s$ (which
is empty if $g(H)\geq 4$).

Observe that $g(H)-k$ is a rational number and

(17) $\displaystyle\frac{s}{h_{1}^{2}}\leq g(H)-k<1.$

Indeed, the lower bound is trivial if $g(H)\geq 4$; if $3<g(H)<4$ then
$s=h^{2}_{1}-h^{2}_{2}$ and $k=3$, so
$g(H)-k\geq(2-h_{2}/h_{1})(2h_{1}+h_{2})/h_{1}-k=4-(h_{2}/h_{1})^{2}-3=1-(h_{2}/h_{1})^{2}=s/h^{2}_{1}$.

Thus, by (17), there exist $a,b\in\mathbb{N}\cup\\{0\\}$ such that
$(a,b)\not=(0,0)$ and

$a(1-g(H)+k)=b(g(H)-k-s/h^{2}_{1})\implies
a+b\frac{s}{h_{1}^{2}}=(a+b)(g(H)-k)$ (18) $\displaystyle\implies
a(th_{1})^{2}+bt^{2}s=(a+b)(th_{1})^{2}(g(H)-k).$

Let $B^{\prime}$ be the complete $(k+1)$-partite graph with parts
$B^{\prime}_{1},\dots,B^{\prime}_{k+1}$ where

$|B^{\prime}_{1}|=(a+b)(th_{1})^{2}(g(H)-k)\quad\text{and}\quad|B^{\prime}_{i}|=(a+b)(th_{1})^{2}$

for every $i>1$. Notice $\chi_{cr}(B^{\prime})=g(H)$, so it remains to show
that $B^{\prime}$ is a simple bottlegraph of $H$.

Let $\sigma$ be a permutation of $[k+1]$ and let $\phi$ be an interval
labelling of $B^{\prime}$ with respect to $\sigma$. Recall that the ordered
graph $(B^{\prime},\phi)$ has parts
$B^{\prime}_{\sigma^{-1}(1)}<\cdots<B^{\prime}_{\sigma^{-1}(k+1)}$. Let $X,Y$
be two disjoint sets in $V(B^{\prime})$ of size $a|B|$ and $b|B|$ respectively
such that

$|X\cap B^{\prime}_{\sigma^{-1}(i)}|=\begin{cases}a(th_{1})^{2}&\text{if
$i<k+1$},\\\ a(t^{2}s)&\text{if $i=k+1$},\end{cases}$

and

$|Y\cap B^{\prime}_{\sigma^{-1}(i)}|=\begin{cases}b(th_{1})^{2}&\text{if
$\sigma^{-1}(i)\not=1$},\\\ b(t^{2}s)&\text{if
$\sigma^{-1}(i)=1$}.\end{cases}$

Notice that by (18) and the choice of the sizes of the parts of $B^{\prime}$,
all vertices in $B^{\prime}_{\sigma^{-1}(i)}$ are in $X\cup Y$ for $i\leq k$;
as $s\leq h^{2}_{1}$ it may be that some vertices in
$B^{\prime}_{\sigma^{-1}(k+1)}$ are not in $X\cup Y$.

Note that $(B^{\prime},\phi)[X]$ is a copy of $(B(a),\phi^{\prime})$ for some
interval labelling $\phi^{\prime}$. So as $B$ is a simple bottlegraph of
$H(t,\ell)$, $(B(a),\phi^{\prime})$ contains a perfect $H(t,\ell)$-tiling
$\mathcal{M}_{1}$ consisting of

(19)
$\displaystyle\frac{a|B|}{|H(t,\ell)|}=\frac{a(th_{1})^{2}g(H(t,\ell))}{|H(t,\ell)|}=a(th_{1})^{2}\left(2-\frac{h_{2}}{h_{1}}\right)\frac{h-\ell/t}{h_{1}}\frac{1}{th-\ell}=a(2h_{1}-h_{2})t$

copies of $H(t,\ell)$. Similarly, $(B^{\prime},\phi)[Y]$ is a copy of
$(B(b),\phi^{\prime\prime})$ for some interval labelling $\phi^{\prime\prime}$
and it contains a perfect $H(t,\ell)$-tiling $\mathcal{M}_{2}$ consisting of

(20) $\displaystyle\frac{b|B|}{|H(t,\ell)|}=b(2h_{1}-h_{2})t$

copies of $H(t,\ell)$. Note that the vertices in $V(B^{\prime})\setminus(X\cup
Y)$ lie in $B^{\prime}_{\sigma^{-1}(k+1)}$. Moreover, as
$g(H)=(2-h_{2}/h_{1})h/h_{1}$,

$\displaystyle|V(B^{\prime})\setminus(X\cup Y)|$
$\displaystyle=|B^{\prime}|-(a+b)|B|=(a+b)(th_{1})^{2}g(H)-(a+b)|B|$
$\displaystyle\stackrel{{\scriptstyle(\ref{new4}),(\ref{new5})}}{{=}}(a+b)\left((2h_{1}-h_{2})ht^{2}-(2h_{1}-h_{2})(th-\ell)t\right)=(a+b)(2h_{1}-h_{2})\ell
t.$

Thus, we can divide $V(B^{\prime})\setminus(X\cup Y)$ into
$(a+b)(2h_{1}-h_{2})t$ sets of size $\ell$ and assign each set to a copy of
$H(t,\ell)$ in $\mathcal{M}_{1}\cup\mathcal{M}_{2}$. Note that each copy of
$H(t,\ell)$ together with its assigned set forms a copy of $H(t,0)$. Thus we
constructed a perfect $H(t,0)$-tiling in $(B^{\prime},\phi)$. Since
$H(t,0)=H(t)$, this yields a perfect $H$-tiling in $(B^{\prime},\phi)$,
proving that $B^{\prime}$ is indeed a simple bottlegraph of $H$.

Claim 11.9 implies that $\chi_{cr}^{*}(H)\leq g(H)$. Together with Claim 11.6,
this concludes the proof.  $\square$

Observe that Propositions 11.3 and 11.5 combined with Theorem 1.8 yield the
following result which makes the threshold in Theorem 1.8 explicit for all
complete $3$-partite ordered graphs.

######  Theorem 11.10.

Let $H$ be a complete $r$-partite ordered graph on $h$ vertices with parts
$H_{1}<\cdots<H_{r}$ where $|H_{i}|=h_{i}$ for every $i\in[r]$.

  * •

If $h_{1}\leq h_{i}$ for every $i>1$, then
$\delta_{<}(H,n)=\left(1-\frac{h_{1}}{h}+o(1)\right)n.$

  * •

If $h_{r}\leq h_{i}$ for every $i\in[r-1]$, then
$\delta_{<}(H,n)=\left(1-\frac{h_{r}}{h}+o(1)\right)n.$

  * •

If $r=3$ and $h_{2}\leq h_{1}\leq h_{3}$ then
$\delta_{<}(H,n)=\left(1-\frac{h_{1}^{2}}{(2h_{1}-h_{2})h}+o(1)\right)n.$

  * •

If $r=3$ and $h_{2}\leq h_{3}\leq h_{1}$ then
$\delta_{<}(H,n)=\left(1-\frac{h_{3}^{2}}{(2h_{3}-h_{2})h}+o(1)\right)n.$

##  12\. The tightness of Theorem 1.6

In this section we show that the minimum degree condition in Theorem 1.6 is
best possible. Given an ordered graph $H$, let $c_{<}(H)$ denote the smallest
non-negative number which satisfies the following: for every $\eta>0$, there
exists an integer $n_{0}\in\mathbb{N}$ such that if $G$ is an ordered graph on
$n\geq n_{0}$ vertices and with minimum degree $\delta(G)\geq c_{<}(H)n$ then
$G$ contains an $H$-tiling covering all but at most $\eta n$ vertices. Observe
Theorem 1.6 immediately implies that

(21) $\displaystyle c_{<}(H)\leq\left(1-\frac{1}{\chi^{*}_{cr}(H)}\right).$

In fact, we will show that equality holds.

######  Theorem 12.1.

Let $H$ be an ordered graph on $h$ vertices. Then

$c_{<}(H)=\left(1-\frac{1}{\chi^{*}_{cr}(H)}\right).$

###### Proof.

By (21) it remains to prove that $c_{<}(H)\geq(1-{1}/{\chi^{*}_{cr}(H)}).$