# Ordered graphs of bounded twin-width

Pierre Simon and Szymon Toruńczyk

###### Abstract

We consider hereditary classes of graphs equipped with a total order. We
provide multiple equivalent characterisations of those classes which have
bounded twin-width. In particular, we prove that those are exactly the classes
which avoid certain large grid-like structures and induced substructures. From
this we derive that the model-checking problem for first-order logic is fixed-
parameter tractable over a hereditary class of ordered graphs if, and – under
common complexity-theoretic assumptions – only if the class has bounded twin-
width. We also show that bounded twin-width is equivalent to the NIP property
from model theory, as well as the smallness condition from enumerative
combinatorics. We prove the existence of a gap in the growth of hereditary
classes of ordered graphs. Furthermore, we prove a grid theorem which applies
to all monadically NIP classes of structures (ordered or unordered), or
equivalently, classes which do not transduce the class of all finite graphs.

##  1 Introduction

The recently introduced notion of twin-width [BKTW20a, BGK+, BGK+20] is a
graph width parameter with remarkable properties. It measures how well a given
graph can be recursively decomposed into parts which have simple interactions
with each other (see Sec. 2 for a definition). The notion generalizes to
arbitrary relational structures equipped with unary and binary relations.

Many well-studied classes have bounded twin-width: the class of planar graphs,
and more generally, any class of graphs excluding a fixed minor; the class of
cographs and more generally, any class of bounded cliquewidth; posets of
bounded width; and classes of permutations (viewed as sets with two total
orders) omitting a fixed permutation as an induced substructure. Moreover,
classes of bounded twin-width enjoy good properties of combinatorial,
algorithmic, and logical nature. For instance, classes of bounded twin-width
are closed under first-order transductions, are small (contain $n!\cdot
2^{\mathcal{O}(n)}$ distinct labelled graphs on $n$ vertices), and are
$\chi$-bounded (the chromatic number can be bounded in terms of the clique
number) [BGK+]. Furthermore, it is shown that model-checking first-order logic
is fixed-parameter tractable on classes of bounded twin-width, assuming the
input graph $G$ is given _together with a certificate_ of having bounded twin-
width (a certain sequence of operations). More precisely, given a first-order
sentence $\varphi$, a graph $G$, and a certificate that $G$ has twin-width at
most $d$, there is an algorithm which determines whether $G$ satisfies
$\varphi$ in time $f(\varphi,d)\cdot|V(G)|^{c}$ for some computable function
$f\colon\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ and fixed constant
$c\in\mathbb{N}$.

For each of the classes $\mathscr{C}$ mentioned above there is an algorithm
which, given a graph $G\in\mathscr{C}$, computes some certificate that $G$ has
twin-width bounded by a constant, in polynomial time [BKTW20a]. Hence, for
each of those classes $\mathscr{C}$, model-checking first-order logic is
fixed-parameter tractable, generalizing many previous results.

The appropriate certificate of having bounded twin-width is usually obtained
from a suitable ordering of the vertices. The adjacency matrix of the graph
with respect to this order should be simple in a certain sense. The existence
of such an order is essential in proving results about classes of bounded
twin-width, as well as obtaining efficient algorithms. This suggests that
_ordered graphs_ of bounded twin-width are the more fundamental object.

### Main result

We solve a number of problems which are open for graphs of bounded twin-width,
in the case of ordered graphs of bounded twin-width. Among other things, we
show that if a class $\mathscr{C}$ of ordered graphs has bounded twin-width,
then for each $G\in\mathscr{C}$, a certificate that $G$ has twin-width bounded
by a constant can be computed in polynomial time. Consequently, model-checking
is fixed-parameter tractable on $\mathscr{C}$. We also prove that the converse
holds, under common complexity-theoretic assumptions.

More importantly, we give multiple characterisations of classes of ordered
graphs of bounded twin-width, connecting notions from various areas of
mathematics and theoretical computer science, and solving several open
problems on the way.

The most tangible characterisation is in terms of certain forbidden
substructures, dubbed _semigrids_. Those are two-dimensional variations of
half-graphs, matchings, and complements of matchings which are depicted in
Fig. 1. Say that two sets $X,Y$ of vertices of an ordered graph $G$ _form an
$R$-graph_, where $R\in\\{\leqslant,\geqslant,=,\neq\\}$, if the $i$th
smallest element in $X$ is adjacent to the $j$th smallest element in $Y$ if
and only if $iRj$, for all $1\leqslant i,j\leqslant|X|$, see Fig. 1.

Figure 1: A $\leqslant$-graph, a $\geqslant$-graph, a $=$-graph, and a
$\neq$-graph formed by sets $X$ (six vertices on the top) and $Y$ (six
vertices on the bottom), where $X$ and $Y$ are both ordered from left to
right. Note that the edges within $X$ and within $Y$ may be arbitrary.

An $m\times n$ _semigrid of type $R\in\\{\leqslant,\geqslant,=,\neq\\}$_ is an
ordered graph $G=(V,E,\leqslant)$ whose domain $V$ can be partitioned into
$m+1$ disjoint intervals (with respect to the order $\leqslant$ on $V$)
$I_{0},I_{1},\ldots,I_{m}$ with $n+1$ elements each and $I_{1}<\ldots<I_{m}$,
such that $I_{0}$ and $I_{i}$ form an $R$-graph, for $i=1,\ldots,m$ (cf. Fig.
2).

Figure 2: A $5\times 5$-semigrid of type $\geqslant$. The vertices are ordered
left to right in each interval.

Note that there are many $m\times n$-semigrids of a given type, as the above
specification is not complete: the adjacencies within $I_{1}\cup\cdots\cup
I_{m}$, as well as the adjacencies within $I_{0}$, and also the relative order
between the interval $I_{0}$ and the intervals $I_{1},\ldots,I_{m}$, are all
left unspecified. However, using a Ramsey argument one can prove that a large
_regular_ $n\times n$-semigrid can be found as an induced substructure of a
sufficiently large semigrid $n^{\prime}\times n^{\prime}$ (see Section 4 for a
definition). In particular, a regular $m\times n$-semigrid is uniquely
specified by the dimensions $m,n\geqslant 1$ and one of $256$ _schemes_.

Another characterisation is in terms of (simple first-order)
_interpretations_. Interpretations are a means of producing new structures out
of old ones, using formulas. The new structure has the same domain as the old
one (or its subset defined by a formula $\delta(x)$) while each of its
relations is defined by a formula $\varphi(x,y)$ interpreted in the old
structure. For example, there is an interpretation which transforms a given
graph $G$ into its edge-complement (using the formula $\neg E(x,y)$), and an
interpretation which transforms $G$ into its square (using the formula
$\exists z.E(x,z)\land E(z,y)$). Transductions are a similar notion, but
additionally allow to arbitrarily color the old structure before applying the
interpretation and then use the colors in the formulas. Say that $\mathscr{C}$
_interprets_ the class of all graphs if there is an interpretation $I$ such
that every (finite) graph $G$ can be obtained as the result of $I$ applied to
some structure in $\mathscr{C}$. Replacing interpretations with transductions,
we say that $\mathscr{C}$ _transduces_ the class of all graphs. It is known
that no class of bounded twin-width transduces all graphs.

We may now state our main result, concerning classes of ordered graphs which
are _hereditary_ , that is, closed under taking induced substructures. Among
others, it provides a dichotomy result for all such classes: either they have
bounded twin-width, and are therefore very well-behaved, or otherwise, they
contain arbitrarily large regular $n\times n$-semigrids, and are then
untamable.

######  Theorem 1.1.

The following conditions are equivalent for a hereditary class $\mathscr{C}$
of finite, ordered graphs:

  1. 1.

$\mathscr{C}$ has bounded twin-width,

  2. 2.

$\mathscr{C}$ does not contain arbitrarily large regular $n\times
n$-semigrids,

  3. 3.

$\mathscr{C}$ does not interpret the class of all graphs,

  4. 4.

$\mathscr{C}$ does not transduce the class of all graphs,

  5. 5.

model-checking first-order logic is fixed-parameter tractable on $\mathscr{C}$
(assuming $\mathrm{FPT\neq AW[\ast]}$),

  6. 6.

$\mathscr{C}$ contains at most $2^{\mathcal{O}(n)}$ structures with $n$
elements, up to isomorphism,

  7. 7.

$\mathscr{C}$ contains fewer than $\lfloor\frac{n}{3}\rfloor!$ structures with
$n$ elements, up to isomorphism,

  8. 8.

there are $k,t\in\mathbb{N}$ such that for all $G\in\mathscr{C}$, if the
adjacency matrix of $G$ is cut into $t^{2}$ zones using $t-1$ vertical and
$t-1$ horizontal lines, then there is a zone with no more than $k$ non-
identical rows and no more than $k$ non-identical columns.

The above result connects notions from logic, enumerative combinatorics,
parameterized complexity, graph theory and matrix theory. However, at the core
of our approach are tools and ideas originating from _model theory_.

As our second main result, we provide further characterisations of bounded
twin-width classes in terms of notions which originate from model theory, but
which also transpire in algorithmic and structural graph theory. We prove that
generalizations of the conditions (2), (3), and (8) hold for arbitrary
_monadically NIP classes_ $\mathscr{C}$ of relational structures. Those can be
equivalently characterised as classes (of finite or infinite structures) which
do not transduce the class of all finite graphs. They include all graph
classes of bounded twin-width (with or without an order), but also all
transductions of nowhere-dense classes (see below).

The following theorem is a vast generalization of some of the key implications
in Theorem 1.1.

######  Theorem 1.2.

For any class of structures $\mathscr{C}$, consider the following statements:

  1. 9.

$\mathscr{C}$ does not transduce the class of all graphs,

  2. 10.

$\mathscr{C}$ is monadically NIP,

  3. 11.

$\mathscr{C}$ does not define large grids (cf. Def. 4),

  4. 12.

$\mathscr{C}$ is $1$-dimensional (cf. Def. 12),

  5. 13.

$\mathscr{C}$ is a regular class (cf. Def. 13).

Then the implications
$\eqref{qit:trans}\leftrightarrow\eqref{qit:mNIP}\rightarrow\eqref{qit:grids}\rightarrow\eqref{qit:1-dim}\rightarrow\eqref{qit:regular}$
hold. For classes of binary, ordered structures, the above conditions are all
equivalent to:

  1. 14.

the class of all finite induced substructures of structures in $\mathscr{C}$
has bounded twin-width,

  2. 15.

the class of all finite induced substructures of structures in $\mathscr{C}$
is NIP.

The notion (11) of defining large grids generalizes the notion (2) of
containing large semigrids to arbitrary structures, while the notion (13) of
regularity generalizes condition (8) from Theorem 1.1. In particular, those
notions do not require the structures to be ordered, finite, or binary. The
notion of 1-dimensionality has a somewhat geometric flavor. It is defined in
terms of a variant of forking independence – a central concept in stability
theory, generalizing e.g. independence in vector spaces or algebraic
independence.

Theorem 1.2 provides a key ingredient in our proof of Theorem 1.1 – a _grid
theorem_. More importantly, we believe that it may be of independent interest,
and possibly of broader applicability than just in the context of ordered
structures. For example, by Theorem 1.2, all graph classes of bounded twin-
width (without an order) and all interpretations of _nowhere-dense_ classes
[NOdM11] are regular.

The implications (11)$\rightarrow$(12)$\rightarrow$(13) are proved using
model-theoretic tools. They yield a general grid theorem for classes that are
not regular in the sense of (13).

Very roughly, the proof of Theorem 1.1 can be summarized as follows. The goal
is to show that if $\mathscr{C}$ is a class of ordered graphs which has
unbounded twin-width, then $\mathscr{C}$ contains arbitrarily large regular
semigrids. We do it in the following steps:

  1. 1.

If a class $\mathscr{C}$ of ordered graphs satisfies condition (8) then it has
bounded twin-width. This generalizes a result from [BKTW20a], and uses similar
methods.

  2. 2.

Suppose $\mathscr{C}$ has unbounded twin-width; then it fails condition (8)
and in particular, is not regular. By Theorem 1.2, $\mathscr{C}$ defines large
grids.

  3. 3.

Large grids are then made more structured using a Ramsey result in order to
exhibit arbitrarily large regular semigrids in $\mathscr{C}$.

Once $\mathscr{C}$ is known to have large regular semigrids, conditions
(3)-(7) in Theorem 1.1 are easily shown to fail.

Some parts of our proof are ineffective, in particular, we use the compactness
theorem for first-order logic. Quite remarkably, we are still able to derive
effective bounds and algorithms. For instance, we get a polynomial-time
algorithm approximating the twin-width of a given ordered graph $G$:

######  Theorem 1.3.

There is a computable function $f\colon\mathbb{N}\to\mathbb{N}$ and an
algorithm which inputs an ordered graph $G$, and computes in polynomial time a
certificate that $G$ has twin-width at most $f(\textrm{twin-width}(G))$.

This, combined with the result of [BKTW20b] yields fixed-parameter
tractability of the model-checking problem for classes of ordered graphs of
bounded twin-width, proving the implication (1)$\rightarrow$(5). We also prove
the converse implication, under the common complexity-theoretic assumption
FPT$\neq$AW[$\ast$].

Theorem 1.1 is proved in the greater generality of ordered structures over an
arbitrary binary signature.

Our results generalize several known results, including the celebrated
Stanley-Wilf conjecture about permutations avoiding a fixed permutation
pattern. Moreover, we solve several open questions. This is discussed below.

### Related work

#### Enumerative combinatorics.

Enumerative combinatorics is involved in counting the number of labelled or
unlabelled structures in a given class of structures. Marcus and Tardos proved
[MT04] the Stanley-Wilf conjecture, that every class of permutations (viewed
as sets equipped with two linear orders) avoiding a fixed permutation as a
substructure has growth $2^{\mathcal{O}(n)}$, that is, contains at most
$2^{\mathcal{O}(n)}$ unlabelled structures with $n$ elements (up to
isomorphism). In particular, a hereditary class of permutations either has
growth $2^{\mathcal{O}(n)}$ or has factorial growth $n!$. The Marcus-Tardos
theorem is fundamental in twin-width theory, and underlies many of the
arguments used in [BKTW20a, BGK+, BGK+20], and also in the current paper. It
is also an immediate consequence of the equivalence (6)$\leftrightarrow$(2) in
Theorem 1.1, as every permutation is a substructure of any sufficiently large
regular semigrid (defined suitably for structures with two linear orders).

Our result proves the existence of a gap in the growth of hereditary classes
of ordered graphs: either the class has exponential growth
$2^{\mathcal{O}(n)}$ or, or otherwise it has at least factorial growth
$\lfloor\frac{n}{3}\rfloor!$. This generalizes previous results and answers a
problem posed by Bolagh, Bollobás and Morris [BBM06, Sec. 8].

In [BGK+] it is shown that every class of bounded twin-width is small, that
is, contains at most $n!2^{\mathcal{O}(n)}$ _labelled_ structures with $n$
elements (that is, with domain $\\{1,\ldots,n$}). It has been also conjectured
that the converse holds for every hereditary class of graphs. Our equivalence
(1)$\leftrightarrow$(6) in Theorem 1.1 confirms this conjecture in the case of
ordered graphs. Note that a class of ordered graphs is small if and only if it
contains at most $2^{\mathcal{O}(n)}$ unlabelled structures of size $n$ (that
is, up to isomorphism) as any ordered structure yields exactly $n!$ distinct
labelled structures.

#### Transductions and interpretations.

The study of transductions in theoretical computer science originates from the
study of word-like and tree-like structures, such as graphs of bounded
treewidth [ALS88] or graphs of bounded cliquewidth [Cou94].

By results of [BKTW20a], classes of bounded twin-width are closed under
transductions; in particular, no class of bounded twin-width transduces (nor
interprets) the class of all graphs.

The equivalence (1)$\leftrightarrow$(4), characterising hereditary classes of
ordered graphs of bounded twin-width as precisely those which do not transduce
the class of all graphs, is not unlike a result [CiO07] characterizing classes
of bounded cliquewidth as precisely those which do not transduce the class of
all graphs via some transduction of counting monadic second-order logic (CMSO,
an extension of first-order logic).

Note that in our result we require the graphs to be ordered for the
implication (4)$\rightarrow$(1) to hold: the class $\mathscr{C}$ of graphs of
maximum degree $3$ has unbounded twin-width [BGK+], but does not transduce the
class of all graphs as it is nowhere dense (see below).

Both the above result for cliquewidth and our results are obtained using
appropriate grid theorems.

#### Grid theorems.

Grid theorems are dichotomy results in structural graph theory which state
that either a structure has a small width with respect to a considered width
parameter, or otherwise, a grid-like obstruction can be found in the
structure. For example, this applies to the treewidth parameter and planar
grids occurring as minors [RS86]. It also applies to cliquewidth and planar
grids being definable in CMSO [CiO07]. As CMSO formulas can define the
relations of being in the same row/column in a planar grid, this allows to
encode any graph in a subgraph of a sufficiently large grid, implying the
result mentioned earlier about classes of bounded cliquewidth.

Our main result also proves an appropriate grid theorem for classes of ordered
graphs of bounded twin-width, as made precise by the notion of regular
semigrids. For such semigrids there is a first-order formula which defines the
relation of being in the same interval $I_{1},\ldots,I_{n}$ (‘same row’), and
the relation of having the same distance from the beginning of an interval
(‘same column’). From this it follows that if a hereditary class has unbounded
twin-width then it interprets the class of all graphs.

There are other known grid theorems. The Marcus-Tardos result itself proves a
result of this kind, stating that if a square $0-1$ matrix has sufficiently
many $1$’s then it must contain a large grid-like pattern formed by $1$’s.
Finally, [BKTW20a] use the Marcus-Tardos result to exhibit a grid-like
structure in classes of unbounded twin-width (as a subdivision of the
adjacency matrix). However, the grids obtained this way are not sufficiently
structured to allow to define the ‘same row’ and ‘same column’ relations. The
large semigrids that we exhibit provide the ultimate grid theorem for classes
of unbounded twin-width.

#### Monadic NIP.

Model theory classifies typically infinite structures according to the
combinatorial complexity of families of definable sets. This is usually done
through the introduction of tameness properties. The most important such
notion is that of stability. A structure is stable if no formula
$\varphi(x,y)$ encodes arbitrary large half-graphs ($\leqslant$-graphs as in
Fig. 1), which roughly means that there is no definable order on large subsets
of the structure. Stability captures the tameness properties of families of
algebraic sets. A related, weaker, notion is that of NIP: a structure is NIP
if every definable family of sets has finite VC-dimension. This captures the
tameness properties of families of sets arising from geometric settings (for
instance families of semi-algebraic sets of bounded complexity have finite VC-
dimension).

The notion of monadically NIP is a much stronger requirement which says that
the structure is NIP even if every subset of the domain can be used as a unary
predicate.

This notion is closely related to notions which are studied in theoretical
computer science and structural graph theory.

As mentioned, a class of structures $\mathscr{C}$ is monadically NIP if and
only if it does not transduce the class of all graphs. Hence, Theorem 1.1
proves that a class of ordered graphs is monadically NIP if, and only if it
has bounded twin-width.

Examples of monadically NIP graph classes include all nowhere dense classes. A
class of graphs $\mathscr{C}$ is _nowhere dense_ if for all $r\in\mathbb{N}$
there is some $t\in\mathbb{N}$ such that the $r$-subdivision of the $t$-clique
is not a subgraph of any graph in $\mathscr{C}$. Examples include the class of
graphs with maximum degree bounded by a constant (those classes have unbounded
twin-width [BGK+]), as well as every proper minor-closed graph class (here the
twin-width is bounded). A subgraph-closed class of graphs is nowhere dense if
and only if it is monadically NIP [AA14].

Monadically NIP classes are closed under transductions, so any transduction of
a nowhere dense graph class is also monadically NIP, but not necessarily
nowhere dense.

Theorem 1.2 provides a grid theorem for any monadically NIP class of
structures – not necessarily ordered, binary, nor finite.

#### Tractability of model-checking.

Testing if a given sentence $\varphi$ of first-order logic holds in a given
graph $G$ takes time $\mathcal{O}(|V(G)|^{|\varphi|})$ using the naive
algorithm, and it is conjectured that the exponential dependency on
$|\varphi|$ cannot be avoided. More precisely, it is conjectured that model-
checking first-order logic is not fixed-parameter tractable on the class of
all graphs, which is equivalent to the conjecture FPT$\neq$AW[$\ast$] from
parameterized complexity theory [FG06].

There are several known classes $\mathscr{C}$ of structures for which model-
checking first-order logic is fixed-parameter tractable. To the best of our
knowledge, all known tractable hereditary classes are monadically
NIP111Tractable classes that are not hereditary include for example the class
of all finite abelian groups [BM15].

Altogether, the following picture emerges, assuming FPT$\neq$AW[$\ast$]:

  1. 1.

if $\mathscr{C}$ is a subgraph-closed class of graphs then $\mathscr{C}$ is
monadically NIP if, and only if model-checking first-order logic is fixed-
parameter tractable over $\mathscr{C}$ [GKS14],

  2. 2.

if $\mathscr{C}$ is a hereditary class of ordered graphs then $\mathscr{C}$ is
monadically NIP if, and only if model-checking first-order logic is fixed-
parameter tractable over $\mathscr{C}$.

The last item is by the equivalence (1)$\leftrightarrow$(5) in our main
result, Theorem 1.1, both implications being new.

There are a few hereditary graph classes there are known to be tractable for
first-order logic, but are not covered by the items above. Those include:

  * –

classes of structures of bounded twin-width for which there is an effectively
computable certificate of having bounded twin-width (this includes all the
examples from the first paragraph),

  * –

map graphs [EK17],

  * –

first-order transductions of graph classes with bounded maximum degree
[GHO+20].

A conjecture [GHO+20, Conj. 8.2] implies that if a class $\mathscr{C}$ does
not transduce all graphs, equivalently, $\mathscr{C}$ is monadically NIP, then
model-checking first-order logic is fixed-parameter tractable on $\mathscr{C}$
(the conjecture there is actually even stronger). This would generalize all
the above.

Theorem 1.1 confirms this conjecture in the case of ordered binary structures.
Theorem 1.2 provides a tool for approaching the conjecture for all monadically
NIP classes, by providing a grid theorem for such classes.

#### Independent work.

A few days before this paper was submitted, Bonnet, Giocanti, Ossona de
Mendez, and Thomassé reported [BGdMT21] essentially the same result as our
Theorem 1.1 and Theorem 1.3. Our results were obtained independently, and most
likely using different methods (we were unable to verify this in the short
time before submission). The key differences between our results and the
results of [BGdMT21] are summarized below:

  * –

Part of our proof is not effective, as it uses tools from model theory,
including the compactness theorem for first-order logic. In particular, we do
not obtain an explicit upper bound on the twin-width of a graph avoiding a
fixed regular $n\times n$-semigrid. We do, however, obtain a computable bound.
It should not be difficult to extract some elementary bound from our proof,
but this falls short of the explicit bounds obtained in [BGdMT21].

  * –

The lower bound $\lfloor\frac{n}{3}\rfloor!$ in the growth of hereditary
classes of unbounded twin-width (7) in Theorem 1.1 is improved to $n!$ in
[BGdMT21]. Proving this requires substantially more effort than our bound,
which falls trivially out of the existence of large regular semigrids.

  * –

On the other hand, [BGdMT21] does not provide any result analogous to our
second main result, Theorem 1.2, which applies to all classes of structures –
possibly unordered, of arbitrary arity, and infinite.

##  2 Preliminaries

For $n\in\mathbb{N}$ denote $[n]=\\{0,\ldots,n-1\\}$.

#### Order.

Order means total order. A subset $C$ of an ordered set $(X,\leqslant)$ is
_convex_ , or an _interval_ , if $a,b\in C$ and $a\leqslant c\leqslant b$
imply $c\in C$, for all $a,b,c\in X$. A _convex partition_ of $X$ is a
partition into convex subsets.

#### Structures.

We consider the setting of relational structures. Fix a relational signature
$\Sigma$.

Let $\mathrm{S}$ be a $\Sigma$-structure. We identify $\mathrm{S}$ with its
domain when writing e.g. $a\in\mathrm{S}$ or $A\subseteq\mathrm{S}$. Tuples of
elements of $\mathrm{S}$ are denoted $\bar{a}\in\mathrm{S}^{k}$ or
$\bar{a}\in\mathrm{S}^{\bar{x}}$, where $\bar{x}$ is a finite set of
variables. In the latter case, the tuple $\bar{a}$ can be seen as a valuation
of the variables $\bar{x}$.

If $\mathrm{S}$ and $\mathrm{T}$ are two $\Sigma$-structures then $\mathrm{S}$
is an _induced substructure_ of $\mathrm{T}$ if the domain of $\mathrm{S}$ is
contained in the domain of $\mathrm{T}$ and for every relation symbol
$R\in\Sigma$ of arity $k$ and $\bar{a}\in\mathrm{S}^{k}$, $R(\bar{a})$ holds
in $\mathrm{S}$ if and only if $R(\bar{a})$ holds in $\mathrm{T}$.

#### Formulas.

We only consider first-order $\Sigma$-formulas in what follows.

If $\alpha$ is a formula and $\bar{x}$ is a finite set of variables then we
may write $\alpha(\bar{x})$ to indicate that the free variables of $\alpha$
are among $\bar{x}$.

For a formula $\alpha(\bar{x})$ and tuple $\bar{a}\in\mathrm{S}^{\bar{x}}$
write $\mathrm{S}\models\alpha(\bar{a})$ to denote that $\bar{a}$ satisfies
$\alpha$ in $\mathrm{S}$. Denote

$\alpha(\mathrm{S})=\\{\bar{a}\in\mathrm{S}^{\bar{x}}\mid\mathrm{S}\models\alpha(\bar{a})\\}.$

If $\alpha(\bar{x})$ is a formula and $\bar{x}$ is partitioned as
$\bar{x}=\bar{u}\cup\bar{v}$ then we may write $\alpha(\bar{u};\bar{v})$ to
signify this partition, and that $\bar{v}$ will be treated as variables
ranging over _parameters_. For instance, if $\mathrm{S}$ is a structure and
$\bar{b}\in\mathrm{S}^{\bar{v}}$ is a tuple then $\theta(\bar{x};\bar{b})$
denotes the _formula with parameters_ obtained from $\theta$ by replacing the
variables $\bar{v}$ by $\bar{b}$, treated as constants. Denote

$\alpha(\mathrm{S};\bar{b})=\\{\bar{a}\in\mathrm{S}^{\bar{u}}\mid\mathrm{S}\models\alpha(\bar{a};\bar{b})\\}.$

#### Atomic types.

An _atomic formula_ is a formula of the form $R(x_{1},\ldots,x_{k})$ where
$R\in\Sigma$ is of arity $k$. For a $k$-tuple $\bar{a}\in\mathrm{S}^{k}$, its
_atomic type_ , denoted $\operatorname{atp}(\bar{a})$, is conjunction of all
formulas $\alpha(x_{1},\ldots,x_{k})$ such that
$\mathrm{S}\models\alpha(\bar{a})$ and $\alpha$ is either an atomic formula,
or its negation. Up to bijection, $\operatorname{atp}(\bar{a})$ is uniquely
determined by the isomorphism type of the substructure $\mathrm{S}^{\prime}$
of $\mathrm{S}$ induced by $\\{a_{1},\ldots,a_{k}\\}$, expanded with $k$
constants interpreted as $a_{1},\ldots,a_{k}$.

An _atomic type_ with variables $\bar{x}$ is a conjunction which contains as a
conjunct every atomic formula $R(x_{1},\ldots,x_{k})$ for $R\in\Sigma$ and
$x_{1},\ldots,x_{k}\in\bar{x}$, or its negation $\neg R(x_{1},\ldots,x_{k})$.

####  $\theta$-types over a set.

Let $\theta(\bar{u};\bar{v})$ be a formula and $\mathrm{S}$ a structure. For a
tuple $\bar{a}\in\mathrm{S}^{\bar{u}}$ and a set $B\subseteq\mathrm{S}$ of
_parameters_ define the _type of $\bar{a}$ over $B$_ as:

$\operatorname{tp}^{\theta}(\bar{a}/B)=\\{\bar{b}\in
B^{\bar{v}}\mid\mathrm{S}\models\theta(\bar{a};\bar{b})\\}.$

Equivalently – up to bijection – $\operatorname{tp}^{\theta}(\bar{a}/B)$ is
the set of formulas $\theta(\bar{u};\bar{b})$ with parameters $\bar{b}$ from
$B$ that are satisfied by $\bar{a}$ in $\mathrm{S}$.

For a set $A\subseteq\mathrm{S}$, denote

$\mathrm{Types}^{\theta}(A/B):=\\{\operatorname{tp}^{\theta}(\bar{a}/B)\mid\bar{a}\in
A^{\bar{u}}\\}.$

Note that if $\mathrm{Types}^{\theta}(A/B)\leqslant k$ then
$\mathrm{Types}^{\hat{\theta}}(B/A)\leqslant 2^{k}$, where
$\hat{\theta}(\bar{v};\bar{u})=\theta(\bar{u};\bar{v})$.

If $\Sigma$ is a binary signature then denote

$\mathrm{Types}^{\Sigma}(A/B):=\\{\operatorname{tp}^{R}(a/B)\mid\bar{a}\in
A,R\in\Sigma\\}.$

Similarly as above, if $\mathrm{Types}^{\Sigma}(A/B)\leqslant k$ then
$\mathrm{Types}^{\Sigma}(B/A)\leqslant 2^{|\Sigma|k}$. Moreover, if
$\mathrm{Types}^{R}(A/B)\leqslant k_{R}$ for all $R\in\Sigma$ then
$\mathrm{Types}^{\Sigma}(A/B)\leqslant\prod_{R\in\Sigma}k_{R}$.

#### Homogeneity.

Let $\mathrm{S}$ be a structure over a binary relational signature $\Sigma$
and let $X,Y\subseteq\mathrm{S}$. The pair $X$ and $Y$ is _homogeneous_ if

$|\mathrm{Types}^{\Sigma}(X/Y)|=|\mathrm{Types}^{\Sigma}(Y/X)|=1.$

###### Example 2.1.

In a graph $G$, a pair $X,Y\subseteq G$ is homogeneous if and only if it is
homogeneous in the sense considered in Section 1. If $G$ is an ordered graph
then a pair $X,Y\subseteq G$ is homogeneous if $X$ and $Y$ are homogeneous in
$G$ as an unordered graph, and moreover, either all elements of $X$ are
strictly smaller than all elements of $Y$, or vice-versa.

#### Interpretations and transductions.

Let $\Sigma$ and $\Gamma$ be relational signatures. An _interpretation_
$I\colon\Sigma\to\Gamma$ consists of a $\Sigma$-formula $\delta(x)$ and for
each symbol $R\in\Gamma$ of arity $k$, a $\Sigma$-formula
$\varphi_{R}(x_{1},\ldots,x_{k})$. Given a $\Sigma$-structure $\mathrm{S}$,
define $I(\mathrm{S})$ as the $\Gamma$-structure with domain
$D=\delta(\mathrm{S})$ equipped with the relation $\varphi_{R}(\mathrm{S})\cap
D^{k}$ interpreted as $R$, for each $R\in\Gamma$ of arity $k$. A
_transduction_ $T\colon\Sigma\to\Gamma$ is a $\widehat{\Sigma}$-interpretation
for some $\widehat{\Sigma}$ extending $\Sigma$ by unary predicates. Given a
$\Sigma$-structure $\mathrm{S}$, define $T(\mathrm{S})$ as the set of
$\Gamma$-structures $I(\widehat{{\mathrm{S}}})$, where $\widehat{\mathrm{S}}$
ranges over all $\widehat{\Sigma}$-structures expanding $\mathrm{S}$ by
arbitrarily interpreting the unary predicates in $\widehat{\Sigma}-\Sigma$ in
$\widehat{\mathrm{S}}$.

Interpretations and transductions are closed under compositions: if

$\Sigma_{1}\stackrel{{\scriptstyle
I_{1}}}{{\longrightarrow}}\Sigma_{2}\stackrel{{\scriptstyle
I_{2}}}{{\longrightarrow}}\Sigma_{3}$

are two interpretations (resp. transductions) then there is an interpretation
(resp. transduction) $I_{2}\circ I_{1}\colon\Sigma_{1}\to\Sigma_{3}$ such that
$(I_{2}\circ I_{1})(\mathrm{S})=I_{2}(I_{1}(\mathrm{S}))$, for every
$\Sigma$-structure $\mathrm{S}$.

###### Remark 2.1.

What is defined above is a special case of a more general notion of
interpretations considered in model theory. The restricted interpretations
that we consider here are sometimes called _simple_ interpretations, but we
drop this qualifier in this paper.

###### Definition 1.

A class of $\Gamma$-structures $\mathscr{D}$ is an _interpretation_ (resp.
_transduction_) of a class of $\Sigma$-structures $\mathscr{C}$ if there is an
interpretation (resp. transduction) $T\colon\Sigma\to\Gamma$ such that for
every structure $\mathrm{D}\in\mathscr{D}$ there is some
$\mathrm{C}\in\mathscr{C}$ with $\mathrm{D}\in T(\mathrm{C})$.In this case we
also say that $\mathscr{C}$ _interprets_ (resp. _transduces_) $\mathscr{D}$.

#### Classes of structures.

We consider classes $\mathscr{C}$ of structures that are all over a common
relational signature $\Sigma$. We assume that $\mathscr{C}$ is closed under
isomorphisms, that is, if $\mathrm{A}$ and $\mathrm{B}$ are isomorphic
structures then either both belong to $\mathscr{C}$ or both do not belong to
$\mathscr{C}$. A class of structures is _hereditary_ if it is closed under
taking induced substructures.

We say that $\mathscr{C}$ is a class of _binary structures_ if $\Sigma$ is a
relational signature with relation symbols of arity at most two. We do not
restrict only to classes of finite structures. However, graphs are always
assumed to be finite (specifically, when we say that $\mathscr{C}$ interprets
the class of all graphs). By a class of _ordered structures_ we mean a class
of structures over a signature including the symbol $\leqslant$ which is
interpreted as an order in each structure from the class.

### Twin-width

A partition ${\mathcal{P}}$ of the domain of a structure $\mathrm{S}$ has
_red-degree_ at most $d$ (for $d\in\mathbb{N}$) if for every
$X\in{\mathcal{P}}$ there are at most $d$ sets $Y\in{\mathcal{P}}$ other than
$X$ such that $X$ and $Y$ are not homogeneous. A _contraction sequence_ in a
finite structure $\mathrm{S}$ is a sequence of partitions
${\mathcal{P}}_{1},{\mathcal{P}}_{2},\ldots,{\mathcal{P}}_{n}$ of $\mathrm{S}$
such that:

  * –

${\mathcal{P}}_{1}$ has one part,

  * –

${\mathcal{P}}_{n}$ is the partition into singletons,

  * –

${\mathcal{P}}_{i+1}$ is obtained from ${\mathcal{P}}_{i}$ by splitting one of
the parts of ${\mathcal{P}}_{i}$ into two, for $i=1,\ldots,n-1$.

###### Definition 2 (Twin-width).

Fix $d\in\mathbb{N}$. A finite structure $\mathrm{S}$ over a binary signature
has _twin-width_ at most $d$ if it has a contraction sequence consisting of
partitions of red-degree at most $d$.

A class $\mathscr{C}$ of finite, binary structures has _bounded twin-width_ if
there is some $d\in\mathbb{N}$ such that every $\mathrm{S}\in\mathscr{C}$ has
twin-width at most $d$.

###### Example 2.2.

A class of graphs has twin-width $0$ if and only if it is a class of cographs,
that is, graphs that can be obtained from one-vertex graphs by the operations
of disjoint union and edge-complement.

###### Example 2.3 ([BKTW20b]).

The following classes have bounded twin-width:

  * –

every proper minor-closed class of finite graphs,

  * –

every class of graphs of bounded clique-width,

  * –

every class of posets of bounded width,

  * –

every class of permutations that excludes a fixed permutation pattern.

On the other hand, the following classes do not have bounded twin-width:

  * –

the class of all finite graphs,

  * –

the class of all bipartite graphs,

  * –

the class of all graphs of degree at most $3$ [BGK+].

The following is a consequence of [BKTW20b], Theorems 10 and 14.

######  Fact 1 ([BKTW20b]).

The following conditions are equivalent for a class of finite binary
structures $\mathscr{C}$:

  1. 1.

$\mathscr{C}$ has bounded twin-width,

  2. 2.

There is some $t\in\mathbb{N}$ such that for every structure
$\mathrm{S}\in\mathscr{C}$ there is an order on $\mathrm{S}$ such that for
every two convex partitions ${\mathcal{L}}$ and ${\mathcal{R}}$ of
$\mathrm{S}$ into $t$ parts, there are $L\in\mathcal{L}$ and $R\in\mathcal{R}$
such that $|\mathrm{Types}^{\Sigma}(L/R)|=1$ or
$|\mathrm{Types}^{\Sigma}(R/L)|=1$.

In the case of graph classes $\mathscr{C}$, the second condition above means
the following: for every $G\in\mathscr{C}$ there is an order $\leqslant$ on
$G$ such that in the adjacency matrix $M$ of $G$ along this order, for every
partition $\mathcal{R}$ of the rows of $M$ and partition $\mathcal{C}$ of the
columns of $M$ into convex intervals, there is some pair $R\in\mathcal{R}$ and
$C\in\mathcal{C}$ such that the submatrix $M[R\times C]$ has either all rows
equal, or all columns equal.

######  Fact 2 ([BKTW20b]).

Classes of bounded twin-width are closed under:

  1. 1.

_expanding by unary predicates:_ if $\mathscr{C}$ is a class of bounded twin-
width and $\mathscr{C}^{\prime}$ is a class of structures such that each
$\mathrm{S}^{\prime}\in\mathscr{C}^{\prime}$ is an expansion of some
$\mathrm{S}\in\mathscr{C}$ by unary predicates, then $\mathscr{C}^{\prime}$
has bounded twin-width.

  2. 2.

_taking induced substructures_ : if $\mathscr{C}$ has bounded twin-width and
$\mathscr{C}^{\prime}$ is a class such that every structure in
$\mathscr{C}^{\prime}$ is an induced substructure of some structure in
$\mathscr{C}$, then $\mathscr{C}^{\prime}$ has bounded twin-width.

  3. 3.

_first-order transductions:_ if $\mathscr{C}$ is a class of bounded twin-width
and $T$ is a first-order transduction, then $T(\mathscr{C})$ is a class of
bounded twin-width;

  4. 4.

_expanding by compatible orders:_ if $\mathscr{C}$ is a class of bounded twin-
width then there is an ordered expansion $\mathscr{C}^{\prime}$ of
$\mathscr{C}$ (that is, a class of ordered structures $\mathscr{C}^{\prime}$
such that for each structure in $\mathrm{S}\in\mathscr{C}$, the structure
$\mathrm{S}$ with some order belongs to $\mathscr{C}^{\prime}$) such that
$\mathscr{C}^{\prime}$ has bounded twin-width.

###### Proof.

(3) follows from [BKTW20b, Theorem 39]. (1) and (2) are special cases (also
(2) is immediate by definition: when taking a substructure induced by $A$, the
same contraction sequence, restricted to $A$, works).

We show (4). Let $\mathrm{S}$ be a structure and let
$\mathcal{P}_{1},\ldots,\mathcal{P}_{n}$ be its contraction sequence. There is
an order $\leqslant$ on $\mathrm{S}$ such that each partition
$\mathcal{P}_{i}$ is convex. Indeed, order the parts of $\mathcal{P}_{i}$ by
induction on $i$: $\mathcal{P}_{1}$ has just one part, so there is nothing to
do, whereas $\mathcal{P}_{i+1}$ is obtained from $\mathcal{P}_{i}$ by merging
some two part $X_{1},X_{2}$ of $\mathcal{P}_{i}$ into one parts $X_{1}\cup
X_{2}$ of $\mathcal{P}_{i+1}$. By induction, $X_{1}$ and $X_{2}$ are already
ordered, and order $X_{1}\cup X_{2}$ by declaring (arbitrarily) that
$X_{1}<X_{2}$.

As each partition $\mathcal{P}_{i}$ is convex with respect to $\leqslant$, a
pair of its parts that was homogeneous in $\mathrm{S}$ remains homogeneous in
$(\mathrm{S},\leqslant)$. Hence, the contraction sequence
$\mathcal{P}_{1},\ldots,\mathcal{P}_{n}$ has the same red-degree in
$\mathrm{S}$ as in $(\mathrm{S},\leqslant)$.

Given a class of structures $\mathscr{C}$ of twin-width bounded by $d$, pick a
contraction sequence of red-degree at most $d$ for each structure
$\mathrm{S}\in\mathscr{C}$ and then expand $\mathrm{S}$ by the order as
defined above. This yields a class of ordered structures
$\mathscr{C}^{\prime}$ of red-degree at most $d$. ∎

Morally, an ordered expansion $G_{\leqslant}$ of $G$ with
$\operatorname{tww}(G_{\leqslant})$ with twin-width bounded by a function of
$\operatorname{tww}(G)$ is the same as $G$ together with a contraction
sequence. In one direction, given $G$ together with a contraction sequence we
can compute (in linear time) a total order $\leqslant$ on $G$ such that
$\operatorname{tww}(G_{\leqslant})=\operatorname{tww}(G)$, described as above.
The converse direction is not that clear, however. We will prove (cf. Section
7) there is a polynomial-time algorithm which inputs a totally ordered
structure $G_{\leqslant}$ and outputs its contraction sequence of red-degree
$f(\operatorname{tww}(G_{\leqslant}))$, for some computable function $f$. A
contraction sequence of $G_{\leqslant}$ is also a contraction sequence of $G$.

##  3 Proof outline

Our proof proceeds in several steps, which utilise various notions which turn
out to be equivalent to bounded twin-width. We explain those notions and
outline the proof below. Figure 3 may be helpful in tracing the implications.

[BKTW20b](cf. Fact. 2)Sec. 5, usesgrid RamseySec. 8 and 9,model-theoretic Sec.
6, usesMarcus-TardosSection 7[BGK+]Section 4boundedtwin-widthdoes not
interpretall graphsfpt model-checkingsmallno large quantifier-free gridsno
large regular semigrids$(k,t)$-simple Figure 3: Implications among the
conditions in Theorem 1.1.

The first notion is as follows.

###### Definition 3 ($(k,t)$-simple).

An ordered binary structure $\mathrm{S}$ is _$(k,t)$ -simple_ if for every
pair of convex partitions $\mathcal{L},\mathcal{R}$ with
$|\mathcal{L}|=|\mathcal{R}|\geqslant t$ of $\mathrm{S}$, there are
$L\in\mathcal{L}$ and $R\in\mathcal{R}$ such that
$|\mathrm{Types}^{\Sigma}(L/R)|\leqslant k$ and
${|\mathrm{Types}^{\Sigma}(R/L)|\leqslant k}$.

For an ordered graph $G$ this means that if the set of rows and set of columns
of the adjacency matrix of $G$ are partitioned into $t$ intervals each, then
there there is a submatrix induced by some two of those intervals which has at
most $k$ distinct rows and at most $k$ distinct columns. This perspective can
be adapted to binary structures, by suitably defining their adjacency matrices
(cf. Sec. 6).

As a first step, we prove that $(k,t)$-simple classes have bounded twin-width.

######  Theorem 3.1.

Every $(k,t)$-simple finite ordered binary structure has twin-width
$2^{2^{\mathcal{O}(kt)}}$.

This is shown in Section 6, and follows the ideas present in [BKTW20b]. The
proof is combinatorial, and uses the Marcus-Tardos result about 0-1 matrices
with many entries equal to $1$, which is the cornerstone of twin-width theory.
Our proof generalizes a result and a construction of Bonnet et al. [BKTW20b,
Theorem 14].

Another key notion is that of defining grids by a first-order formula. It
makes sense in any class of structures over any signature $\Sigma$.

Fix a first-order formula $\varphi(\bar{x},\bar{y},z)$, where $\bar{x}$ and
$\bar{y}$ are sets of variables and $z$ is a single variable. An _$m\times n$
grid_ defined by $\varphi$ in a structure $\mathrm{S}$ is a triple of sets
$A\subseteq\mathrm{S}^{\bar{x}}$, $B\subseteq\mathrm{S}^{\bar{y}}$ and
$C\subseteq\mathrm{S}$ with $|A|=m$, $|B|=n$ and $|C|=m\times n$, such that
the relation

$\\{(\bar{a},\bar{b},c)\in A\times B\times
C\mid\mathrm{S}\models\varphi(\bar{a},\bar{b},c)\\}$

is the graph of a bijection between $A\times B$ and $C$. More explicitly, for
each $(\bar{a},\bar{b})\in A\times B$ there is a unique $c\in C$ such that
$\mathrm{S}\models\varphi(\bar{a},\bar{b},c)$, and conversely, for each $c\in
C$ there is a unique $(\bar{a},\bar{b})\in A\times B$ such that
$\mathrm{S}\models\varphi(\bar{a},\bar{b},c)$.

###### Definition 4 (Defining large grids).

A class of structures $\mathscr{C}$ _defines large grids_ if there is a
formula $\varphi(\bar{x},\bar{y},z)$ such that for all $n\in\mathbb{N}$
$\varphi$ defines an $n\times n$ grid in some structure
$\mathrm{S}\in\mathscr{C}$.

###### Example 3.1.

Consider an $m\times n$-semigrid as discussed in the introduction. It consists
of $m+1$ intervals $I_{0},\ldots,I_{m}$ of size $n+1$ each, and with
$I_{1}<\ldots<I_{m}$. We show that there is a formula
$\varphi(x_{1},x_{2};y_{1},y_{2};z)$ which defines an $m\times n$-grid in an
$m\times n$-semigrid $G$ of a given type
$R\in\\{\leqslant,\geqslant,=,\neq\\}$.

The set $A\subseteq G^{2}$ consists of the pairs $\bar{a}_{i}=(\min I_{i},\max
I_{i})$ of endpoints of the intervals $I_{i}$, for $i=1,\ldots,n$. Suppose the
semigrid has type $=$. Then we take $B=I_{0}\subseteq G$,
$C=I_{1}\cup\cdots\cup I_{n}$, and
$\varphi(x_{1},x_{2};y;z)\equiv(x_{1}\leqslant z\leqslant x_{2})\land E(x,z).$
The reader is invited to check that this formula defines an
$n\times(n+1)$-grid $(A,B,C)$.

The case of a $\leqslant$-semigrid is only slightly different. Note that in a
$\leqslant$-graph formed by two sets $X$ and $Y$ (cf. Fig. 1), the $i$th
vertex $y\in Y$ in the bottom can be characterized in terms of $X$ by saying
that it is adjacent to the $i$th vertex in $X$ and non-adjacent to the
$(i+1)$st vertex in $X$. Because of this, we now take $B\subseteq G^{2}$ to
consist of pairs of consecutive elements of $I_{0}$, and for $A$ and $C$ as
above, use the formula $\psi(x_{1},x_{2};y_{1},y_{2};z)\equiv(x_{1}\leqslant
z\leqslant x_{2})\land(E(y_{1},z)\land\neg E(y_{2},z))$. Then $\psi$ defines
an $n\times n$-grid $(A,B,C)$.

The cases of $\geqslant$ and $\neq$-semigrids are similar.

The core of our proof is the following:

######  Theorem 3.2.

If $\mathscr{C}$ is a class of ordered binary structures which is not
$(k,t)$-simple for any $k,t\in\mathbb{N}$, then some quantifier-free formula
$\varphi(\bar{x},\bar{y},z)$ defines large grids in $\mathscr{C}$.

This is proved using model-theoretic methods. In particular, we use
compactness to construct an infinite ordered binary structure $\mathrm{N}$
which defines infinite grids. This is done in Sections 8 and 9.

Model-theoretic ideas are at the heart of our approach. We provide further
characterisations of bounded twin-width classes in terms of notions
originating from model-theory in Section 8. In particular, some of the
implications in Theorem 1.1 are stated and proved in much greater generality,
for arbitrary classes of structures.

Finally, we prove:

######  Theorem 3.3.

Let $\mathscr{C}$ be a hereditary class of ordered binary structures. If
$\mathscr{C}$ defines large grids using a quantifier-free formula, then
$\mathscr{C}$ contains arbitrarily large regular $n\times n$-semigrids.

This uses a result from Ramsey theory to regularize the obtained grids. It
crucially relies on the grids being defined by a quantifier-free formula. This
is proved in Section 5.

As a consequence of our proof, we obtain Theorem 1.3, yielding a polynomial-
time approximation algorithm for the twin-width of a given ordered binary
structure. This in turn yields Corollary 7.2, about fixed-parameter
tractability of model-checking of first-order logic on ordered structures of
bounded twin-width. This is shown in Section 7.

From here, it is all downhill. The following result is relatively
straightforward.

######  Proposition 3.4.

Let $\mathscr{C}$ be a hereditary class of ordered graphs which contains
arbitrarily large regular $n\times n$-semigrids. Then:

  * –

$\mathscr{C}$ interprets the class of all graphs,

  * –

model-checking first-order logic on $\mathscr{C}$ is as hard as on the class
of all graphs,

  * –

$\mathscr{C}$ contains at least $\lfloor\frac{n}{3}\rfloor!$ non-isomorphic
structures with $n$ vertices.

Conversely, by the results of [BKTW20a] and [BGK+] classes of ordered graphs
of bounded twin-width:

  * –

are preserved under transductions,

  * –

have at most $2^{\mathcal{O}(n)}$ structures of size $n$, up to isomorphism,

This closes the loop (cf. Fig. 3) and proves the equivalence of all the
notions considered above, yielding our first main result, Theorem 1.1.

Our second main result, Theorem 1.2, applies to arbitrary classes of
structures, not necessarily finite, ordered or binary. Similarly as above, at
its core is a suitable grid theorem. We define a notion _regular_ classes
$\mathscr{C}$, which generalizes the notion of $(k,t)$-simple classes above to
arbitrary structures. We then show that if a class $\mathscr{C}$ is not
regular then it defines large grids. This is proved in Section 8, alongside
with Theorem 3.2. In the process, we exhibit various properties of monadically
NIP classes of structures, in particular, that they are _1-dimensional_.

##  4 Regular semigrids

In this section, we define the notion of regular semigrids, and prove that
they exhibit bad behaviour, proving Proposition 3.4. In particular, they do
not have bounded twin-width.

We start with defining regular semigrids. The definition below applies only to
ordered graphs, rather than to ordered binary structures. The complete
definition of regular semigrids for ordered binary structures is deferred to
Section 5. Proposition 3.4 will be easily lifted to arbitrary binary
signatures (cf. Corollary 5.8).

Fix an $m\times n$-semigrid consisting of disjoint intervals
$I_{0},\ldots,I_{m}$ of length $n+1$ each, with $I_{1}<\ldots<I_{m}$. It will
be convenient to identify the elements of the $m\times n$ semigrid with the
points in $[m+1]\times[n+1]$ so that for each $i\in[m+1]$, the elements of
$I_{i}$ are identified with the elements in the $i$th row $\\{i\\}\times[n+1]$
in increasing order (that is, the smallest element in $I_{i}$ is identified
with $(i,0)$, the second smallest with $(i,1)$, etc.). In other words, the
intervals $I_{0},\ldots,I_{m}$ are arranged in an $(m+1)\times(n+1)$ matrix by
putting $I_{0}$ in the first row, $I_{1}$ in the next one, and so on. Note
that the order $\leqslant$ on $I_{1}\cup\cdots\cup I_{m}$ (with the interval
$I_{0}$ omitted) agrees with the lexicographic order on
$\\{1,\ldots,m\\}\times\\{0,\ldots,n\\}$. For $p,q\in I_{1}\cup\cdots\cup
I_{m}$, with $p=(i,j)$ in the $i$th row and $j$th column and
$q=(i^{\prime},j^{\prime})$ in the $i^{\prime}$th row and $j^{\prime}$th
column, and $p<q$ lexicographically, let
$\mathrm{dir}(p,q)\in\\{\rightarrow,\downarrow,\searrow,\swarrow\\}$ be equal
to:

> $\rightarrow$ if $i=i^{\prime}$, $j<j^{\prime}$, $\downarrow$ if
> $j=j^{\prime}$, $i<i^{\prime}$, $\searrow$ if $i<i^{\prime}$,$j>j^{\prime}$,
> $\swarrow$ if $i<i^{\prime}$, $j^{\prime}<j^{\prime}$.

An $m\times n$-semigrid is  _regular_ if:

  1. 1.

$I_{0}<I_{1}<\ldots<I_{m}$ or $I_{1}<\ldots<I_{m}<I_{0}$,

  2. 2.

$I_{0}$ forms a clique or an independent set, and

  3. 3.

for $p,q\in I_{1}\cup\cdots\cup I_{n}$ with $p<q$, the adjacency between $p$
and $q$ depends only $\mathrm{dir}(p,q)$.

A _scheme_ of a semigrid consists of: the type
$R\in\\{\leqslant,\geqslant,\neq,=\\}$, a parameter $S\in\\{<,>\\}$
corresponding to the choice (1) above, a parameter
$T\in\\{\text{clique},\text{independent}\\}$ corresponding to the choice (2)
above, and a subset $X\subseteq\\{\rightarrow,\downarrow,\swarrow,\searrow\\}$
corresponding to the choices (3) above, where a pair $p,q$ with $p<q$ is
adjacent if and only if $\mathrm{dir}(p,q)\in X$. Denote by

$\mathrm{Schemes}=\\{\leqslant,\geqslant,\neq,=\\}\times\\{<,>\\}\times\\{\text{clique},\text{independent}\\}\times
2^{\\{\rightarrow,\downarrow,\swarrow,\searrow\\}}$

the set of all possible schemes, so $|\mathrm{Schemes}|=2^{8}$. For each
$\sigma\in\mathrm{Schemes}$, let $\mathscr{R}_{\sigma}$ denote the class of
all regular $m\times n$ semigrids conforming to $\sigma$, for all
$m,n\in\mathbb{N}$.

Note that a regular $m\times n$-semigrid $G\in\mathscr{R}_{\sigma}$ contains
as induced substructures every regular $m^{\prime}\times n^{\prime}$-semigird
$G^{\prime}\in\mathscr{R}_{\sigma}$, for all $m^{\prime}\leqslant m$ and
$n^{\prime}\leqslant n$ (by removing some rows and columns of $G$), so if a
hereditary class $\mathscr{C}$ contains arbitrarily large regular $n\times
n$-semigrids then $\mathscr{C}\supseteq\mathscr{R}_{\sigma}$ for some
$\sigma\in\mathrm{Schemes}$.

The definition of regular semigrids is generalized to arbitrary binary
structures in Section 5.

Proposition 3.4 is restated below.

######  Proposition 4.1.

Let $\mathscr{C}$ be a hereditary class of ordered graphs. If $\mathscr{C}$
contains arbitrarily large regular semigrids then:

  1. 1.

$\mathscr{C}$ interprets the class of all graphs,

  2. 2.

model-checking first-order logic on $\mathscr{C}$ is AW[$\ast$]-hard,

  3. 3.

$\mathscr{C}$ contains at least $\lfloor\frac{n}{3}\rfloor!$ non-isomorphic
structures with $n$ elements.

###### Proof.

Fix any $\sigma\in\mathrm{Schemes}$ such that $\mathscr{C}$ contains
$\mathscr{R}_{\sigma}$. Without loss of generality we may assume that $\sigma$
imposes an independent set on $I_{0}$ (otherwise we replace edges by non-edges
in all graphs in $\mathscr{C}$ and replacing ‘$\mathrm{clique}$’ by
‘$\mathrm{independent}$’ in $\sigma$). Also without loss of generality we may
assume that $\sigma$ imposes $I_{0}<I_{1}$ (otherwise reverse the order in all
structures in $\mathscr{C}$ and replace $<$ by $>$ in $\sigma$).

Fix a semigrid $G\in\mathscr{R}_{\sigma}$; recall that its elements are
identified with $[m+1]\times[n+1]$. Let $\ast=(0,0)$ denote the smallest
element in $G$. This is also the smallest element of $I_{0}$, by the
assumption above. Let $\mathcal{R}=\\{\min I_{1},\ldots,\min
I_{m}\\}=\\{(1,0),(2,0),\ldots,(m,0)\\}$ be the set of smallest elements of
each of the intervals $I_{1},\ldots,I_{m}$ ($I_{0}$ is omitted). Those
elements represent the rows of $M=\\{1,\ldots,m\\}\times\\{1,\ldots,n\\}$. Let
$\mathcal{C}=\\{(0,1),\ldots,(0,n)\\}=I_{0}-\\{\ast\\}$; those elements
represent the columns of $M$.

For a given $S\subseteq M$, denote by $G^{S}$ the ordered subgraph of $G$
induced by $\\{\ast\\}\cup\mathcal{C}\cup\mathcal{R}\cup S$. The following is
immediate.

######  Claim 4.1.

There is a polynomial-time algorithm which inputs numbers $m,n\in\mathbb{N}$,
a relation $S\subseteq\\{1,\ldots,m\\}\times\\{1,\ldots,n\\}$ and in
polynomial time outputs the ordered graph $G^{S}\in\mathscr{R}_{\sigma}$.

This will be the basis of our reduction from the model-checking problem over
the class of arbitrary binary relations to that over $\mathscr{C}$.

We now show how to interpret the binary relation $S$ in $G^{S}$ by a first-
order formula. The following lemma is proved by a simple case analysis,
depending on $\sigma\in\mathrm{Schemes}$.

######  Lemma 4.2.

There are first-order formulas
$\varphi_{\mathcal{C}}(x),\varphi_{\mathcal{R}}(x),\pi_{1}(x,y),\pi_{2}(x,y),\rho(x,y)$
such that for every $m\times n$-semigrid $G\in\mathscr{R}_{\sigma}$ and
$S\subseteq\\{1,\ldots,m\\}\times\\{1,\ldots,n\\}$:

$\displaystyle\varphi_{\mathcal{C}}(G^{S})$
$\displaystyle=\mathcal{C}\subseteq G^{S},$
$\displaystyle\varphi_{\mathcal{R}}(G^{S})$
$\displaystyle=\mathcal{R}\subseteq G^{S},$ $\displaystyle\pi_{1}(G^{S})$
$\displaystyle=\\{((i,j),(i,0))\mid(i,j)\in S\\}\subseteq
S\times\mathcal{R}\subseteq G^{S}\times G^{S}$ $\displaystyle\pi_{2}(G^{S})$
$\displaystyle=\\{((i,j),(0,j))\mid(i,j)\in S\\}\subseteq
S\times\mathcal{C}\subseteq G^{S}\times G^{S}$ $\displaystyle\rho(G^{S})$
$\displaystyle=\\{((i,0),(0,j))\mid(i,j)\in
S\\}\subseteq\mathcal{R}\times\mathcal{C}\subseteq G^{S}\times G^{S}.$

In words, $\pi_{1}$ and $\pi_{2}$ define the graphs of the two projections
from $S\subseteq\\{1,\ldots,m\\}\times\\{1,\ldots,n\\}$ onto
$\mathcal{R}\simeq\\{1,\ldots,m\\}$ and $\mathcal{C}\simeq\\{1,\ldots,n\\}$,
while $\rho$ defines the relation
$S\subseteq\\{1,\ldots,m\\}\times\\{1,\ldots,n\\}$ as a relation on
$\mathcal{R}\times\mathcal{C}$.

###### Proof.

If $\sigma$ specifies a type among $\leqslant,\geqslant,=$, then $\mathcal{C}$
is the open interval between $\ast$ and the smallest neighbor of $\ast$. If
$\sigma$ specifies the type $\neq$, then $\mathcal{C}$ is the open interval
between $\ast$ and the smallest neighbor of the successor of $\ast$. In either
case, $\mathcal{C}$ can be described by a first-order formula
$\varphi_{\mathcal{C}}(x)$ not depending on $m,n\in\mathbb{N}$ and $S$.

If $\sigma$ specifies the type $=$ or $\geqslant$, then $\mathcal{R}$ is the
set of neighbors of $\ast$. If $\sigma$ specifies the type $\leqslant$ then
$\mathcal{R}$ is the neighborhood of $\ast$ minus the neighborhood of the
successor of $\ast$. Finally, if $\sigma$ specifies the type $\neq$ then
$\mathcal{R}$ is the complement of $\mathcal{C}\cup\\{\ast\\}\cup N(\ast)$
(the set of neighbors of $\ast$). In all cases, $\mathcal{R}$ can be described
by a first-order formula $\psi_{\mathcal{R}}(x)$ not depending on $m,n$ and
$S$.

Note that an element $p\in S$ lies in the $i$th row if and only if
$(i,0)<p<(i+1,0)$, which can be expressed by a first-order formula. More
precisely, consider the first-order formula $\pi_{1}(x,y)$ which holds if and
only if $y\in\mathcal{R}$, and $y<x<y^{\prime}$ where $y^{\prime}$ is the
least $y^{\prime}\in\mathcal{R}$ with $y>y^{\prime}$ (unless no such
$y^{\prime}$ exists, then just take $y<x$). Then $\pi_{1}(p,q)$ holds if and
only if $p$ and $q$ are in the same row and $p\in\mathcal{R}$, defining the
required relation.

Dually, we can define that an element in $S$ is in a column $c\in\mathcal{C}$.
Namely, let $\pi_{2}(x,y)$ be the first-order formula expressing that
$y\in\mathcal{C}$, and:

(case $=$)

$x$ is a neighbor of $y$,

(case $\neq$)

$x$ is a non-neighbor of $y$,

(case $\leqslant$)

$y$ is a neighbor of $x$ but not of the predecessor of $x$,

(case $\geqslant$)

$x$ is a neighbor $y$ but not of the predecessor of $y$.

Finally, the formula $\rho(x,y)$ expresses that
$x\in\mathcal{R},y\in\mathcal{C}$ and there exists $z$ such that
$\pi_{1}(z,x)$ and $\pi_{2}(z,y)$ hold. ∎

Let $\mathscr{B}$ be the class of all finite, ordered bipartite graphs
$H=(V_{1}\cup V_{2},E,\leqslant_{1},\leqslant_{2})$ with parts $V_{1}$ and
$V_{2}$, where $V_{1}$ is totally ordered by $\leqslant_{1}$ and $V_{2}$ is
totally ordered by $\leqslant_{2}$, and $E\subseteq V_{1}\times V_{2}$.

######  Lemma 4.3.

There is an interpretation $I_{\sigma}$ such that
${I_{\sigma}(\mathscr{C})=\mathscr{B}}$ for every hereditary class of ordered
graphs $\mathscr{C}$ containing $\mathscr{R}_{\sigma}$. More precisely, for
$S\subseteq\\{1,\ldots,m\\}\times\\{1,\ldots,n\\}$, the structure
$I_{\sigma}(G^{S})$ is the bipartite graph with parts
$\mathcal{R}=\\{1,\ldots,m\\}$ and $\mathcal{C}=\\{1,\ldots,n\\}$, each
ordered by $\leqslant$, where $i\in\mathcal{R}$ and $j\in\mathcal{C}$ are
adjacent if and only if $(i,j)\in S$.

###### Proof.

$I_{\sigma}$ consists of:

  * –

the the domain formula
$\delta(x)\equiv\varphi_{\mathcal{R}}(x)\lor\varphi_{\mathcal{C}}(x)$ defining
the domain $\mathcal{R}\cup\mathcal{C}$,

  * –

the formula $\varphi_{E}(x,y)\equiv\rho(x,y)$ defining the edge relation $E$,

  * –

the formula $\varphi_{\mathcal{R}}(x)\land\varphi_{\mathcal{R}}(y)\land
x\leqslant y$ defining the order $\leqslant_{1}$ on $\mathcal{R}$, and

  * –

the formula $\varphi_{\mathcal{C}}(x)\land\varphi_{\mathcal{C}}(y)\land
x\leqslant y$ defining the order $\leqslant_{2}$ on $\mathcal{C}$.

The statement follows from Lemma 4.2. ∎

As the class of all graphs interprets in the class of all bipartite graphs via
some first-order interpretation $T$, the interpretation $I_{\sigma}$ can be
further composed with $T$ obtaining an interpretation $T\circ T_{\sigma}$ such
that $(T\circ T_{\sigma})(\mathscr{C})$ is the class of all finite graphs.
This proves (1).

This also gives a polynomial-time reduction of the model-checking problem on
the class of bipartite graphs to the model-checking problem on $\mathscr{C}$:
a sentence $\psi$ holds in a bipartite graph $H=(V_{1},V_{2},E)$ with
$V_{1}=\\{1,\ldots,m\\},V_{2}=\\{1,\ldots,n\\}$ if and only if the sentence
obtained from $\psi$ by replacing each atom $E(x,y)$ by $\rho(x,y)$ holds in
the structure $G^{S}$, where $G\in\mathscr{R}_{\sigma}$ is the $m\times
n$-semigrid and $S=E\cap(V_{1}\times V_{2})$. As $G^{S}$ can be computed in
polynomial time given $H$ (cf. Claim 4.1), this yields the required
polynomial-time reduction. Since model-checking first-order logic on the class
of all bipartite graphs is AW[$\ast$]-hard [FG06], this yields the same lower
bound for $\mathscr{C}$, proving (2).

We now prove (3). For a $k\times l$ matrix $M\in\\{0,1\\}^{k\times l}$ with
0-1 entries let $|M|$ denote $k+l$ plus the number of nonzero entries in $M$.
For $n\in\mathbb{N}$ define

$f(n)=\max\\{|M|\mid k,l\in\mathbb{N},M\in\\{0,1\\}^{k\times l}\\}.$

It is easy to see that $f(n)\geqslant\lfloor\frac{n}{3}\rfloor!$. Indeed: for
$n=3k$ consider a $k\times k$ permutation matrix $M$, having exactly one
nonzero entry in each row and each column. Then $|M|=n$, and there are exactly
$k!$ such matrices.

This bound can be easily improved: instead of permutation matrices we can
consider all $k\times k$ matrices with exactly one nonzero entry in each
column, yielding $f(n)\geqslant k^{k}$ for $n=3k$. Further, taking all
$k\times k$ matrices with exactly $k$ nonzero entries yields
$f(n)\geqslant{k^{2}\choose k}$ for $n=3k$. We expect those lower bounds can
be improved further. We use the first lower bound as it yields the simplest
expression among the three.

######  Lemma 4.4.

$\mathscr{C}$ contains at least $f(n)$ non-isomorphic structures with $n$
vertices, for each $n\in\mathbb{N}$.

###### Proof.

For all $k,l\in\mathbb{N}$ and matrix $M\in\\{0,1\\}^{k,l}$, consider the
$k\times l$-regular semigrid $G\in\mathscr{R}_{\sigma}$ and denote by
$F(k,l,M)$ the ordered graph $G^{S}\in\mathscr{C}$ as constructed above for
$S$ being the set of non-zero entries in $M$:

$S=\\{(i,j)\mid 1\leqslant i\leqslant k,1\leqslant j\leqslant l,M_{ij}=1\\}.$

It follows from the above that $F$ maps distinct matrices to non-isomorphic
structures in $\mathscr{C}$. Indeed: for the transduction $T$ defined above,
$T(F(m,n,M))$ uniquely determines $m,n$ and $M$. This proves the lemma. ∎

This completes the proof of Proposition 4.1, and hence Proposition 3.4. (See
Corollary 5.8 below for a generalization to arbitrary binary signatures). ∎

######  Corollary 4.5.

$\mathscr{C}$ has unbounded twin-width.

###### Proof.

If $\mathscr{C}$ has bounded twin-width then it does not interpret the class
of all graphs [BKTW20a] and is small [BGK+]. ∎

##  5 From quantifier-free grids to regular semigrids

In this section we prove Theorem 3.3, which we recall below, generalized to
arbitrary binary signatures $\Sigma$:

######  Theorem 5.1.

Let $\mathscr{C}$ be a hereditary class of ordered binary structures graphs.
If $\mathscr{C}$ defines large grids using a quantifier-free formula, then
$\mathscr{C}$ contains arbitrarily large regular $n\times n$-semigrids.

In particular, we need to define the notion of a regular semigrid for an
arbitrary binary signature $\Sigma$.

Before doing this, we introduce the relevant result from Ramsey theory. Let an
_ordered $m\times n$ grid_ be the relational structure with domain
$[m]\times[n]$ and two quasi-orders $\leqslant_{1}$ and $\leqslant_{2}$, where
two points $(i,j),(i^{\prime},j^{\prime})$ are related by $\leqslant_{1}$ if
and only if $i\leqslant i^{\prime}$ and are related by $\leqslant_{2}$ if and
only if $j\leqslant j^{\prime}$. A _pair coloring_ of such an ordered $m\times
n$ grid is a function $c\colon([m]\times[n])^{2}\to\Gamma$ to a fixed finite
set $\Gamma$ of _colors_. Such a coloring is _homogeneous_ if the color
$c(p,q)$ depends only on the atomic type of the pair $(p,q)$. In other words,
the color of a pair $(p,q)$ depends only on whether $p=q$, and if not, on the
quadrant or principle semi-axis in $\mathbb{Z}^{2}$ to which the vector $p-q$
belongs to. There are $9$ possible types, corresponding to the pairs in
$\\{<,=,>\\}^{2}$ describing the relations between $p$ and $q$ in each of the
two dimensions.

The following result is a special case of the so-called _product Ramsey
theorem_ (see e.g. Proposition 3 in [Bod15] in the special case of the full
product of two copies of $(\mathbb{Q},\leqslant)$. See also the historical
comment following it).

######  Lemma 5.2.

Fix a finite set of colors $\Gamma$. For every $m,n$ there are
$m^{\prime},n^{\prime}$ such that for every coloring $c$ of the ordered
$m^{\prime}\times n^{\prime}$ there is an induced substructure isomorphic to
the $m\times n$ grid for which the coloring induced by $c$ is homogeneous.

Fix a formula $\varphi(\bar{x},\bar{y},z)$, an ordered structure $\mathrm{S}$
and an $m\times n$ grid $(A,B,C)$ defined by $\varphi$ in $\mathrm{S}$. The
sets $A\subseteq\mathrm{S}^{\bar{x}}$ and $B\subseteq\mathrm{S}^{\bar{y}}$ are
ordered lexicographically with respect to the order on $\mathrm{S}$, and some
fixed enumeration of the tuples $\bar{x}$ and $\bar{y}$. Those two orders
induce two quasi-orders $\leqslant_{1},\leqslant_{2}$ on $C$, via the
bijection $\alpha\colon A\times B\to C$ defined by the formula $\varphi$.
Namely,
$\alpha(\bar{a},\bar{b})\leqslant_{1}\alpha(\bar{a}^{\prime},\bar{b}^{\prime})$
if and only if $\bar{a}\leqslant_{\textrm{lex}}\bar{a}^{\prime}$ and
$\alpha(\bar{a},\bar{b})\leqslant_{2}\alpha(\bar{a}^{\prime},\bar{b}^{\prime})$
if and only if $\bar{b}\leqslant_{\textrm{lex}}\bar{b}^{\prime}$.

Say that the grid $(A,B,C)$ is _homogeneous_ if for every
$(\bar{a},\bar{b}),(\bar{a}^{\prime},\bar{b}^{\prime})\in A\times
B\subseteq\mathrm{S}^{\bar{x}\bar{y}}$ the atomic type of
$(\bar{a},\bar{b},\bar{a}^{\prime},\bar{b}^{\prime},\alpha(\bar{a},\bar{b}),\alpha(\bar{a}^{\prime},\bar{b}^{\prime}))$
in $\mathrm{S}$ depends only on the atomic type of
$(\alpha(\bar{a},\bar{b}),\alpha(\bar{a}^{\prime},\bar{b}^{\prime}))$ in
$(C,\leqslant_{1},\leqslant_{2})$.

######  Lemma 5.3.

Fix a finite signature $\Sigma$ containing $\leqslant$ and a $\Sigma$-formula
$\varphi(\bar{x},\bar{y},z)$. For every $m,n$ there are
$m^{\prime},n^{\prime}$ such that if $\varphi$ defines an $m^{\prime}\times
n^{\prime}$ grid in an ordered $\Sigma$-structure $\mathrm{S}$ then $\varphi$
also defines an $m\times n$ homogeneous grid in $\mathrm{S}$.

###### Proof.

Let $\Gamma$ be the set of atomic $\Sigma$-types of tuples of length
$2(|\bar{x}|+|\bar{y}|+1)$. Apply Lemma 5.2 yielding numbers
$m^{\prime},n^{\prime}$.

Suppose $\varphi$ defines an $m^{\prime}\times n^{\prime}$ grid $(A,B,C)$ in
$\mathrm{S}$, and let $\alpha\colon A\times B\to C$ be the bijection defined
by $\varphi$. Consider $C$ with the two orders $\leqslant_{1}$ and
$\leqslant_{2}$ as described earlier, then $(C,\leqslant_{1},\leqslant_{2})$
is isomorphic to the ordered $m^{\prime}\times n^{\prime}$ grid. Color each
pair $(\alpha(\bar{a},\bar{b}),\alpha(\bar{a}^{\prime},\bar{b}^{\prime}))\in
C^{2}$ by the atomic type of the tuple
$(\bar{a},\bar{b},\bar{a}^{\prime},\bar{b}^{\prime},\alpha(\bar{a},\bar{b}),\alpha(\bar{a}^{\prime},\bar{b}^{\prime}))$
in $\mathrm{S}$.

By Lemma 5.2, $(C,\leqslant_{1},\leqslant_{2})$ contains a copy
$C^{\prime}\subseteq C$ of a homogeneous ordered $m\times n$-grid. Then
$\alpha^{-1}(C^{\prime})\subseteq A\times B$ and $C^{\prime}$ form a
homogeneous $m\times n$ grid defined by $\varphi$. ∎

We now generalize the notion of a regular semigrid from Section 4 to an
arbitrary relational binary signature $\Sigma$ containing the order symbol
$\leqslant$.

Fix $m,n\in\mathbb{N}$ and consider the ordered grid $(m+1)\times(n+1)$-grid
$(C,\leqslant_{1},\leqslant_{2})$ with domain $C=[m+1]\times[n+1]$ as
described above. Let $B=[0]\times[n+1]\subseteq C$, and let $\pi\colon C\to B$
be the projection mapping $(i,j)\in C$ to $(0,j)$.

A _regular $m\times n$-semigrid_ is an ordered $\Sigma$-structure $\mathrm{S}$
with domain $C$ such that the order $\leqslant$ of $\mathrm{S}$ agrees with
the natural lexicographic order on $C=[m+1]\times[n+1]$ or its inverse, and
for all $a,b\in B$ and $p,q\in C-B$:

  1. 1.

the atomic type of $(a,b)$ in $\mathrm{S}$ depends only on the atomic type of
$(a,b)$ in $(B,\leqslant)$;

  2. 2.

the atomic type of $(p,q)$ in $\mathrm{S}$ depends only on the atomic type of
$(p,q)$ in $(C,\leqslant_{1},\leqslant_{2})$;

  3. 3.

the atomic type of $(p,b)$ in $\mathrm{S}$ depends only on the atomic type of
$(\pi(p),b)$ in $(B,\leqslant)$, and is non-constant.

A regular semigrid is completely specified by the dimensions $m\times n$, the
information ($<$ or $>$) about whether or not to reverse the lexicographic
order, as well as a tuple of functions describing the dependencies as above.
For example, the dependencies (1) and (3) above are each specified by a
function from $\\{<,=,>\\}$ to the set $T$ of atomic $\Sigma$-types of pairs,
whereas the dependency (2) is specified by a function from $\\{<,=,>\\}^{2}$
to $T$. In total, all the dependencies are described by a tuple in
$T^{3+3+9}=T^{15}$ (with some tuples being excluded due to the non-constant
requirement, and some being unsatisfiable in an ordered structure). Let
$\mathrm{Schemes}=\\{<,>\\}\times T^{15}$ denote the set of possible choices,
called _schemes_.

As $|T|\leqslant 4^{|\Sigma|}$, we get the following.

######  Lemma 5.4.

For every $n\geqslant 1$ there are at most $2^{\mathcal{O}(|\Sigma|)}$
distinct regular $n\times n$-semigrids, and they can be enumerated in time
$2^{\mathcal{O}(|\Sigma|)}\cdot\textit{poly}(n)$.

######  Lemma 5.5.

Assume $\Sigma=\\{E,\leqslant\\}$ consists only of the edge symbol $E$ and
order symbol $\leqslant$. Then an ordered graph is a regular semigrid in the
sense of Section 4 if and only if it is a regular semigrid as defined above.

###### Proof sketch.

In one direction, suppose $G$ is a regular semigrid in the sense of Section 4
with intervals $I_{0},\ldots,I_{m}$ of size $n+1$, and assume
$I_{0}<I_{1}<\ldots<I_{m}$ (in the other case reverse the order of $G$).
Arrange $I_{0},\ldots,I_{m}$ in a grid $C=[m+1]\times[n+1]$ by placing $I_{0}$
in the first row, $I_{1}$ in the second, etc. Then the order of $G$ on
$I_{0}\cup\ldots\cup I_{m}$ agrees with the lexicographic order on
$C=[m+1]\times[n+1]$, and the conditions (1)-(3) in the definition above hold.

The other direction is similar. ∎

######  Lemma 5.6.

For any class $\mathscr{C}$ of ordered $\Sigma$-structures which contains
arbitrarily large $n\times n$-semigrids there is a quantifier-free
interpretation $I\colon\Sigma\to\\{E,\leqslant\\}$ such that $I(\mathscr{C})$
is a class of ordered graphs containing arbitrarily large regular $n\times
n$-semigrids.

###### Proof sketch.

We use the notation from the definition of regular semigrids above. Fix
$\sigma\in\mathrm{Schemes}$ such that there are arbitrarily large $n\times
n$-semigrids in $\mathscr{C}$ conforming to $\sigma$. Then $\sigma$ specifies
that the atomic type of $(p,q)$ in $\mathrm{S}$ depends in the same way on the
atomic type of $(\pi(p),b)$ in $(B,\leqslant)$; in particular, this dependency
is non-constant. Hence there are two distinct atomic types $\tau_{1},\tau_{2}$
which are realized as atomic types of pairs of the form $(\pi(p),b)$ for $b\in
B,p\in C-B$.

The interpretation $I$ is the interpretation with domain formula
$\delta(x)=(x=x)$, order formula $\varphi_{\leqslant}(x,y)=(x\leqslant y)$ and
edge formula $\varphi_{E}(x,y)=\tau_{1}(x,y)\lor\tau_{1}(y,x)$.

If $\mathrm{S}$ is a regular $m\times n$-semigrid of scheme $\sigma$ then
$I(\mathrm{S})$ is a regular $m\times n$-semigrid which is an ordered graph.
Indeed, since $I$ is quantifier-free, the atomic type of $(x,y)$ in
$I(\mathrm{S})$ depends only on the atomic type of $(x,y)$ in $\mathrm{S}$,
and hence the conditions in the definition of regularity are met. The non-
constancy condition is also satisfied by the choice of $\tau_{1}\neq\tau_{2}$.
∎

We now exhibit large regular semigrids in any class in which some quantifier-
free formula defines large grids.

######  Proposition 5.7.

Let $\mathscr{C}$ be a hereditary class of ordered structures over a finite
binary signature $\Sigma$ and let $\varphi(\bar{x},\bar{y},z)$ be a
quantifier-free formula which defines large grids in $\mathscr{C}$. Then
$\mathscr{C}$ contains arbitrarily large regular $n\times n$-semigrids.

###### Proof.

Fix a number $n$. By Lemma 5.3 $\varphi$ defines a homogeneous
$(n+1)\times(n+1)$ grid $(A,B,C)$ in some structure
$\mathrm{S}\in\mathscr{C}$. In particular, the atomic type
$\operatorname{atp}(\bar{a},\bar{b})$ does not depend on the choice of
$\bar{a}\in A$ and $\bar{b}\in B$.

As in the definition of homogeneity of the grid $(A,B,C)$, order
$A\subseteq\mathrm{S}^{\bar{x}}$ and $B\subseteq\mathrm{S}^{\bar{y}}$
lexicographically with respect to the order $\leqslant$ on $\mathrm{S}$ and
the fixed enumeration of $\bar{x}$ and $\bar{y}$. Let $\leqslant_{A}$ and
$\leqslant_{B}$ be the resulting orders of $A$ and $B$. This induces, via the
bijection $\alpha\colon A\times B\to C$ defined by $\varphi$, eight possible
lexicographic orders on $C$:

  * –

we may either order $A$ using $\leqslant_{A}$ or its inverse $\geqslant_{A}$,

  * –

we may either order $B$ using $\leqslant_{B}$ or its inverse $\geqslant_{B}$,

  * –

we may then order $C\simeq A\times B$ lexicographically using first the chosen
order on $A$ then the chosen order on $B$, or the other way around.

######  Claim 5.1.

The order $\leqslant$ on $C$ coincides with one of the $8$ orders above.

###### Proof.

For $\bar{a}\in A,\bar{b}\in B$ denote
$[\bar{a},\bar{b}]:=\alpha(\bar{a},\bar{b})$. Pick points
$\bar{a}<_{A}\bar{a}^{\prime}\in A$ and
$\bar{b}<_{B}\bar{b}^{\prime}<_{B}b^{\prime\prime}\in B$. Assume
$[\bar{a},\bar{b}]<[\bar{a},\bar{b}^{\prime}]$; otherwise replace
$\leqslant_{B}$ with $\geqslant_{B}$ in the following. Assume
$[\bar{a},\bar{b}^{\prime}]<[\bar{a},\bar{b}^{\prime}]$; otherwise replace
$\leqslant_{A}$ with $\geqslant_{A}$ in the following.

Let
$C^{\prime}=\\{[\bar{a},\bar{b}],[\bar{a},\bar{b}^{\prime}],[\bar{a},\bar{b}^{\prime\prime}],[\bar{a}^{\prime},\bar{b}^{\prime}]\\}\subseteq
C\subseteq A\times B$.

Compare $[\bar{a}^{\prime},\bar{b}^{\prime}]$ with
$[\bar{a},\bar{b}^{\prime\prime}]$. If
$[\bar{a}^{\prime},\bar{b}^{\prime}]<[\bar{a},\bar{b}^{\prime\prime}]$ then
$\leqslant$ coincides on $C^{\prime}$ with the lexicographic order which first
orders according to $\leqslant_{B}$ and then according to $\leqslant_{A}$.
Otherwise, if
$[\bar{a},\bar{b}^{\prime\prime}]<[\bar{a}^{\prime},\bar{b}^{\prime}]$ then
$\leqslant$ coincides on $C^{\prime}\subseteq C\simeq A\times B$ with the
lexicographic order which first orders according to $\leqslant_{A}$ and then
according to $\leqslant_{B}$. Let $\leqslant_{\mathrm{lex}}$ denote this among
those two lexicographic orders which agrees with $\leqslant$ on $C^{\prime}$.

By construction of $C^{\prime}$, for every pair of points
$c_{1}=[\bar{a}_{1},\bar{b}_{1}],c_{2}=[\bar{a}_{2},\bar{b}_{2}]$ in $C$,
there is a pair $c_{1}^{\prime},c_{2}^{\prime}$ in $C^{\prime}$ such that
$[c_{1}^{\prime},c_{2}^{\prime}]$ and $[c_{1},c_{2}]$ have equal atomic types
in $(C,\leqslant_{1},\leqslant_{2})$. It follows from homogeneity that
$\leqslant$ agrees of $\leqslant_{\mathrm{lex}}$ on all of $C$. ∎

Suppose that the order $\leqslant$ on $C$ coincides with one of the four
lexicographic orders where $A$ has higher priority than $B$ (otherwise replace
$B$ and $A$ in the argument), and the projection from $C\simeq A\times B$ to
$A$ is monotone rather than anti-monotone (otherwise replace $\leqslant$ with
$\geqslant$ in the argument).

Pick points $\bar{a}<\bar{a}^{\prime}$ in $A$ and $\bar{b}<\bar{b}^{\prime}$
in $B$ and let $c=[\bar{a},\bar{b}]\in C$, so that
$\varphi(\bar{a},\bar{b},c)$ holds.

######  Claim 5.2.

$\operatorname{atp}(\bar{b},c)\neq\operatorname{atp}(\bar{b}^{\prime},c)$.

###### Proof.

Note that
$\operatorname{atp}(\bar{a},\bar{b})=\operatorname{atp}(\bar{a},\bar{b}^{\prime})$
by homogeneity. If
$\operatorname{atp}(\bar{b},c)=\operatorname{atp}(\bar{b}^{\prime},c)$ then we
would have
$\operatorname{atp}(\bar{a},\bar{b},c)=\operatorname{atp}(\bar{a},\bar{b}^{\prime},c)$
since the signature is binary. This is a contradiction since $\varphi$ is
quantifier-free and holds of $(\bar{a},\bar{b}_{,}c)$ but not of
$(\bar{a},\bar{b}^{\prime},c).$ ∎

As $\Sigma$ is binary, there is a variable $y\in\bar{y}$ such that
$\operatorname{atp}(\bar{b}(y),c)\neq\operatorname{atp}(\bar{b}^{\prime}(y),c)$.
Let $B^{\prime}=\pi_{y}(B)\subseteq\mathrm{S}$ be the projection of
$B\subseteq\mathrm{S}^{\bar{y}}$ onto the $y$-component of $\bar{y}$.

It is now straightforward to verify that the substructure of $\mathrm{S}$
induced by $C\cup B^{\prime}$ is (isomorphic to) a regular $(n+1)\times
n$-semigrid. In particular, it contains a regular $n\times n$-semigrid as an
induced substructure. ∎

######  Corollary 5.8.

If $\mathscr{C}$ is a hereditary class of ordered $\Sigma$-structures
containing arbitrarily large regular $n\times n$-semigrids then:

  * –

$\mathscr{C}$ interprets all graphs,

  * –

$\mathscr{C}$ is not small,

  * –

model-checking first-order logic is AW[$\ast$]-hard on $\mathscr{C}$,

  * –

$\mathscr{C}$ has unbounded twin-width.

###### Proof.

Let $I$ be the quantifier-free interpretation from Lemma 5.6. Then
$I(\mathscr{C})$ is a class of ordered graphs that contains arbitrarily large
semigrids, hence satisfies the above conditions by Proposition 4.1. This
implies the same properties for $\mathscr{C}$. ∎

##  6 $(k,t)$-simplicity

In this section we prove Theorem 3.1, which is repeated below:

######  Theorem (3.1).

Every $(k,t)$-simple finite ordered binary structure has twin-width
$2^{2^{\mathcal{O}(kt)}}$.

We follow the general scheme of the proof of the implication
(2)$\rightarrow$(1) in Fact 1, presented in [BKTW20b, Section 5].

Instead of working with binary structures, we will consider their adjacency
matrices. An ordered $\Sigma$-structure $\mathrm{S}$ induces a square matrix,
called the _adjacency matrix_ of $\mathrm{S}$, whose rows and columns
correspond to the elements of $\mathrm{S}$, and where the entry at $(a,b)$ is
the atomic type $\operatorname{atp}(ab)$. In the case of ordered graphs, there
are five possible atomic types, depending on whether $a=b,a<b$ or $a>b$, and
on the adjacency between $a$ and $b$. All matrices below have ordered sets of
rows and columns.

###### Definition 5 ($(k,t)$-mixed minor).

Fix $k,t\in\mathbb{N}$. A _$(k,t)$ -mixed minor_ in a matrix $M$ is a convex
partition $\mathcal{R}$ of its rows and a convex partition $\mathcal{C}$ of
its columns, each with $t$ parts, such that for all $R\in\mathcal{R}$ and
$C\in\mathcal{L}$, the submatrix $M[R\times C]$ of $M$ has at least $k$
different columns or at least $k$ different columns.

Note that if a class $\mathscr{C}$ is $(k+1,t)$-simple then the adjacency
matrix of every $\mathrm{S}\in\mathscr{C}$ has no $(k,t)$-mixed minor.

We will use the following result due to Marcus and Tardos, concerning a
related notion, of _grid minors_ in $0$-$1$ matrices with many $1$’s.

###### Definition 6 (grid minor).

A _$t$ -grid minor_ in a $0$-$1$ matrix $M$ is a convex partition
$\mathcal{R}$ of its rows and a convex partition $\mathcal{C}$ of its columns,
each with $t$ parts, such that for all $R\in\mathcal{R}$ and
$C\in\mathcal{C}$, the submatrix $M[R\times C]$ has an entry $1$.

######  Theorem 6.1.

[MT04] For every $t\in\mathbb{N}$ there is a constant $c_{t}$ such that every
$m\times n$ $0$-$1$ matrix $M$ with at least $c_{t}\cdot\max(m,n)$ entries $1$
has a $t$-grid minor.

It is known [CK16] that $c_{t}=2^{\mathcal{O}(t)}$.

A row interval $R$ and a column interval $C$ are _homogeneous_ if the
submatrix $M[R\times C]$ of $M$ has all entries equal to each other. We will
consider pairs consisting of a convex partition $\mathcal{R}$ of the rows and
of a convex partition $\mathcal{C}$ of the columns. Such a pair
$(\mathcal{R},\mathcal{C})$ has _red-degree_ at most $d$ if for each row part
$R\in\mathcal{R}$ there are at most $d$ column parts $C\in\mathcal{C}$ such
that $R$ and $C$ are not homogeneous, and symmetrically, for each column part
$C\in\mathcal{C}$ there are at most $d$ row parts $R\in\mathcal{R}$ such that
$R$ and $C$ are not homogeneous.

We prove the following, asymmetric variant of Theorem 3.1.

######  Proposition 6.2.

Fix $k$ and $t\in\mathbb{N}$. There is a constant $d=2^{2^{\mathcal{O}(tk)}}$
such that for every rectangular matrix $M$ with no $(k,t)$-mixed minor there
is a sequence

$\displaystyle(\mathcal{R}_{0},\mathcal{C}_{0}),(\mathcal{R}_{1},\mathcal{C}_{1}),\ldots,(\mathcal{R}_{l},\mathcal{C}_{l})$
(1)

of pairs of partitions (of the rows and columns of $M$, respectively) that is
maximal under refinement, and consists of pairs of red-degree at most $d$.

Here, maximality under refinement means:

  * –

$\mathcal{R}_{0}$ and $\mathcal{C}_{0}$ are both partitions into singletons,

  * –

$\mathcal{R}_{l}$ and $\mathcal{C}_{l}$ are both partitions with one part, and

  * –

if $1\leqslant i<l$ then $(\mathcal{R}_{i+1},\mathcal{C}_{i+1})$ either
$\mathcal{R}_{i+1}$ is obtained by merging two parts in $\mathcal{R}_{i}$ into
one and leaving $\mathcal{C}_{i+1}=\mathcal{C}_{i}$, or vice-versa.

Note that the partitions in Proposition 6.2 are not necessarily convex.

We proceed to the proof of Proposition 6.2. For the rest of Section 6, fix
constants $k$ and $t$ and a matrix $M$ with no $(k,t)$-mixed minor. We proceed
in two steps. The first step is:

######  Lemma 6.3.

There are constants $b=2c_{tk}$ and $c=k^{c_{tk}}$ depending on $k$ and $t$
only such $M$ has a maximal (under refinement) sequence

$\displaystyle(\mathcal{R}_{0},\mathcal{C}_{0}),(\mathcal{R}_{1},\mathcal{C}_{1}),\ldots,(\mathcal{R}_{l},\mathcal{C}_{l})$
(2)

of pairs of convex partitions of the rows and columns of $M$ such that the
following conditions hold for $0\leqslant i\leqslant l$:

  * –

for each row interval $R\in\mathcal{R}_{i}$ there is a set
$B\subseteq\mathcal{C}_{i}$ of at most $b$ column intervals such that $M$ has
at most $c$ distinct rows in $R\times\bigcup(\mathcal{C}_{i}-B)$, and

  * –

symmetrically for columns and rows exchanged.

To construct the sequence (2), we start with the partitions $\mathcal{R}_{0}$
and $\mathcal{C}_{0}$ of the rows and columns into singletons, and then
proceed by repeatedly merging either two adjacent parts of the row partition
or of the column partition so that the condition in the lemma above is
maintained. This is done in a greedy way, and we show that if the process is
blocked at some point, then $M$ must have a $(k,t)$-mixed minor, by the
Marcus-Tardos result.

The key lemma is:

######  Lemma 6.4.

Let $\mathcal{R}$ be a convex partition of the rows and $\mathcal{C}$ be a
convex partition of the columns of $M$, such that
$2|\mathcal{R}|\geqslant|\mathcal{C}|$. Then for some row interval
$R\in\mathcal{R}$ there is a set $B\subseteq\mathcal{C}$ of at most $2c_{tk}$
column intervals such that $M$ has at most $k^{c_{tk}}$ distinct rows in
$R\times\bigcup(\mathcal{C}-B)$.

###### Proof.

Fix a row interval $R\in\mathcal{R}$. A _minimal bad interval_ for $R$ is an
inclusion-minimal interval of columns $I$ such that $M[R\times I]$ contains at
least $k$ distinct rows. The first column in a minimal bad interval for $R$ is
a _bad column_ for $R$.

Consider the $\mathcal{R}\times\mathcal{C}$ matrix $N$ whose $(R,C)$-entry is
$1$ if $C$ contains a bad column for $R$, and $0$ otherwise. By the Marcus-
Tardos theorem, at least one of the following holds:

  1. (_a_)

some row $R\in\mathcal{R}$ in $N$ has less than $2c_{tk}$ many $1$’s, or

  2. (_b_)

$N$ has a $tk$-grid minor.

Assume case (_a_) holds. Let $B\subseteq\mathcal{C}$ be the set of columns $C$
such that the $(R,C)$-entry is a $1$. By assumption, $|B|<2c_{tk}$. Consider a
maximal interval in $I\subseteq\mathcal{C}$ not containing an element of $B$.
Then $I$ does not contain a minimal bad interval for $R$. In particular,
$M[R\times I]$ has fewer than $k$ distinct rows. Since $|B|<2c_{tk}$, there
are at most $2c_{tk}$ such intervals $I$. It follows that
$M[R\times(\bigcup\mathcal{C}-B)]$ has fewer than $k^{2c_{tk}}$ distinct rows,
yielding the conclusion of the lemma. It remains to prove that case (_b_)
cannot hold.

We show that case (_b_) would yield a $(k,t)$-mixed minor in $M$, contrary to
the assumption. Assume that $N$ has a $tk$-grid minor. This minor corresponds
to a convex coarsening $\mathcal{R}^{\prime}$ of $\mathcal{R}$ and a convex
coarsening $\mathcal{C}^{\prime}$ of $\mathcal{C}$ such that for all
$R\in\mathcal{R}^{\prime}$ and $C\in\mathcal{C}^{\prime}$, a bad column for
$R$ can be found in $C$. Moreover, $\mathcal{C}^{\prime}$ and
$\mathcal{R}^{\prime}$ have $tk$ parts each.

Let $\mathcal{C}^{\prime\prime}$ be the coarsening of $\mathcal{C}^{\prime}$
obtained by grouping parts of $\mathcal{C}^{\prime}$ by groups of size $k$, so
that each interval in $\mathcal{C}^{\prime\prime}$ is a union of $k$ intervals
in $\mathcal{C}^{\prime}$. Then $\mathcal{C}^{\prime\prime}$ has $t$ parts.

Fix a row interval $R\in\mathcal{R}^{\prime}$ and a column interval
$C\in\mathcal{C}^{\prime\prime}$. We claim that $M[R\times C]$ has at least
$k$ different columns.

By definition of $\mathcal{C}^{\prime\prime}$, there are $k$ columns
$c_{1}<\ldots<c_{k}$ in $C$ such that for each $1\leqslant i\leqslant k$,
column $c_{i}$ is bad for some row interval $R_{i}\in\mathcal{R}$ that is
contained in $R$. Let $I_{i}$ be the corresponding bad interval that starts at
column $c_{i}$. If some $I_{i}$ is contained in $C$ then we are done, since
$I_{i}$ witnesses that $M[R_{i}\times I_{i}]$ has at least $k$ different
columns, so even more so $M[R\times C]$.

Otherwise, every interval $I_{i}$ starts at $c_{i}\in C$ and extends beyond
$C$. We claim that then the columns $c_{1},\ldots,c_{k}$ of $M[R\times C]$ are
pairwise distinct. To this end, pick $1\leqslant i<j\leqslant k$; we show that
the columns $c_{i}$ and $c_{j}$ differ already within $M[R_{i}\times C]$.

Note that $c_{j}\in I_{i}$ since $I_{i}$ starts at $c_{i}$ and extends beyond
$C$, whereas $c_{i}<c_{j}\in C$. Since $I_{i}$ is a minimal bad interval for
$R_{i}$, the columns $c_{i}$ and $c_{j}$ of $M[R_{i}\times C]$ differ –
otherwise $M[R_{i}\times(I_{i}-\\{c_{i}\\})]$ would have the same set of
columns as $M[R_{i}\times I_{i}]$, contradicting minimality of $I_{i}$.

This proves that $M[R\times C]$ contains at least $k$ distinct columns, for
all $R\in\mathcal{R}^{\prime}$ and $C\in\mathcal{C}^{\prime\prime}$.
Coarsening $\mathcal{R}^{\prime}$ by grouping by $k$ parts, we get a convex
partition $\mathcal{R}^{\prime\prime}$ into $t$ parts. The partitions
$\mathcal{R}^{\prime\prime}$ and $\mathcal{C}^{\prime\prime}$ witness that $M$
has a $(k,t)$-mixed minor, contradicting the assumption. Hence, case (_b_)
cannot hold. ∎

###### Proof of Lemma 6.3.

We construct a sequence
$(\mathcal{R}_{0},\mathcal{C}_{0}),(\mathcal{R}_{1},\mathcal{C}_{1}),\ldots,(\mathcal{R}_{i},\mathcal{C}_{i})$
of pairs of convex partitions, satisfying the two conditions in the lemma, as
follows. $\mathcal{R}_{0}$ is the partition of the rows into singletons, and
$\mathcal{C}_{0}$ is the partition of the columns into singletons. For $i>0$,
construct $(\mathcal{R}_{i},\mathcal{C}_{i})$ from
$(\mathcal{R}_{i-1},\mathcal{C}_{i-1})$ as follows. Assume that
$|\mathcal{R}_{i-1}|\geqslant|\mathcal{C}_{i-1}|$, the other case being
symmetric. Group the parts of $\mathcal{R}_{i-1}$ by two, yielding a partition
$\mathcal{R}$ with $2|\mathcal{R}|\geqslant|\mathcal{C}_{i-1}|$. Apply Lemma
6.4, yielding some row interval $R\in\mathcal{R}$ for which there is a set
$B\subseteq\mathcal{C}_{i-1}$ of at most $2{c_{tk}}$ column intervals such
that $M$ has at most $k^{c_{tk}}$ distinct rows in
$R\times\bigcup(\mathcal{C}_{i-1}-B)$. The row interval $R\in\mathcal{R}$
corresponds to two adjacent row intervals in $\mathcal{R}_{i-1}$. Let
$\mathcal{R}_{i}$ be obtained from $\mathcal{R}_{i-1}$ by replacing those two
adjacent row intervals by their union $R$, and let
$\mathcal{C}_{i}=\mathcal{C}_{i-1}$. The above construction terminates once
both $\mathcal{R}_{i}$ and $\mathcal{C}_{i}$ have one part each. ∎

In the second step, we improve the sequence (2), yielding a sequence of pairs
of _not necessarily convex_ partitions with the properties described in the
following reformulation of Proposition 6.2. Below, $b=2c_{tk}$ and
$c=k^{c_{tk}}$ are the constants from Lemma 6.3.

######  Lemma 6.5.

There is a maximal (under refinement) sequence

$\displaystyle(\mathcal{R}_{0}^{\prime\prime},\mathcal{C}_{0}^{\prime\prime}),(\mathcal{R}_{1}^{\prime\prime},\mathcal{C}_{1}^{\prime\prime}),\ldots,(\mathcal{R}_{l}^{\prime\prime},\mathcal{C}_{l}^{\prime\prime})$
(3)

of pairs of partitions of the rows and columns of $M$ of red-degree at most
$d=2bc^{2}$.

###### Proof.

We start with the sequence (2) obtained from Lemma 6.3.

Fix $0\leqslant i\leqslant l$ and a row interval $R\in\mathcal{R}_{i}$. Let
$B\subseteq\mathcal{C}_{i}$ be as in the statement of Lemma 6.3, with
$|B|\leqslant b=2c_{tk}$. Then $M$ has $c=k^{c_{tk}}$ distinct rows in
$R\times\bigcup(\mathcal{C}_{i}-B)$. Partition $R$ into at most $c$ parts,
where two rows $r,r^{\prime}\in R$ are in the same part if they coincide on
each column in $\mathcal{C}_{i}-B$.

By doing this for every row interval $R$, we obtain a refinement
$\mathcal{R}_{i}^{\prime}$ of $\mathcal{R}_{i}$, in which every interval in
$\mathcal{R}_{i}$ is partitioned into at most $c$ parts in
$\mathcal{R}_{i}^{\prime}$. We proceed symmetrically with the columns,
yielding a refinement $\mathcal{C}_{i}^{\prime}$ of $\mathcal{C}_{i}$.

We show that the obtained sequence of pairs of partitions satisfies the
conditions of Lemma 6.5, apart from being a maximal chain under refinement.

By construction of $\mathcal{R}_{i}^{\prime}$ and $\mathcal{C}_{i}^{\prime}$,
we get:

######  Claim 6.1.

For each row part $R\in\mathcal{R}_{i}^{\prime}$ there is a set
$B^{\prime}\subseteq\mathcal{C}_{i}^{\prime}$ of at most $t^{\prime}=b\cdot c$
column parts such that for all $C\in\mathcal{C}_{i}^{\prime}-B^{\prime}$, all
entries in $M[R,C]$ are equal. Symmetrically for columns and rows exchanged.

Say that a partition $\mathcal{P}_{1}$ is an $r$-_coarsening_ of a partition
$\mathcal{P}_{2}$ if every part of $\mathcal{P}_{1}$ is union of at most $r$
parts of $\mathcal{P}_{2}$

######  Claim 6.2.

$\mathcal{R}_{i}^{\prime}$ is a $2c$-coarsening of
$\mathcal{R}_{i-1}^{\prime}$ and $\mathcal{C}_{i}^{\prime}$ is a
$2c$-coarsening of $\mathcal{C}_{i-1}^{\prime}$.

This claim, as well as the rest of the proof, proceed as in [BKTW20b, Proof of
Theorem 10]. In particular, applying Lemma 8 from there yields the sequence
(3) of red-degree $d=2c\cdot bc$. ∎

Lemma 6.5 yields Proposition 6.2.

To finish the proof of Theorem 3.1, we observe that the sequence (3) can be
made so that the partitions in each pair are equal, just as in [BKTW20b, Proof
of Theorem 14].

Observe that the construction above is effective, and yields the following:

######  Corollary 6.6.

Fix a binary signature $\Sigma$. There is an algorithm which, given an ordered
binary structure $\mathrm{S}$ and numbers $k,t\in\mathbb{N}$, terminates in
time polynomial in $|\mathrm{S}|$ with one of the following outcomes:

  * –

either a contraction sequence of $\mathrm{S}$ of red-degree bounded by
$2^{2^{\mathcal{O}(kt)}}$, or

  * –

a $(k,t)$-mixed minor in the adjacency matrix of $\mathrm{S}$.

##  7 Approximating twin-width

In this section we assume that we already know that every hereditary class
$\mathscr{C}$ of binary structures of unbounded twin-width contains
arbitrarily large regular semigrids. This will be proved in the following
sections using entirely different tools, but in this section we focus only on
the algorithmic application of this fact. We prove:

######  Theorem 7.1 (1.3).

There is a computable function $f\colon\mathbb{N}\to\mathbb{N}$ and an
algorithm which inputs an ordered binary structure $\mathrm{S}$, and computes
in time polynomial in $|\mathrm{S}|$ a contraction sequence of $\mathrm{S}$ of
red-degree at most $f(\operatorname{tww}(\mathrm{S}))$.

######  Corollary 7.2.

Fix a binary signature $\Sigma$. There is a computable function
$g\colon\mathbb{N}\times\mathbb{N}\to\mathbb{N}$, a constant $c\in\mathbb{N}$
and an algorithm which given a binary ordered structure $\mathrm{S}$ and a
first-order sentence $\varphi$, determines whether $\mathrm{S}\models\varphi$
in time $g(|\varphi|,\operatorname{tww}(\mathrm{S}))\cdot|\mathrm{S}|^{c}$. In
other words, model-checking first-order logic is fixed-parameter tractable on
ordered, binary structures, with the parameter being the formula $\varphi$ and
the twin-width of the input structure.

###### Proof.

Follows from Theorem 1.3 and [BKTW20a, Theorem 1] according to which a there
is an algorithm which given a first-order sentence $\varphi$ and a binary
structure $\mathrm{S}$ together with a contraction sequence of red-degree at
most $d$ determines if $\mathrm{S}\models\varphi$ in time
$h(d,\varphi)\cdot|\mathrm{S}|^{c}$, for some computable function $h$ and
constant $c\in\mathbb{N}$. ∎

Fix an ordered binary structure $\mathrm{S}$ and define the following two
parameters:

  * –

$\mathrm{max\text{-}semigrid}(\mathrm{S})$: the maximal number $n$ such that
some regular $n\times n$-semigrid is an induced substructure of $\mathrm{S}$,

  * –

$\mathrm{simplicity}(\mathrm{S})$: the least number $k$ such that $\mathrm{S}$
is $(k,k)$-simple.

Clearly, both functions are computable.

For two functions $p,q$ mapping $\Sigma$-structures to numbers, write
$p\preccurlyeq q$ if there is a computable function
$\alpha\colon\mathbb{N}\to\mathbb{N}$ such that
$p(\mathrm{S})\leqslant\alpha(q(\mathrm{S}))$ for all finite ordered
$\Sigma$-structures $\mathrm{S}$.

######  Lemma 7.3.

We have:

$\operatorname{tww}\preccurlyeq\mathrm{simplicity}\preccurlyeq\mathrm{max\text{-}semigrid}\preccurlyeq\operatorname{tww}.$

###### Proof.

The first inequality is by Theorem 3.1.

We show the second inequality. Fix $k\in\mathbb{N}$. Let $\mathcal{F}_{k}$
denote the family of all minimal (under induced substructure) structures
$\mathrm{S}$ which are not $(k-1,k-1)$-simple. In particular, every
$\mathrm{S}$ with $\mathrm{simplicity}(\mathrm{S})\geqslant k$ contains at
least one structure in $\mathcal{F}_{k}$ as an induced substructure.

######  Claim 7.1.

The family $\mathcal{F}_{k}$ is finite (up to isomorphism) and its
representatives are effectively computable, given $k$.

###### Proof.

A $(k,t)$-mixed minor in a matrix $M$ is exhibited by a set $R$ of at most
$kt^{2}$ rows and a set $C$ of at most $kt^{2}$ columns (in each of the
$t^{2}$ zones leave $k$ distinct rows and $k$ distinct columns). If $M$ is the
adjacency matrix of a binary ordered structure $\mathrm{M}$, then the rows and
columns are indexed by the same set $\mathrm{M}$, so $R\cup
C\subseteq\mathrm{M}$. Then the substructure of $\mathrm{M}$ induced by $R\cup
C$ has a $(k,t)$-mixed minor and has size $|\mathrm{M}|\leqslant 2kt^{2}$.

This shows that every structure that is not $(k,t)$-simple contains an induced
substructure of size at most $2kt^{2}$ which is not $(k,t)$-simple. Hence, the
family of minimal structures that are not $(k,t)$-simple is finite and can be
effectively enumerated by checking all structures of size $2kt^{2}$. ∎

Denote

$\alpha(k):=\min\\{\mathrm{max\text{-}semigrid}(\mathrm{S})\mid\mathrm{S}\in\mathcal{F}_{k}\\}.$

The function $\alpha$ is computable by the claim above. By construction, if
$\mathrm{simplicity}(\mathrm{S})=k$ then $\mathrm{S}$ has some structure in
$\mathcal{F}_{k}$ as an induced substructure, and hence also some semigrid of
size $\alpha(k)$. This proves
$\mathrm{max\text{-}semigrid}(\mathrm{S})\geqslant\alpha(\mathrm{simplicity}(\mathrm{S}))$.
Hence,
$\mathrm{simplicity}(\mathrm{S})\leqslant\alpha^{-1}(\mathrm{max\text{-}semigrid}(\mathrm{S}))$,
proving $\mathrm{simplicity}\preccurlyeq\mathrm{max\text{-}semigrid}$.

Finally, we prove
$\mathrm{max\text{-}semigrid}\preccurlyeq\operatorname{tww}$.

By Lemma 4.3 and Lemma 5.6 there is a fixed transduction $T$ such that for any
regular $k\times k$-semigrid $\mathrm{K}$ over the signature $\Sigma$, the set
of outputs $T(\mathrm{K})$ contains the set $B_{k}$ of all bipartite graphs
with two parts of size $k$ The transduction $T$ nondeterministically guesses a
subset of a given $k\times k$-semigrid $\mathrm{K}$ corresponding to some set
$S\subseteq\\{1,\ldots,k\\}\times\\{1,\ldots,k\\}$ and guesses the scheme
$\sigma$ (now in the signature of ordered graphs) and then applies the
interpretation $I$ from Lemma 5.6 (converting the regular semigrid over
$\Sigma$ to a graph semigrid) followed by $I_{\sigma}$ from Lemma 4.3,
converting a regular $k\times k$-semigrid $G$ with a chosen set
$S\subseteq\\{1,\ldots,k\\}\times\\{1,\ldots,k\\}$ into the bipartite graph
corresponding to $S$.

We can furthermore assume that $T(\mathrm{S}^{\prime})\subseteq T(\mathrm{S})$
for any $\mathrm{S}$ and its induced substructure $\mathrm{S}^{\prime}$, as
$T$ may first restrict the domain of the input structure using a unary
predicate.

By [BKTW20b, Theorem 39], there is a computable function $\beta$ (depending on
$T$) such that
$\operatorname{tww}(T(\mathrm{S}))\leqslant\beta(\operatorname{tww}(\mathrm{S}))$
(in the left-hand side $T(\mathrm{S})$ is a set $X$ of structures, so
$\operatorname{tww}(X)=\max_{\mathrm{S}^{\prime}\in
X}\operatorname{tww}(\mathrm{S}^{\prime}))$.

Suppose $\mathrm{max\text{-}semigrid}(\mathrm{S})=k$. Then $\mathrm{S}$
contains a $k\times k$-regular semigrid $\mathrm{K}$, so
$T(\mathrm{S})\supseteq B_{k}$ and:

$\beta(\operatorname{tww}(\mathrm{S}))\geqslant\operatorname{tww}(T(\mathrm{S}))\geqslant\operatorname{tww}(B_{k})=:\gamma(k),$

where $\gamma(k)$ is a computable function which is unbounded, as the class of
all bipartite graphs has unbounded twin-width.

Hence $k\leqslant\gamma^{-1}(\beta(\operatorname{tww}(\mathrm{S})))$, proving
$\mathrm{max\text{-}semigrid}\preccurlyeq\operatorname{tww}$. ∎

We now prove Theorem 1.3.

###### Proof of Theorem 1.3.

Given a structure $\mathrm{S}$, the algorithm proceeds as follows. For each
$k=1,2,\ldots,n$, run the algorithm from Corollary 6.6, until encountering the
smallest number $k$ for which the algorithm returns a contraction sequence of
red-degree $d=2^{2^{\mathcal{O}(k^{2})}}$. This contraction sequence is the
result of our algorithm. We now provide an upper bound on $d$ in terms of
$\operatorname{tww}(\mathrm{S})$.

We have that $\mathrm{simplicity}(\mathrm{S})\geqslant k$, since the algorithm
did not succeed for the value $k-1$. As
$\mathrm{simplicity}\preccurlyeq\operatorname{tww}$, this shows that
$\operatorname{tww}(\mathrm{S})\geqslant\alpha(k)$ for some computable
function, and hence $k\leqslant\alpha^{-1}(\operatorname{tww}(\mathrm{S}))$,
and so $d=2^{2^{\mathcal{O}(k^{2})}}$ is bounded by a computable function of
$\operatorname{tww}(\mathrm{S})$. ∎

##  8 Model-theoretic characterisations

In this section, we present our model-theoretic characterisations of classes
of bounded twin-width, as well as prove more general results concerning
arbitrary classes of structures. Among others, this will prove Theorem 3.2 and
Theorem 1.2.

We start with introducing the relevant notions from model theory.

###  8.1 Monadically NIP classes

#### Monadically NIP classes

A formula $\varphi(\bar{x},\bar{y})$ defines in a structure $\mathrm{S}$ a
bipartite graph with parts $\mathrm{S}^{\bar{x}}$ and $\mathrm{S}^{\bar{y}}$,
in which two tuples $\bar{a}\in\mathrm{S}^{\bar{x}}$ and
$\bar{b}\in\mathrm{S}^{\bar{y}}$ are adjacent if $\varphi(\bar{a},\bar{b})$
holds in $\mathrm{S}$.

###### Definition 7.

A class of structures $\mathscr{C}$ is _NIP_ if for every formula
$\varphi(\bar{x},\bar{y})$ there is a finite bipartite graph $H$ which does
not occur as an induced subgraph of $\varphi(\mathrm{S})$, for all
$\mathrm{S}\in\mathscr{C}$.

For example, the class of all cliques is NIP, whereas the class $\mathscr{C}$
of all finite graphs is not, since the edge formula $E(x,y)$ may define
arbitrary bipartite graphs in $\mathscr{C}$. As another example, consider the
class of all cliques with each edge subdivided: an additional vertex placed in
the middle of each edge. This class is NIP – intuitively, one cannot define
much more in such a graph than in a usual clique. However, this changes if one
can remove some of the newly inserted vertices and the edges incident to them
– this way, we can obtain any graph $G$ with each edge subdivided, and hence,
very complex graphs can be obtained. The same is true if instead of removing
the vertices, we can color some of the vertices by adding unary predicates,
and use those predicates in the formulas.

###### Definition 8 (Monadic NIP).

A class of structures $\mathscr{C}$ is _monadically NIP_ if every expansion
$\mathscr{C}^{\prime}$ of $\mathscr{C}$ by unary predicates is NIP (here
$\mathscr{C}^{\prime}$ is such that every structure from
$\mathrm{S}^{\prime}\in\mathscr{C}^{\prime}$ is obtained from some structure
in $\mathrm{S}\in\mathscr{C}$ by equipping $\mathrm{S}$ with arbitrarily many
unary predicates).

In particular, if $\mathscr{C}$ is monadically NIP then the hereditary closure
of $\mathscr{C}$ is also monadically NIP, since removing vertices can be
simulated by coloring them. The following fact essentially says that it is
enough to consider formulas $\varphi(x,y)$ with just two variables when
considering monadic NIP.

###### Definition 9 (Finitely monadically NIP).

A class of structures $\mathscr{C}$ is _finitely monadically NIP_ (_fmNIP_) if
every expansion of $\mathscr{C}$ by finitely many unary predicates that are
interpreted in structures from $\mathscr{C}$ as _finite sets_ is NIP.

The following lemma is immediate.

######  Lemma 8.1.

  1. 1.

The class of all finite graphs is not NIP.

  2. 2.

A class of finite structures is monadically NIP if and only if it is fmNIP.

The following proposition is a restatement of a result of the first author
[Sim21], see Appendix A.5 for more details.

######  Proposition 8.2 ([Sim21]).

The following conditions are equivalent for a class of structures
$\mathscr{D}$:

  * –

$\mathscr{D}$ is not NIP,

  * –

there is a formula $\varphi(x,y;\bar{z})$ such that for every $n$ there is a
structure $\mathrm{M}\in\mathscr{D}$ and a tuple
$\bar{c}\in\mathrm{M}^{\bar{z}}$ such that
$\varphi(\mathrm{M};\bar{c})\subseteq\mathrm{M}^{2}$ defines a binary relation
of VC-dimension at least $n$;

######  Corollary 8.3.

The following conditions are equivalent for a class of structures
$\mathscr{C}$:

  1. 1.

$\mathscr{C}$ does not transduce the class of all finite graphs;

  2. 2.

$\mathscr{C}$ is not monadically NIP.

Corollary 8.3 also follows from results of Baldwin and Shelah [BS85].

Together with Fact 2 this gives:

######  Corollary 8.4.

Every class of bounded twin-width is monadically NIP.

Finitely monadically NIP classes do not define large grids (cf. Def. 4):

######  Lemma 8.5.

If $\mathscr{C}$ is fmNIP then $\mathscr{C}$ does not define large grids.

###### Proof.

Observe that if $\varphi(\bar{x},\bar{y},z)$ defines a grid $(A,B,C)$ in a
structure $\mathrm{S}$ then for every binary relation $R\subseteq A\times B$
there is a unary predicate $U\subseteq C$ such that the formula

$\psi(\bar{x},\bar{y}):=\exists z.\varphi(\bar{x},\bar{y},c)\land U(z)$

defines $R$, so that for all $\bar{a}\in A$ and $\bar{b}\in B$,

$(\bar{a},\bar{b})\in
R\quad\Leftrightarrow\quad\mathrm{S}\models\psi(\bar{a},\bar{b}).$

In particular, if $|A|=n$ and $|B|=2^{n}$ then for a suitably chosen
$U\subseteq C$, the formula $\psi$ defines a relation of VC-dimension $n$
between $A$ and $B$.

Consider the expansion of $\mathscr{C}$ by a unary predicate $U$ interpreted
as finite sets. Then the formula $\psi(\bar{x},\bar{y})$ above has unbounded
VC-dimension on $\mathscr{C}$, proving that $\mathscr{C}$ is not fmNIP. ∎

###  8.2 1-dimensionality

We now introduce a wholly model-theoretic notion characterizing bounded twin-
width. For this, we first recall some basic notions from model theory.

By a _model_ we mean a structure which is typically infinite, as opposed to
the structures considered earlier, which were typically finite. We give a
brief account of basic notions from model theory in Appendix A, although they
are not needed to follow the main text below.

The _elementary closure_ of a class of structures $\mathscr{C}$ is the class
of all models $\mathrm{M}$ that satisfy every sentence $\varphi$ that holds in
all structures $\mathrm{S}\in\mathscr{C}$. In particular, if $\mathscr{C}$
does not define large grids, then neither does its elementary closure. This is
because for any fixed $n\in\mathbb{N}$ the existence of an $n\times n$-grid
defined by a fixed formula $\varphi(\bar{x},\bar{y},z)$ can be expressed by a
first-order sentence $\varphi^{\prime}$ which existentially quantifies
$(|\bar{x}|+|\bar{y}|)\cdot n+n^{2}$ variables, corresponding to sets $A,B,C$
of $\bar{x}$-tuples, $\bar{y}$-tuples and single vertices, and then checks
that $\varphi$ defines a bijection between $A\times B$ and $C$.

By the compactness theorem (cf. Thm. A.1), if $\mathscr{C}$ defines large
grids, then its elementary closure contains a structure that defines a grid
$(A,B,C)$ with $A$ and $B$ of arbitrarily large infinite cardinalities.

###### Definition 10 (Elementary extension).

Let $\mathrm{M},\mathrm{N}$ be two models. Then $\mathrm{N}$ is an _elementary
extension_ of $\mathrm{M}$, written $\mathrm{M}\prec\mathrm{N}$, if the domain
of $\mathrm{M}$ is contained in the domain of $\mathrm{N}$, and for every
formula $\varphi(\bar{x})$ and tuple $\bar{a}\in\mathrm{M}^{\bar{x}}$ of
elements of $\mathrm{M}$,

$\mathrm{M}\models\varphi(\bar{a})\text{\quad if and only if
\quad}\mathrm{N}\models\varphi(\bar{a}).$

In other words, it doesn’t matter if we evaluate formulas in $\mathrm{M}$ or
in $\mathrm{N}$. In particular, $\mathrm{M}$ and $\mathrm{N}$ satisfy the same
sentences.

A _formula $\varphi(\bar{x})$ with parameters_ from $C\subseteq\mathrm{N}$ is
a formula using constant symbols denoting elements from $C$. Such a formula
can be evaluated in $\mathrm{N}$ on a tuple $\bar{a}\in\mathrm{N}^{\bar{x}}$,
as expected. Note that if $\mathrm{M}\prec\mathrm{N}$ and $\varphi(\bar{x})$
is a formula with parameters from $\mathrm{N}$ and
$\bar{a}\in\mathrm{M}^{\bar{x}}$ then it is not necessarily the case that
$\mathrm{M}\models\varphi(\bar{a})$ if and only if
$\mathrm{N}\models\varphi(\bar{a})$, although this does hold for formulas with
parameters from $\mathrm{M}$.

###### Definition 11 (Independence).

Let $\mathrm{M}$ be a model and $\mathrm{N}$ its elementary extension. For a
tuple $\bar{a}\in\mathrm{N}^{\bar{x}}$ and a set $B\subseteq\mathrm{N}$ say
that $\bar{a}$ is _independent_ from $B$ over $\mathrm{M}$, denoted
$\bar{a}\mathrel{\mathop{\vbox{
\hbox{\oalign{\kern-1.29167pt\cr\hfil$|$\hfil\cr\kern-6.45831pt\cr$|$\cr\kern-1.29167pt\cr}}
}}\displaylimits_{\mathrm{M}}}B$, if for every formula $\varphi(\bar{x})$ with
parameters from $B\cup\mathrm{M}$ such that
$\mathrm{N}\models\varphi(\bar{a})$ there is some
$\bar{c}\in\mathrm{M}^{\bar{x}}$ such that
$\mathrm{N}\models\varphi(\bar{c})$.

Abusing notation, if $B$ is enumerated by a tuple $\bar{b}$, then we may write
$\bar{a}\mathrel{\mathop{\vbox{
\hbox{\oalign{\kern-1.29167pt\cr\hfil$|$\hfil\cr\kern-6.45831pt\cr$|$\cr\kern-1.29167pt\cr}}
}}\displaylimits_{\mathrm{M}}}\bar{b}$. We write $\mathrel{\mathop{\vbox{
\hbox{\oalign{\kern-1.29167pt\cr\hfil$\nmid$\hfil\cr\kern-6.45831pt\cr$|$\cr\kern-1.29167pt\cr}}
}}\displaylimits_{\mathrm{M}}}$ for the negation of the relation
$\mathrel{\mathop{\vbox{
\hbox{\oalign{\kern-1.29167pt\cr\hfil$|$\hfil\cr\kern-6.45831pt\cr$|$\cr\kern-1.29167pt\cr}}
}}\displaylimits_{\mathrm{M}}}$.

###### Example 8.1.

Let $\mathrm{N}$ be $(\mathbb{R},\leqslant)$ and let $\mathrm{M}$ be the union
of the open intervals $]0,1[$ and $]8,9[$, equipped with the relation
$\leqslant$. Then $\mathrm{M}\prec\mathrm{N}$. This is easy to derive from the
fact that $(\mathbb{R},\leqslant)$ has quantifier elimination, that is, every
formula $\varphi(\bar{x})$ is equivalent to a quantifier-free formula.

Figure 4: The structures $\mathrm{M}\prec\mathrm{N}$, a set $B$ and two
tuples, $\bar{a},\bar{e}$, with $\bar{a}\mathrel{\mathop{\vbox{
\hbox{\oalign{\kern-1.29167pt\cr\hfil$|$\hfil\cr\kern-6.45831pt\cr$|$\cr\kern-1.29167pt\cr}}
}}\displaylimits_{\mathrm{M}}}B$ and $\bar{e}\mathrel{\mathop{\vbox{
\hbox{\oalign{\kern-1.29167pt\cr\hfil$\nmid$\hfil\cr\kern-6.45831pt\cr$|$\cr\kern-1.29167pt\cr}}
}}\displaylimits_{\mathrm{M}}}B$.

Figure 4 illustrates independence over $\mathrm{M}$.

###### Example 8.2.

Let $\mathrm{M}\prec\mathrm{N}$. Then $\bar{a}\mathrel{\mathop{\vbox{
\hbox{\oalign{\kern-1.29167pt\cr\hfil$|$\hfil\cr\kern-6.45831pt\cr$|$\cr\kern-1.29167pt\cr}}
}}\displaylimits_{\mathrm{M}}}{}\mathrm{M}$ for every
$\bar{a}\in\mathrm{N}^{\bar{x}}$ (cf. Lemma A.3).

###### Definition 12 (1-dimensionality).

A model $\mathrm{M}$ is _1-dimensional_ if for every
$\mathrm{M}\prec\mathrm{N}$, tuples $\bar{a},\bar{b}$ of elements of
$\mathrm{N}$ and $c\in\mathrm{N}$ a single element, if
$\bar{a}\mathrel{\mathop{\vbox{
\hbox{\oalign{\kern-1.29167pt\cr\hfil$|$\hfil\cr\kern-6.45831pt\cr$|$\cr\kern-1.29167pt\cr}}
}}\displaylimits_{\mathrm{M}}}{}\bar{b}$ then $\bar{a}c\mathrel{\mathop{\vbox{
\hbox{\oalign{\kern-1.29167pt\cr\hfil$|$\hfil\cr\kern-6.45831pt\cr$|$\cr\kern-1.29167pt\cr}}
}}\displaylimits_{\mathrm{M}}}{}\bar{b}$ or $\bar{a}\mathrel{\mathop{\vbox{
\hbox{\oalign{\kern-1.29167pt\cr\hfil$|$\hfil\cr\kern-6.45831pt\cr$|$\cr\kern-1.29167pt\cr}}
}}\displaylimits_{\mathrm{M}}}{}\bar{b}c$. A class $\mathscr{C}$ of structures
is _1-dimensional_ if every model in the elementary closure of $\mathscr{C}$
is 1-dimensional.

###### Example 8.3.

Any total order $(X,\leqslant)$ is 1-dimensional. As an illustration, in the
situation in Fig. 4, consider the tuples $\bar{a},\bar{b}$ marked therein.
Then $\bar{a}\mathrel{\mathop{\vbox{
\hbox{\oalign{\kern-1.29167pt\cr\hfil$|$\hfil\cr\kern-6.45831pt\cr$|$\cr\kern-1.29167pt\cr}}
}}\displaylimits_{\mathrm{M}}}\bar{b}$. Let $c\in\mathrm{N}$. If $c$ belongs
to the interval $]b_{1},b_{2}[$ then $\bar{a}\mathrel{\mathop{\vbox{
\hbox{\oalign{\kern-1.29167pt\cr\hfil$|$\hfil\cr\kern-6.45831pt\cr$|$\cr\kern-1.29167pt\cr}}
}}\displaylimits_{\mathrm{M}}}\bar{b}c$. Otherwise,
$\bar{a}c\mathrel{\mathop{\vbox{
\hbox{\oalign{\kern-1.29167pt\cr\hfil$|$\hfil\cr\kern-6.45831pt\cr$|$\cr\kern-1.29167pt\cr}}
}}\displaylimits_{\mathrm{M}}}\bar{b}$.

###### Example 8.4.

Let $\mathrm{N}=(\mathbb{R}\times\mathbb{R},\sim_{1},\sim_{2})$ where for
$i=1,2$, the relation $\sim_{i}$ denotes equality of the $i$th coordinates.
Let $\mathrm{M}$ be the induced substructure of $\mathrm{N}$ with domain
$I\times I$ for some infinite subset $I\subseteq\mathrm{N}$. Then
$\mathrm{M}\prec\mathrm{N}$. In the situation depicted in Fig. 5,
$a\mathrel{\mathop{\vbox{
\hbox{\oalign{\kern-1.29167pt\cr\hfil$|$\hfil\cr\kern-6.45831pt\cr$|$\cr\kern-1.29167pt\cr}}
}}\displaylimits_{\mathrm{M}}}b$ but both $ac\mathrel{\mathop{\vbox{
\hbox{\oalign{\kern-1.29167pt\cr\hfil$\nmid$\hfil\cr\kern-6.45831pt\cr$|$\cr\kern-1.29167pt\cr}}
}}\displaylimits_{\mathrm{M}}}b$ and $a\mathrel{\mathop{\vbox{
\hbox{\oalign{\kern-1.29167pt\cr\hfil$\nmid$\hfil\cr\kern-6.45831pt\cr$|$\cr\kern-1.29167pt\cr}}
}}\displaylimits_{\mathrm{M}}}bc$. So $\mathrm{M}$ is not $1$-dimensional.

Figure 5: The structures $\mathrm{M}\prec\mathrm{N}$ and elements
$a,b,c\in\mathrm{N}$ with $a\mathrel{\mathop{\vbox{
\hbox{\oalign{\kern-1.29167pt\cr\hfil$|$\hfil\cr\kern-6.45831pt\cr$|$\cr\kern-1.29167pt\cr}}
}}\displaylimits_{\mathrm{M}}}b,ac\mathrel{\mathop{\vbox{
\hbox{\oalign{\kern-1.29167pt\cr\hfil$\nmid$\hfil\cr\kern-6.45831pt\cr$|$\cr\kern-1.29167pt\cr}}
}}\displaylimits_{\mathrm{M}}}b$ and $a\mathrel{\mathop{\vbox{
\hbox{\oalign{\kern-1.29167pt\cr\hfil$\nmid$\hfil\cr\kern-6.45831pt\cr$|$\cr\kern-1.29167pt\cr}}
}}\displaylimits_{\mathrm{M}}}bc$.

The following result is essentially [She86, Lemma 2.2].

######  Proposition 8.6.

If a model $\mathrm{M}$ does not define large grids the it is 1-dimensional.
More precisely, if there is a formula $\varphi(\bar{x},\bar{y},z)$ with
parameters from $\mathrm{M}$ which is satisfied by $\bar{a},\bar{b},c$ and
such that $\varphi(\bar{x},\bar{b},z)$ and $\varphi(\bar{x},\bar{b},c)$ are
not satisfiable in $\mathrm{M}$ then a boolean combination $\psi$ of instances
of $\varphi$ defines large grids in $\mathrm{M}$.

See Appendix C for a proof. In particular, every class $\mathscr{C}$ that does
not define large grids is 1-dimensional.

###  8.3 Regular classes

We now provide a characterization in terms of the number of types. The
definition below generalizes the definition of $(k,t)$-simplicity for ordered
structures.

Let $\varphi(x,\bar{y})$ be a formula and $\mathrm{S}$ a structure. A
_$\varphi$ -definable disjoint family_ is a family $\mathcal{R}$ of pairwise
disjoint of subsets of $\mathrm{S}$, where for each $R\in\mathcal{R}$ there is
$\bar{b}\in\mathrm{S}^{\bar{y}}$ with $R=\varphi(\mathrm{S},\bar{b})$. For
example, if $\mathrm{S}$ is an ordered structure and $\mathcal{R}$ is a convex
partition of $\mathrm{S}$, then $\mathcal{R}$ is a $\varphi$-definable family
of pairwise disjoint sets, for $\varphi(x,y_{1},y_{2})=y_{1}\leqslant
x\leqslant y_{2}$.

###### Definition 13 (Regularity).

A class $\mathscr{C}$ of structures is _regular_ if the following condition
holds. Let $\varphi(x;\bar{y})$, $\psi(x;\bar{z})$ and
$\theta(\bar{u};\bar{v})$ be $L$-formulas. Then there are natural numbers $t$
and $k$ such that for any $\mathrm{S}\in\mathscr{C}$ and any
$\varphi$-definable disjoint family $\mathcal{R}\subseteq P(\mathrm{S})$ and
$\psi$-definable disjoint family $\mathcal{L}\subseteq P(\mathrm{S})$ with
$|\mathcal{R}|=|\mathcal{L}|\geqslant t$ there are $R\in\mathcal{R}$ and
$L\in\mathcal{L}$ with $|\mathrm{Types}^{\theta}(R/L)|\leqslant k$.

Note that $|\mathrm{Types}^{\theta}(R/L)|\leqslant k$ implies
$|\mathrm{Types}^{\hat{\theta}}(L/R)|\leqslant 2^{k}$, where
$\hat{\theta}(\bar{v};\bar{u})=\theta(\bar{u};\bar{v})$. So in the definition
of regularity, we could equivalently require both
$|\mathrm{Types}^{\theta}(R/L)|\leqslant k$ and
$|\mathrm{Types}^{\hat{\theta}}(L/R)|\leqslant k$, as $k$ can be increased
appropriately.

It is easy to see that if $\mathscr{C}$ is regular class of ordered graphs
then $\mathscr{C}$ is $(k,t)$-simple for $k,t$ obtained from the definition of
regularity applied to the formulas $\varphi=y_{1}\leqslant x\leqslant y_{2}$
and $\psi=z_{1}\leqslant x\leqslant z_{2}$ and $\theta$ being the edge
relation. This also holds for arbitrary classes of ordered binary structures,
as
$|\mathrm{Types}^{\Sigma}(R/L)|\leqslant\prod_{S\in\Sigma}|\mathrm{Types}^{S}(R/L)|$.

###  8.4 Main model-theoretic result

[BKTW20b](cf. Fact. 2)Sec. 5, usesgrid RamseySec. 8 and 9,model-theoretic Sec.
6, usesMarcus-TardosSection 7[BGK+]Section 4trivial implicationassumes
hereditaritymodel-theoreticLem. 8.5Sec. 9[She86],cf. Prop. 8.6Sec. 5, usesgrid
Ramsey;assumes binary,ordered[She86],cf. Prop. 8.6Sec. 9Sec. 6, usesMarcus-
Tardos;assumes binary,finite, ordered[BKTW20a](cf. Fact 2)Cor. 7.2[BGK+]Prop.
4.1 Prop. 4.1Prop. 4.1[Sim21], [BS85](cf. Cor. 8.3)boundedtwin-widthdoes not
interpretall graphsfpt model-checkingsmallno large quantifier-free gridsno
large regular semigrids$(k,t)$-simpledoesn’t transduceall graphs
(1)monadically NIP (2)finitely monadically NIP (3)no large grids
(4)1-dimensional (5)regular (6)boundedtwin-width (7)doesn’t interpretall
graphs (8)fpt model-checkingsmallNIP (9)no large quantifier-free grids
(11)quantifier-free 1-dimensional (12)no large regular semigrids
(10)quantifier-free regular (13) Figure 6: Implications among the conditions
in Theorems 8.7 and 8.8. All implications apply to arbitrary classes of
structures, unless specified otherwise.

We can finally state our main model-theoretic result. It extends Theorem 1.2
stated in the introduction.

######  Theorem 8.7.

Let $\mathscr{C}$ be any class of structures over a relational signature and
consider the following conditions:

  1. 1.

$\mathscr{C}$ does not transduce the class of all finite graphs,

  2. 2.

$\mathscr{C}$ is monadically NIP,

  3. 3.

$\mathscr{C}$ is finitely monadically NIP,

  4. 4.

$\mathscr{C}$ does not define large grids,

  5. 5.

$\mathscr{C}$ is $1$-dimensional,

  6. 6.

$\mathscr{C}$ is regular.

Then the implications
(1)$\leftrightarrow$(2)$\rightarrow$(3)$\rightarrow$(4)$\rightarrow$(5)$\rightarrow$(6)
hold.

###### Proof.

The implications (1)$\leftrightarrow$(2)$\rightarrow$(3) follow from Corollary
8.3 and Lemma 8.1. Implication (3)$\rightarrow$(4) is by Lemma 8.5. The
implication (4)$\rightarrow$(5) is Proposition 8.6. The implication
(5)$\rightarrow$(6) is relegated to Section 9 below. ∎

For a class $\mathscr{C}$ of ordered structures over a binary signature we may
additionally prove the equivalence of all the above with $\mathscr{C}$ having
bounded twin-width and furthermore improve some of the conditions above to
obtain quantifier-free formulas, as follows. See Fig. 6 for a diagram of all
the various considered conditions and implications among them.

######  Theorem 8.8.

Let $\mathscr{C}$ be a class of ordered structures over a binary signature
$\Sigma$ and $\mathscr{C}^{\prime}$ be the hereditary class of all its finite
induced substructures. Then the following conditions are all equivalent to
each other and to the conditions (1)-(6):

  1. 7.

$\mathscr{C}^{\prime}$ has bounded twin-width,

  2. 8.

$\mathscr{C}^{\prime}$ does not interpret the class of all finite graphs,

  3. 9.

$\mathscr{C}^{\prime}$ is NIP,

  4. 10.

$\mathscr{C}^{\prime}$ does not contain arbitrarily large regular semigrids,

  5. 11.

no quantifier-free formula defines large grids in $\mathscr{C}$,

  6. 12.

(_quantifier-free 1-dim_.) let $\mathrm{M}\prec\mathrm{N}$ be models in the
elementary closure of $\mathscr{C}$,
$\bar{a}\in\mathrm{N}^{\bar{x}},\bar{b}\in\mathrm{N}^{\bar{y}}$ tuples with
$\bar{a}\mathrel{\mathop{\vbox{
\hbox{\oalign{\kern-1.29167pt\cr\hfil$|$\hfil\cr\kern-6.45831pt\cr$|$\cr\kern-1.29167pt\cr}}
}}\displaylimits_{\mathrm{M}}}\bar{b}$, and $c\in\mathrm{N}$; then there is no
quantifier-free formula $\varphi(\bar{x},\bar{y},z)$ such that
$\mathrm{N}\models\varphi(\bar{a},\bar{b},c)$ and such that both
$\varphi(\bar{x},\bar{b},z)$ and $\varphi(\bar{x},\bar{b},c)$ are not
satisfiable in $\mathrm{M}$,

  7. 13.

($(k,t)$-_simple_) there are some $k,t\in\mathbb{N}$ such that for every
structure $\mathrm{S}\in\mathscr{C}$ and two convex partitions ${\mathcal{L}}$
and ${\mathcal{R}}$ of $\mathrm{S}$ into $t$ parts, there are
$L\in\mathcal{L}$ and $R\in\mathcal{R}$ such that
$|\mathrm{Types}^{\Sigma}(L/R)|\leqslant k$ and
${|\mathrm{Types}^{\Sigma}(R/L)|\leqslant k}$.

###### Proof.

The implication (7)$\rightarrow$(8) is by Fact 2, the implication (8)
$\rightarrow$(10) is by Corollary 5.8, (10) $\rightarrow$(11) is by Theorem
5.1. The implication (11)$\rightarrow$(12) is by the refined statement in
Proposition 8.6. The implication (12)$\rightarrow$(13) is proved in Section 9
below, together with the implication (5)$\rightarrow$(6). The implication
(13)$\rightarrow$(7) is by Theorem 3.1. This proves the equivalence of the
conditions (7)-(13).

Equivalence with the conditions (1)-(6) follows since (7)$\rightarrow$(1) by
Fact 2, (3)$\rightarrow$(9)$\rightarrow$(8) are trivial, and
(6)$\rightarrow$(13) is immediate by the remark following Definition 13, as a
convex partition of $\mathrm{S}$ is a $\varphi$-definable disjoint family of
subsets of $\mathrm{S}$, for $\varphi(x,y_{1},y_{2})=y_{1}\leqslant x\leqslant
y_{2}$.

∎

Theorem 8.8 yields Theorem 3.2, and thus completes the proof of our two main
results, Theorem 1.1 and Theorem 1.2. It remains to prove implications
(5)$\rightarrow$(6) and (12)$\rightarrow$(13).

##  9 1-dimensional classes

In this section we prove that every 1-dimensional class is regular, and prove
the implication (12)$\rightarrow$(13) in Theorem 8.8. We start with very
briefly introducing some notions from model theory. A more comprehensive
overview is presented in Appendix A.

###  9.1 On independence

Let $\mathrm{M}\prec\mathrm{N}$. For two sets $A,B\subseteq\mathrm{N}$, write
$A\mathrel{\mathop{\vbox{
\hbox{\oalign{\kern-1.29167pt\cr\hfil$|$\hfil\cr\kern-6.45831pt\cr$|$\cr\kern-1.29167pt\cr}}
}}\displaylimits_{\mathrm{M}}}B$ if $\bar{a}\mathrel{\mathop{\vbox{
\hbox{\oalign{\kern-1.29167pt\cr\hfil$|$\hfil\cr\kern-6.45831pt\cr$|$\cr\kern-1.29167pt\cr}}
}}\displaylimits_{\mathrm{M}}}B$ for all tuples $\bar{a}$ of elements of $A$.
Note that $A\mathrel{\mathop{\vbox{
\hbox{\oalign{\kern-1.29167pt\cr\hfil$|$\hfil\cr\kern-6.45831pt\cr$|$\cr\kern-1.29167pt\cr}}
}}\displaylimits_{\mathrm{M}}}B$ if and only if
$\bar{a}\mathrel{\mathop{\vbox{
\hbox{\oalign{\kern-1.29167pt\cr\hfil$|$\hfil\cr\kern-6.45831pt\cr$|$\cr\kern-1.29167pt\cr}}
}}\displaylimits_{\mathrm{M}}}\bar{b}$ for all tuples $\bar{a}$ in $A$ and
$\bar{b}$ in $B$.

######  Lemma 9.1.

Fix a formula $\theta(\bar{u};\bar{v})$. Suppose $A\mathrel{\mathop{\vbox{
\hbox{\oalign{\kern-1.29167pt\cr\hfil$|$\hfil\cr\kern-6.45831pt\cr$|$\cr\kern-1.29167pt\cr}}
}}\displaylimits_{\mathrm{M}}}B$. Then for all $\bar{b}\in B^{\bar{u}}$, the
type $\operatorname{tp}^{\theta}(\bar{b}/A)$ depends only on the type
$\operatorname{tp}^{\theta}(\bar{b}/\mathrm{M})$. More precisely, there is a
function
$f\colon\mathrm{Types}^{\theta}(B/\mathrm{M})\to\mathrm{Types}^{\theta}(B/\mathrm{A})$
such that

$\operatorname{tp}^{\theta}(\bar{b}/A)=f(\operatorname{tp}^{\theta}(\bar{b}/\mathrm{M})).$

###### Proof.

We show that if
$\operatorname{tp}^{\theta}(\bar{b}/A)\neq\operatorname{tp}^{\theta}(\bar{b}^{\prime}/A)$
then
$\operatorname{tp}^{\theta}(\bar{b}/\mathrm{M})\neq\operatorname{tp}^{\theta}(\bar{b}/\mathrm{M})$.
If
$\operatorname{tp}^{\theta}(b/A)\neq\operatorname{tp}^{\theta}(b^{\prime}/A)$
then there is some $\bar{a}\in A^{\bar{v}}$ such that
$\theta(\bar{b},\bar{a})\triangle\theta(\bar{b}^{\prime},\bar{a})$. By
$A\mathrel{\mathop{\vbox{
\hbox{\oalign{\kern-1.29167pt\cr\hfil$|$\hfil\cr\kern-6.45831pt\cr$|$\cr\kern-1.29167pt\cr}}
}}\displaylimits_{\mathrm{M}}}B$ there is some
$\bar{m}\in\mathrm{M}^{\bar{v}}$ such that
$\theta(\bar{b},\bar{m})\triangle\theta(\bar{b}^{\prime},\bar{m})$, implying
$\operatorname{tp}^{\theta}(\bar{b}/A)\neq\operatorname{tp}^{\theta}(\bar{b}^{\prime}/A)$.
∎

As $|\mathrm{Types}(B/\mathrm{M})|\leqslant 2^{|\mathrm{M}|}$, we get a bound
on the number of types.

######  Corollary 9.2.

Fix a model $\mathrm{M}$ and its elementary extension $\mathrm{N}$. Let
$A,B\subseteq\mathrm{N}$ be such that $A\mathrel{\mathop{\vbox{
\hbox{\oalign{\kern-1.29167pt\cr\hfil$|$\hfil\cr\kern-6.45831pt\cr$|$\cr\kern-1.29167pt\cr}}
}}\displaylimits_{\mathrm{M}}}B$. For any formula $\theta(\bar{u};\bar{v})$
the set $\mathrm{Types}^{\theta}(B/A)$ has cardinality at most
$2^{|\mathrm{M}|}$.

The above bound can be leveraged to give a finite bound on the size of a set
of types, as follows.

######  Lemma 9.3.

Fix a model $\mathrm{M}$ and its elementary extension $\mathrm{N}.$ Let
$\varphi(x)$ and $\psi(x)$ be two formulas with parameters from $\mathrm{N}$.
Suppose that for every elementary extension $\mathrm{N}^{\prime}$ of
$\mathrm{N}$,

$\varphi(\mathrm{N}^{\prime})\mathrel{\mathop{\vbox{
\hbox{\oalign{\kern-1.29167pt\cr\hfil$|$\hfil\cr\kern-6.45831pt\cr$|$\cr\kern-1.29167pt\cr}}
}}\displaylimits_{\mathrm{M}}}\psi(\mathrm{N}^{\prime}).$

Then for every formula $\theta(\bar{u};\bar{v})$ the set
$\mathrm{Types}^{\theta}(\psi(\mathrm{N})/\varphi(\mathrm{N}))$ is finite.

###### Proof.

Fix a formula $\theta(\bar{u};\bar{v})$. Let
$E_{\theta}(\bar{u};\bar{u}^{\prime})$ be the formula defining the equivalence
relation on $\psi(\mathrm{N})^{\bar{u}}$ such that

$E_{\theta}(\bar{a},\bar{a}^{\prime})\quad\Leftrightarrow\quad\operatorname{tp}^{\theta}(\bar{a}/\varphi(\mathrm{N}))=\operatorname{tp}^{\theta}(\bar{a}^{\prime}/\varphi(\mathrm{N}))\qquad\qquad\text{for
$\bar{a},\bar{a}^{\prime}\in\psi(\mathrm{N})^{\bar{u}}$}.$

More precisely,

$E_{\theta}(\bar{u};\bar{u}^{\prime})\quad\equiv\quad\psi(\bar{u})\land\psi(\bar{u}^{\prime})\land\forall\bar{v}.\varphi(\bar{v})\implies(\theta(\bar{u};\bar{v})\iff\theta(\bar{u}^{\prime};\bar{v})).$

Suppose $E_{\theta}$ defines infinitely many classes in $\mathrm{N}$. By
compactness there is an elementary extension $\mathrm{N}^{\prime}$ of
$\mathrm{N}$ such that $E_{\theta}$ induces more than $2^{{|M|}}$ equivalence
classes in $\mathrm{N}^{\prime}$ (cf. Lemma A.2). By assumption,

$\varphi(\mathrm{N}^{\prime})\mathrel{\mathop{\vbox{
\hbox{\oalign{\kern-1.29167pt\cr\hfil$|$\hfil\cr\kern-6.45831pt\cr$|$\cr\kern-1.29167pt\cr}}
}}\displaylimits_{\mathrm{M}}}\psi(\mathrm{N}^{\prime}).$

By Corollary 9.2,
$\mathrm{Types}^{\theta}(\psi(\mathrm{N}^{\prime})/\varphi(\mathrm{N}^{\prime}))$
has cardinality at most $2^{{|M|}}$, which is in contradiction with the number
of classes of $E_{\theta}$ in $\mathrm{N}^{\prime}$. ∎

###### Remark 9.1.

To arrive at the conclusion of Lemma 9.3, the assumption
$\varphi(\mathrm{N}^{\prime})\mathrel{\mathop{\vbox{
\hbox{\oalign{\kern-1.29167pt\cr\hfil$|$\hfil\cr\kern-6.45831pt\cr$|$\cr\kern-1.29167pt\cr}}
}}\displaylimits_{\mathrm{M}}}\psi(\mathrm{N}^{\prime})$ can be weakened as
follows: for all $\bar{b},\bar{b}^{\prime}\in\mathrm{M}^{\bar{u}}$ and
$\sigma(\bar{v})=\theta(\bar{b};\bar{v})\triangle\theta(\bar{b}^{\prime};\bar{v})$,
if $\sigma(\bar{v})$ is satisfiable in $\varphi(\mathrm{N}^{\prime})$ then it
is satisfiable in $\mathrm{M}$. The same proof as above works, since $\sigma$
is the only formula that appears in the proof of Lemma 9.1.

###  9.2 Proof of (5)$\rightarrow$(6) and (12)$\rightarrow$(13)

Let $\mathscr{C}$ be a class which is not regular. We show that $\mathscr{C}$
is not 1-dimensional. We first construct a structure $\mathrm{M}$ in the
elementary closure of $\mathscr{C}$ that exhibits the lack of regularity in a
handy way.

Say that a class $\mathscr{C}$ is not regular _as witnessed_ by formulas
$\varphi(x,\bar{y}),\psi(x,\bar{z})$, $\theta(\bar{u},\bar{v})$ if for all
$k,t\in\mathbb{N}$ there are:

  * –

a structure $\mathrm{S}\in\mathscr{C}$,

  * –

a $\varphi$-definable disjoint family $\mathcal{R}\subseteq P(\mathrm{S})$
with $|\mathcal{R}|\geqslant t$,

  * –

a $\psi$-definable disjoint family $\mathcal{L}\subseteq P(\mathrm{S})$ with
$|\mathcal{L}|\geqslant t$,

such that

$|\mathrm{Types}^{\theta}(R/L)|>k\qquad\text{for all $R\in\mathcal{R}$ and
$L\in\mathcal{L}$.}$

If $\mathscr{C}$ is not regular then there are some $\varphi,\psi,\theta$ that
witness it.

###### Remark 9.2.

Suppose $\mathscr{C}$ is a class of ordered binary structures which is not
$(k,t)$-simple for all $k,t\in\mathbb{N}$. That is, for all $k,t\in\mathbb{N}$
there is a structure $\mathrm{S}\in\mathscr{C}$ and two convex partitions
${\mathcal{L}}$ and ${\mathcal{R}}$ of $\mathrm{S}$ into $t$ parts, there are
no $L\in\mathcal{L}$ and $R\in\mathcal{R}$ such that
$|\mathrm{Types}^{\Sigma}(L/R)|\leqslant k$ and
${|\mathrm{Types}^{\Sigma}(R/L)|\leqslant k}$. Then $\mathscr{C}$ is not
regular as witnessed by $\varphi(x,y_{1},y_{2})\equiv y_{1}\leqslant
x\leqslant y_{2}$ and $\psi(x,z_{1},z_{2})\equiv z_{1}\leqslant x\leqslant
z_{2}$ and $\theta(u,v)$ a quantifier-free $\Sigma$-formula with two
variables.

######  Lemma 9.4.

Suppose $\mathscr{C}$ is not regular, as witnessed by formulas
$\varphi(x,\bar{y}),\psi(x,\bar{z}),\theta(\bar{u},\bar{v})$. Then there
exist:

  * –

a structure $\mathrm{M}$ in the elementary closure of $\mathscr{C}$,

  * –

an elementary extension $\mathrm{N}$ of $\mathrm{M}$,

  * –

tuples $\bar{a}_{0},\bar{a}_{1}\in\mathrm{N}^{\bar{y}}$ and
$\bar{b}_{0}\in\mathrm{N}^{\bar{z}}$,

such that the following properties hold:

  1. 1.

$\operatorname{tp}(\bar{a}_{0}/\mathrm{M})=\operatorname{tp}(\bar{a}_{1}/\mathrm{M})$,

  2. 2.

the set $\mathrm{Types}^{\theta}(B/A)$ is infinite, where
$A=\varphi(\mathrm{N},\bar{a}_{1})$ and $B=\psi(\mathrm{N},\bar{b}_{0})$,

  3. 3.

$\bar{a}_{1}\mathrel{\mathop{\vbox{