# First Order Logic and Twin-Width
in Tournaments and Dense Oriented Graphs

Colin Geniet  and  Stéphan Thomassé  Laboratoire de l’Informatique du
Parallélisme, ENS de Lyon, 46 allée d’Italie, 69364 Lyon CEDEX 07, France
<EMAIL_ADDRESS>Laboratoire de l’Informatique du Parallélisme, ENS de
Lyon, 46 allée d’Italie, 69364 Lyon CEDEX 07, France  stephan.thomasse@ens-
lyon.fr

###### Abstract.

We characterise the classes of tournaments with tractable first-order model
checking. For every hereditary class of tournaments $\mathcal{T}$, first-order
model checking either is fixed parameter tractable, or is
$\textrm{AW}[*]$-hard. This dichotomy coincides with the fact that
$\mathcal{T}$ has either bounded or unbounded twin-width, and that the growth
of $\mathcal{T}$ is either at most exponential or at least factorial. From the
model-theoretic point of view, we show that NIP classes of tournaments
coincide with bounded twin-width. Twin-width is also characterised by three
infinite families of obstructions: $\mathcal{T}$ has bounded twin-width if and
only if it excludes at least one tournament from each family. This generalises
results of Bonnet et al. on ordered graphs.

The key for these results is a polynomial time algorithm which takes as input
a tournament $T$ and computes a linear order $<$ on $V(T)$ such that the twin-
width of the birelation $(T,<)$ is at most some function of the twin-width of
$T$. Since approximating twin-width can be done in polynomial time for an
ordered structure $(T,<)$, this provides a polytime approximation of twin-
width for tournaments.

Our results extend to oriented graphs with stable sets of bounded size, which
may also be augmented by arbitrary binary relations.

###### Key words and phrases:

Tournaments, twin-width, first-order logic, model checking, NIP, small classes

###### 2020 Mathematics Subject Classification:

Primary 05C20; Secondary 05C85, 03C13, 05C30

The authors were partially supported by the ANR projects TWIN-WIDTH
(ANR-21-CE48-0014-01) and DIGRAPHS (ANR-19-CE48-0013-01).

##  1\. Introduction

###  1.1. Parameterized problems in tournaments

Tournaments can represent the outcome of a ranking procedure on a set of
candidates, which in general need not be a total order. A well-known example
is the Condorcet voting paradox, where three referees whose preference lists
are $(A,B,C)$, $(B,C,A)$, and $(C,A,B)$ lead to a cycle $A\leftarrow
B\leftarrow C\leftarrow A$ in the ‘preferred over’ relation. This
interpretation leads to classical algorithmic problems when trying to choose a
subset of winners. For instance the Dominating Set (DS) problem on tournaments
can be understood as asking for a subset $D$ which is collectively preferred
to any other candidate, in the sense that for any $y\not\in D$, there is $x\in
D$ such that $x$ is preferred to $y$. The Feedback Vertex Set (FVS) problem
attempts to build a preference order—i.e. an acyclic graph—over the candidates
by ignoring a subset of candidates.

One can consider the parameterized version of these problems, asking for a
solution of size $k$—they are then denoted by $k$-DS, $k$-FVS. A problem
parameterized by $k$ is _fixed parameter tractable_ (FPT) if it admits an
algorithm running in time $O(f(k)n^{c})$ where $n$ is the size of the input.
For instance $k$-FVS is well-known to be FPT for tournaments (see Kumar and
Lokshtanov [22]), whereas $k$-DS is probably not FPT. However general
tournaments may not be representative of usual instances, for example,
majority voting tournaments involving $2r+1$ referees form a very restricted
class. A cornerstone paper by Alon et al. [2], based on Vapnik-Chervonenkis
dimension, shows that $k$-DS is trivially FPT on $(2r+1)$-majority tournaments
because the minimum size of a dominating set is bounded by $f(r)$. This
exemplifies how difficult problems can become easy on restricted classes, and
how complexity parameters (here bounded VC-dimension) can help to define
classes of tournaments.

To put these questions in a much broader perspective, remark that the previous
problems can be expressed in first-order logic (FO). The existence of a $k$-DS
is described by the formula

$\exists x_{1},x_{2},\dots,x_{k}.\forall y.\ (y\to x_{1})\lor\dots\lor(y\to
x_{k})$

(assuming $x\to x$ for all $x$ for simplicity). That $k$-FVS is also
expressible in first-order logic is worth mentioning, as this is only true in
tournaments, and not in general graphs. It is based on the simple remark that
a tournament is acyclic if and only if it is transitive, i.e. it has no
directed 3-cycle—the latter condition is easily expressed in FO. This makes
$k$-DS and $k$-FVS very specific instances of the FO Model Checking (or FOMC)
problem, which given as input a tournament $T$ and a first-order formula
$\phi$, asks if $T\models\phi$. FO model checking is difficult on the class of
all graphs [15], and using back-and-forth encodings expressible in first-order
logic, one can show that it is just as hard in general tournaments. Thus, one
cannot hope for substantial algorithmic results on first-order model checking
for arbitrary tournaments. Instead, we study the classes of tournaments in
which the problem is simple, meaning the classes of tournaments which admit a
FPT algorithm for FO model checking parameterized by the size of the given
formula.

###  1.2. Main results

We prove a dichotomy: in any class of tournaments $\mathcal{T}$ (closed under
taking subtournaments), FOMC is either FPT or $\textrm{AW}[*]$-hard. More
precisely, we show that the key of this dichotomy is _twin-width_ , a
complexity parameter introduced by Bonnet et al. [10], defined on arbitrary
binary structures. If $\mathcal{T}$ has bounded twin-width, then FOMC in
$\mathcal{T}$ is FPT, whereas it is $\textrm{AW}[*]$-hard when $\mathcal{T}$
has unbounded twin-width. This dichotomy also coincides with a model theoretic
characterisation: the class $\mathcal{T}$ has bounded twin-width if and only
if it is (monadically) NIP, which roughly speaking means that arbitrary graphs
cannot be described by use of tournaments in $\mathcal{T}$, and a fixed first-
order formula. In the vocabulary of [6], this proves that tournaments are
_delineated_ : every subclass is NIP if and only if it has bounded twin-width,
answering a question posed in [6]. The equivalence between NIP and FPT FO
model checking also confirms the _nowhere FO dense_ conjecture of Gajarský et
al. [19] in the case of tournaments.

The dichotomy for FO model checking in tournaments also coincides with a gap
in the growth function $g_{\mathcal{T}}(n)$ of the class $\mathcal{T}$,
defined as the number of tournaments of $\mathcal{T}$ with $n$ vertices
counted up to isomorphism. We show that $\mathcal{T}$ has bounded twin-width
if and only if its growth is at most $c^{n}$ for some constant $c$. To the
contrary, when twin-width is not bounded, the growth is at least
$(\left\lfloor n/2\right\rfloor-1)!$. This exponential/factorial gap can be
seen as a generalization of the Marcus-Tardos theorem on permutations avoiding
a fixed pattern [23]. It may also be compared to results of Boudabbous and
Pouzet [12] which imply that hereditary classes of tournaments have growth
either at most polynomial or at least exponential—the growth being polynomial
if and only if the class does not contain arbitrarily large tournaments with
no acyclic modules.

The following theorem summarises our results.

######  Theorem 1.1.

Let $\mathcal{T}$ be a hereditary class of tournaments. Under the assumption
$\textrm{FPT}\neq\textrm{AW}[*]$111The assumption is only used for conditions
2 and 3., the following are equivalent:

  1. (1)

$\mathcal{T}$ has bounded twin-width,

  2. (2)

FO model checking in $\mathcal{T}$ is FPT,

  3. (3)

FO model checking in $\mathcal{T}$ is not $\textrm{AW}[*]$-hard,

  4. (4)

$\mathcal{T}$ does not FO interpret the class of all graphs,

  5. (5)

$\mathcal{T}$ is monadically NIP, i.e. does not FO transduce all graphs,

  6. (6)

the growth of $\mathcal{T}$ is at most $c^{n}$ for some constant $c$,

  7. (7)

the growth of $\mathcal{T}$ is less than
$(\left\lfloor\frac{n}{2}\right\rfloor-1)!$.

These equivalences are completed by three minimal classes of obstructions,
characterising twin-width in terms of excluded substructures. These excluded
tournaments are encodings of arbitrary permutations.

######  Theorem 1.2.

There are three hereditary classes
$\mathcal{F}_{=},\mathcal{F}_{\leqslant},\mathcal{F}_{\geqslant}$ such that a
hereditary class $\mathcal{T}$ of tournaments has unbounded twin-width if and
only if one of
$\mathcal{F}_{=},\mathcal{F}_{\leqslant},\mathcal{F}_{\geqslant}$ is a
subclass of $\mathcal{T}$.

Finally, we show that there is a fixed parameter tractable algorithm which
approximates twin-width of tournaments up to some function.

######  Theorem 1.3.

There is a function $f:\mathbb{N}\to\mathbb{N}$ and a fixed parameter
tractable algorithm which, given as input a tournament $T$, produces

  1. (1)

either a witness that the twin-width $\operatorname{tww}(T)$ is at most
$f(k)$,

  2. (2)

or a witness that $\operatorname{tww}(T)\geqslant k$.

This algorithm is crucial to obtain the FPT FO model checking algorithm in
classes with bounded twin-width.

The former three theorems generalise to oriented graphs with independence
number bounded by some fixed constant. Furthermore, the tournaments (or
oriented graphs with bounded independence) can be augmented by any fixed
number of arbitrary binary relations: the theorems still hold for the
resulting class of binary relational structures. In particular, this work
generalises the analogous results of [9] on ordered graphs and ordered binary
structures: we replace linear orders with tournaments. In these
generalisations, however, the classes of obstructions for Theorem 1.2 are more
numerous, and we do not give precise descriptions.

###  1.3. Overview of the proof

A fundamental idea regarding twin-width is that upper bounds on twin-width can
be witnessed by orders on vertices which exclude grid-like structures in the
adjacency matrix. This idea appears in the founding works of Guillemot and
Marx [21] and Bonnet et al. [10], and the relation between twin-width and
orders has been deeply explored in [9]. However it is difficult to provide
witnesses for _lower bounds_ on twin-width using this approach: one needs to
somehow prove that _all_ orders contain grids. To this purpose, in any
tournament $T$, we want to construct an order $<$ which, if $T$ has small
twin-width, is a witness of this fact. An equivalent and more precise
requirement is that if $T$ has twin-width $k$, then the bi-relation $(T,<)$
should have twin-width at most $f(k)$ for some function $f$.

A tentative approach to obtain such an order is to describe it in FO
logic—that is, to give a FO transduction which produces a total ordering on
any given tournament. Indeed, FO transductions preserve twin-width up to some
function [10, Theorem 39]. Thus, if there is a universal transduction $\Phi$
which on any tournament $T$ computes some order $<$, we immediately obtain
$\operatorname{tww}(T,<)\leqslant f(\operatorname{tww}(T))$ as desired. With
such a transduction, and some additional requirements such as $<$ being
efficiently computable, it would be straightforward to obtain our results from
the known case of ordered graphs [9]. Unfortunately, this approach fails: to
transduce a total order on an iterated lexicographic product of the 3-cycle
with itself, one needs a first-order formula with size increasing in the
number of iterations [5]. This class of counter-examples also has twin-width
1, meaning that it is not even possible to transduce an order on the class of
tournaments of twin-width $k$ for a fixed $k$.

Instead, our approach is the following: we design a candidate total order $<$
on $T$, computable in polynomial time. If the bi-relation $(T,<)$ has small
twin-width, we are done. On the other hand, if $(T,<)$ has large twin-width,
then its adjacency matrix w.r.t. $<$ must contain a large high-rank grid by
[9]. We then extract a subtournament $T^{\prime}\subset T$ in which the
adjacency matrix w.r.t. $<$ still has a substantial (but logarithmically
smaller) high-rank grid, and on which $<$ is roughly described by a FO
transduction. This is enough to witness that $T$ has large twin-width. Using
Ramsey arguments, we are also able to extract from $T^{\prime}$ some
obstruction from one of the classes
$\mathcal{F}_{=},\mathcal{F}_{\leqslant},\mathcal{F}_{\geqslant}$.

The construction of the order is simple: we consider a binary search tree
(BST) on the vertex set, i.e. a tree in which the left, resp. right, branch of
a node $x$ consists only of in-, resp. out-neighbours of $x$. The order $<$ is
the left-to-right order on nodes of the tree. The extraction of smaller high-
rank grids corresponds to the choice of a branch $B$, and the restriction of
$<$ to the relevant subtournament is a lexicographic ordering according to
$B$.

To summarize, the crucial property of BST orders is the following.

######  Lemma 1.4.

There is a function $f$ such that for any tournament $T$ and any BST order
$<$,

$\operatorname{tww}(T,<)\leqslant f(\operatorname{tww}(T))$

Lemma 1.4 implies Theorem 1.3: to approximate the twin-width of $T$, it
suffices to compute any BST order, which takes polynomial time, and then apply
the approximation algorithm for ordered structures [9, Theorem 2], which is
fixed parameter tractable. This last algorithm produces either a contraction
sequence (which is valid for $(T,<)$ and a fortiori for $T$), or a witness
that $(T,<)$ has large twin-width, which in turn implies that $T$ has large
twin-width by Lemma 1.4.

Our main technical result is about extracting the three classes of
obstructions to twin-width
$\mathcal{F}_{=},\mathcal{F}_{\leqslant},\mathcal{F}_{\geqslant}$, which
consist of encodings of arbitrary permutations into tournaments, see section 3
for the definition.

######  Theorem 1.5.

Let $\mathcal{T}$ be a hereditary class of tournaments with the property that
there are tournaments $T\in\mathcal{T}$ and BST orders $<$ such that
$\operatorname{tww}(T,<)$ is arbitrarily large. Then $\mathcal{T}$ contains
one of the classes
$\mathcal{F}_{=},\mathcal{F}_{\leqslant},\mathcal{F}_{\geqslant}$ as a
subclass.

We also prove that the classes
$\mathcal{F}_{=},\mathcal{F}_{\leqslant},\mathcal{F}_{\geqslant}$ are complex
in all the senses considered by Theorem 1.1, that is theoremobstrhard For each
$R\in\\{=,\leqslant,\geqslant\\}$, the class $\mathcal{F}_{R}$

  1. (1)

has unbounded twin-width;

  2. (2)

contains at least $(\left\lfloor\frac{n}{2}\right\rfloor-1)!$ tournaments on
$n$ vertices counted up to isomorphism;

  3. (3)

contains at least $(\left\lfloor\frac{n}{2}\right\rfloor-1)!\cdot n!$
tournaments on vertex set $\\{1,\dots,n\\}$ counted up to equality;

  4. (4)

efficiently interprets the class of all graphs;

  5. (5)

and has $\textrm{AW}[*]$-hard FO model checking problem.

Theorems 1.5 and 1.5 together imply Theorem 1.2. They also imply Lemma 1.4
when applied to the class of tournaments with twin-width at most $k$: this
class cannot contain any of
$\mathcal{F}_{=},\mathcal{F}_{\leqslant},\mathcal{F}_{\geqslant}$, hence its
tournaments must still have bounded twin-width when paired with BST orders.
Finally, Theorems 1.2 and 1.5 directly imply that if $\mathcal{T}$ is a
hereditary class with unbounded twin-width, then $\mathcal{T}$ satisfies none
of the conditions of Theorem 1.1. The remaining implications of Theorem
1.1—that is, when $\mathcal{T}$ has bounded twin-width, all other conditions
hold—follow from known results on twin-width. By [10, Theorem 1], FO model
checking has an FPT algorithm when a witness of bounded twin-width is given.
Combined with Theorem 1.3, we obtain an FPT algorithm for classes of
tournaments with bounded twin-width. By [10, Theorem 39], a class of
structures with bounded twin-width cannot transduce all graphs. Finally, by
[11, Corollary 7.3], a class of structures with bounded twin-width contains at
most $c^{n}$ structures on $n$ vertices up to isomorphism, for some constant
$c$ depending on the class.

###  1.4. Context and related parameters

An important question is how twin-width compares to other classical complexity
measures for tournaments. Bounded twin-width implies bounded Vapnik-
Chervonenkis dimension, because unbounded VC-dimension implies all possible
bipartite tournaments appearing as subgraphs—which is against single-
exponential growth, and thus twin-width is unbounded. The notion of _cutwidth_
was introduced by Chudnovsky, Fradkin and Seymour [14] to study tournament
immersions. The vertex ordering used to certify that cutwidth is bounded can
be shown to exclude grids, meaning that it is a witness of bounded twin-width.
Another parameter, closely related to subdivisions in tournaments, is
_pathwidth_ , studied by Fradkin and Seymour [17]. Bounded pathwidth of
tournaments implies bounded cliquewidth, which in turn also implies bounded
twin-width, see [10]. Thus, we have the following chain of inclusions of
complexity parameters (if a parameter is bounded, all the ones listed after
are also bounded): cutwidth, pathwidth, cliquewidth, twin-width, and VC-
dimension. For more on the subject, we invite to read Fomin and Pilipczuk [16]
or Pilipczuk’s thesis [25].

Our results are a direct generalisation of those of [9], from ordered graphs
to tournaments. This generalisation is non-trivial: as explained in section
1.3, one cannot FO transduce orders from arbitrary tournaments—which would be
the obvious way to reduce the problem from tournaments to ordered graphs. On
the other hand, there is a natural way to form a tournament $T$ from an
ordered graph $(G,<)$, namely $x\to y$ is an arc of $T$ if and only if $x<y$
and $xy$ is an edge of $G$, or $y<x$ and $xy$ is not an edge of $G$. This
gives a way to create tournaments with bounded twin-width: starting with any
graph $G$ with bounded twin-width, consider a total order $<$ on its vertices
which is a witness of its twin-width, and interpret $T$ from $(G,<)$ as
before. This paper can be seen as the reverse operation, that is a way of
producing an order $<$ from a tournament $T$.

Regarding the binary search tree method for ordering tournaments, it
corresponds to the KwikSort algorithm of Ailon, Charikar and Newman for
approximating the minimum feedback arc set [1]. A difference is that their
result requires the BST to be randomly chosen, whereas arbitrary BST provide
approximations of twin-width.

The generalization to oriented graphs with bounded independence number
contains in particular partially ordered sets with bounded width (i.e.
antichains of bounded size). These classes in fact always have bounded twin-
width, see Balabán and Hlinený [3], and before that were already known to be
tractable with respect to FO model checking, see Gajarský et al. [18].

###  1.5. Organisation of the paper

Section 2 summarises definitions and notations used in this paper. In section
3 we define the classes
$\mathcal{F}_{=},\mathcal{F}_{\leqslant},\mathcal{F}_{\geqslant}$ of
obstructions to twin-width in tournaments, and prove Theorem 1.5. Section 4
defines binary search trees, the associated orders, and some related notions.
We then prove a crucial lemma which, from a partition into intervals of a BST
order, extracts some FO definable substructure. Section 5 proves Theorem 1.5
using the former lemma, combined with results of [9] and Ramsey arguments.
Finally, section 6 explains how our results generalise to oriented graphs with
bounded independence number, and to binary relational structures.

##  2\. Preliminaries

This section summarizes the notions and notations used in this work. For
$n\in\mathbb{N}$, we denote by $[n]$ the interval of integers
$\\{1,\dots,n\\}$. All the graphs, matrices, and relational structures
considered in this work are finite.

###  2.1. Graphs, Oriented graphs, Tournaments

A _directed_ graph $D$ consists of a vertex set $V(G)$, and a set $A(G)$ of
_arcs_ which are _ordered_ pairs of vertices. An arc $(u,v)$ is simply denoted
by $uv$, or sometimes $u\to v$ to insist on the orientation. In this work, we
do not consider loops, i.e. arcs of the form $v\to v$. The _underlying graph_
of $D$ is the undirected graph with the same vertices, and an edge $uv$
whenever either $uv$ or $vu$ is an arc of $D$. A _digon_ in a directed graph
is a pair of vertices $u,v$ with both edges $u\to v$ and $v\to u$. An
_oriented_ graph is a directed graph without digons.

A _tournament_ is an oriented graph whose underlying graph is complete, or
equivalently it is a choice of orientation $u\to v$ or $v\to u$ (but not both)
for every pair of vertices. A tournament is _transitive_ if it contains no
directed cycle. A transitive tournament represents some order $<$ on vertices:
there is an edge $u\to v$ if and only if $u<v$. In a directed graph $D$, a
subset $X\subset V(D)$ which induces a transitive tournament is also called a
_chain_.

A (directed) graph $H$ is an _induced subgraph_ of $G$ if $V(H)\subset V(G)$,
and the edges (or arcs) of $H$ are exactly the edges of $G$ which are between
vertices of $V(H)$. If $X=V(H)$, we also say that $H$ is the subgraph of $G$
induced by $X$, denoted $H=G[X]$. A _class_ of graphs is a family of graphs
closed under isomorphism. A class is _hereditary_ if it is also closed under
taking induced subgraphs.

A subset $S$ of a (directed) graph is called _independent_ or _stable_ if no
edge (arc) joins two vertices of $S$. The independence number $\alpha(G)$ is
the maximum size of an independent set in $G$. If $x$ is a vertex of a
directed graph $D$, then $N^{+}(x)=\textstyle\left\\{y\ |\ x\to y\right\\}$
denotes its _out-neighbourhood_ , and $N^{-}(x)=\textstyle\left\\{y\ |\ y\to
x\right\\}$ its _in-neighbourhood_. The _complete neighbourhood_ is
$N(x)=N^{+}(x)\cup N^{-}(x)$.

###  2.2. Relational structures

Relational structures are a natural generalisation of graphs. A relational
_signature_ is a finite set $\Sigma$ of _relation symbols_ $R$, each with an
associated arity $r\in\mathbb{N}$. A relational structure $S$ over $\Sigma$,
or simply $\Sigma$-structure, consists of a domain $A$, and for each relation
symbol $R\in\Sigma$ of arity $r$, an interpretation of $R$ as $R^{S}\subseteq
A^{r}$. One may think of $A$ as a set of vertices, and each $R^{S}$ as a set
of hyperedges. The notions of induced substructure, hereditary classes, etc.
generalise to relational structures in the obvious way.

We will only consider _binary_ relational structures, i.e. over signatures
where all symbols have arity 2. Directed graphs are binary structures with a
single relation for arcs.

An _ordered structure_ $S$ is a structure over a relation $\Sigma$ with a
special symbol, typically denoted ‘$<$’, whose interpretation $<^{S}$ is a
strict total order on the domain of $S$.

###  2.3. Matrices

We consider matrices as maps $M:R\times C\to\Gamma$, where $R,C$ are _ordered
sets_ of rows and columns of the matrix, and $\Gamma$ and its alphabet. The
order of rows and columns is very important in the context of twin-width.
Usually, the alphabet will simply be $\\{0,1\\}$. The value $M(x,y)$ is called
the _entry_ at position $(x,y)$, and an $a$-entry means an entry whose value
is $a$. A submatrix of $M$ is the restriction of $M$ to some subsets of rows
and columns. The notion is comparable to that of induced substructure,
thinking of rows and columns as vertices, and of the content of the matrix as
a relation. Accordingly, a class of matrices is called _hereditary_ if it is
closed under submatrices.

Given a (directed) graph $G$ and a total order $<$ on $V(G)$, the adjacency
matrix $A_{(G,<)}$ is a 0,1-matrix with rows and columns $V(G)$, and with a
‘1’ at position $(u,v)$ if and only if $uv$ is an edge or arc of $G$. A common
alternative definition for oriented graphs, which we do not use, is to place
‘$-1$’ at position $(v,u)$ when $uv$ is an arc, so as to keep the matrix
antisymmetric. Adjacency matrices generalise easily to binary relational
structures over any signature $\Sigma$, the alphabet being
$\\{0,1\\}^{\Sigma}$ in this case.

A _division_ $\mathcal{D}$ of a matrix consist of partitions
$\mathcal{R},\mathcal{C}$ of its rows and its columns respectively into
_intervals_. It is a $k$-division if the partitions have $k$ parts each. A
_cell_ of the division is the submatrix induced by $X\times Y$ for some
$X\in\mathcal{R},Y\in\mathcal{C}$. A $k$-_grid_ in a 0,1-matrix is a division
in which every cell contains a ‘1’-entry.

###  2.4. Orders, Quasi-orders

A _quasi-order_ $\preceq$ is a reflexive and transitive binary relation. Any
quasi-order induces an equivalence relation $x\sim y$ defined as $x\preceq
y\land y\preceq x$, which is trivial if and only if $\preceq$ is an order. One
can also describe a quasi-order by giving this equivalence relation, and the
order on the equivalence classes. The strict component of the quasi-order is
defined by $x\prec y$ if and only if $x\preceq y$ and $y\not\preceq x$. The
quasi-order is _total_ if for all $x,y$, either $x\preceq y$ or $y\preceq x$.

An _interval_ of a quasi-order $\preceq$ is a set of the form
$\textstyle\left\\{z\ |\ x\preceq z\preceq y\right\\}$ for some $x,y$, called
_endpoints_ of the interval. Remark that an interval is always a union of
equivalence classes of $\sim$. Two subsets $X,Y$ of the domain of $\preceq$
are _overlapping_ if there exist $x_{1},x_{2}\in X$ and $y_{1},y_{2}\in Y$
such that $x_{1}\preceq y_{1}$ and $x_{2}\succeq y_{2}$. Equivalently, $X,Y$
are non-overlapping if and only if there are disjoint intervals
$I_{X}$,$I_{Y}$ such that $X\subseteq I_{X}$ and $Y\subseteq I_{Y}$.

###  2.5. Permutations

We denote by $\mathfrak{S}_{n}$ the group of permutations on $n$ elements. The
_permutation matrix_ $M_{\sigma}$ of $\sigma\in\mathfrak{S}_{n}$ is the sparse
$n\times n$ matrix with a ‘1’ at position $(i,j)$ if and only if
$j=\sigma(i)$. A permutation $\tau$ is a _pattern_ of $\sigma$ if $M_{\tau}$
is a submatrix of $M_{\sigma}$.

We say that $\sigma$ contains a $k$-grid if $M_{\sigma}$ contains a $k$-grid.
When this is the case, any permutation in $\mathfrak{S}_{k}$ is a pattern of
$\sigma$. For example, the permutation $\sigma$ on $k^{2}$ elements defined by
$\sigma(ki+j+1)=kj+i+1$ for any $0\leqslant i,j<k$ contains a $k$-grid. Grids
in permutations are deeply related to pattern-closed classes of permutations,
which are precursors of the work on twin-width, see Marcus and Tardos [23] and
Guillemot and Marx [21].

A permutation can be represented as a _bi-order_ , i.e. the superposition of
two total orders. Precisely, for $\sigma\in\mathfrak{S}_{n}$, the structure
$\mathcal{O}_{\sigma}$ has domain $[n]$, and has for relations the natural
order $<$, and the permuted order $<_{\sigma}$ defined as $i<_{\sigma}j$ if
and only if $\sigma(i)<\sigma(j)$. Any bi-order is isomorphic to some
$\mathcal{O}_{\sigma}$. Remark that $\tau$ is a pattern of $\sigma$ if and
only if $\mathcal{O}_{\tau}$ is isomorphic to an induced substructure of
$\mathcal{O}_{\sigma}$. We write $\mathcal{O}_{\mathfrak{S}}$ for the class of
all finite bi-orders.

For any numbers $x,y$ let the _order type_ $ot(x,y)$ be 1 if $x<y$, $-1$ if
$x>y$, and 0 if $x=y$. We also write $ot_{\sigma}(x,y)$ for
$ot(\sigma(x),\sigma(y))$, the order type with regards to the permuted order
$<_{\sigma}$. In a bi-order $\mathcal{O}_{\sigma}=([n],<,<_{\sigma})$,
consider a coloring of pairs $\lambda:[n]^{2}\to\Gamma$ for some finite
alphabet $\Gamma$. We say that this coloring _depends only on the orders
$<,<_{\sigma}$_ if there is a $\eta:\\{-1,0,1\\}^{2}\to\Gamma$ such that
$\lambda$ factors as

$\lambda(x,y)=\eta(ot(x,y),ot_{\sigma}(x,y))$

For example, interpreting the edges of a graph on $[n]$ as a coloring, the
permutation graph with an edge $xy$ if only if $(x<y\land x>_{\sigma}y)$ or
$(x>y\land x<_{\sigma}y)$ is one which only depends on $<$ and $<_{\sigma}$.

The following result of Ramsey theory, stated as such in [9, Lemma 17], will
be used extensively to extract the minimal classes of obstructions in
tournaments with large twin-width. It is a corollary of the _product Ramsey
theorem_ , see [4, Proposition 3.3] or [20, page 97].

######  Lemma 2.1.

For any permutation $\sigma\in\mathfrak{S}_{n}$ and any finite alphabet
$\Gamma$, there is a permutation $\tau$ satisfying the following. Let
$\mathcal{O}_{\tau}=([N],<,<_{\tau})$. For any coloring of pairs
$\lambda:[N]^{2}\to\Gamma$, there exists $X\subset N$ of size $n$ such that
the substructure $\mathcal{O}_{\tau}[X]$ is isomorphic to
$\mathcal{O}_{\sigma}$, and the coloring $\lambda$ restricted to $X$ only
depends on the orders $<,<_{\tau}$.

If the coloring $\lambda$ represents the edges of a tournament on $[n]$, i.e.
$\lambda(x,y)=1$ if and only if $x\to y$ is an edge, then the ‘depends only on
$<,<_{\sigma}$’ conditions becomes particularly useful.

######  Lemma 2.2.

Let $T$ be a tournament and $<_{1},<_{2}$ two orders on $V(T)$ such that the
direction of edges of $T$ only depends on $<_{1},<_{2}$. Then $T$ is
transitive, and the direction of edges coincides with one of $<_{1}$, $<_{2}$,
the reverse of $<_{1}$, or the reverse of $<_{2}$.

###### Proof.

Let $\eta:\\{-1,0,1\\}^{2}\to\\{0,1\\}$ be such that $\lambda$ factors as
$\lambda(x,y)=\eta(ot(x,y),ot_{\sigma}(x,y))$. Since $T$ is a tournament, it
is then simple to verify that $\eta(-1,-1)=1-\eta(1,1)$ and
$\eta(-1,1)=1-\eta(1,-1)$. It follows that the value of $\eta$ only actually
depends on one of the two coordinates. It is then simple to verify that $T$ is
transitive, with either the same order or the reverse of the order
corresponding to this coordinate. ∎

###  2.6. Twin-width

We recall the definition of twin-width for the sake of completeness, however
we will not use it directly, relying on higher level results instead.

In a binary relational structure $S$, two disjoint subsets $X,Y$ of the domain
are _homogeneous_ if for all relations $R$ of $S$, if there are $x\in X,y\in
Y$ with $xRy$, then for all $x^{\prime}\in X,y^{\prime}\in Y$,
$x^{\prime}Ry^{\prime}$, and symmetrically. Thus, the relations between $X$
and $Y$ do not distinguish any vertex. For example, in a graph, $X,Y$ are
homogeneous if and only if the bipartite graph between $X$ and $Y$ is either
empty or complete; and in a tournament, $X$ and $Y$ are homogeneous if and
only if all edges are oriented from $X$ to $Y$, or all from $Y$ to $X$.

A _contraction sequence_ for a structure $S$ is a sequence
$\mathcal{P}_{n},\dots,\mathcal{P}_{1}$ of partitions of the domain of $S$,
where $\mathcal{P}_{n}$ is the partition into singletons, $\mathcal{P}_{1}$ is
the partition in a single part, and $\mathcal{P}_{i}$ is obtained by merging
two parts of $\mathcal{P}_{i}$. For a given part $X\in\mathcal{P}_{i}$, the
_error degree_ of $X$ in $(S,\mathcal{P}_{i})$ is the number of parts
$Y\in\mathcal{P}_{i}\setminus\\{X\\}$ which are not homogeneous to $X$. The
_width_ of the contraction sequence is the maximum error degree of $X$ in
$(S,\mathcal{P}_{i})$ over all choices of $i\in[n]$ and $X\in\mathcal{P}_{i}$.
Finally, the _twin-width_ of $S$, denoted $\operatorname{tww}(S)$, is the
minimum width of a contraction sequence for $S$.

Twin-width is characterised by grid-like structures in adjacency matrices.
Recall that a division of a matrix is a partition of rows and columns into
intervals. We say that a matrix is _$k$ -diverse_ if it contains at least $k$
different rows and $k$ different columns—which is equivalent to having rank at
least $k^{\prime}$ up to single-exponential bounds. Then, a _rank- $k$
division_ is a $k$-division in which every cell is $k$-diverse. Bonnet et al.
proved

######  Theorem 2.3 ([9, Theorem 2]).

There are functions $f,g$ such that for any graph (or binary structure) $G$
and any order $<$ on $V(G)$,

  * •

if $\operatorname{tww}(G,<)\geqslant f(k)$ then the matrix $A_{(G,<)}$ has a
rank-$k$ division, and

  * •

if the matrix $A_{(G,<)}$ has a rank-$g(k)$ division, then
$\operatorname{tww}(G,<)\geqslant k$.

Furthermore there is an FPT algorithm which given $G$, $<$, and $k$, finds
either a rank-$k$ division in $A_{(G,<)}$ or a contraction sequence of width
$f(k)$ for $(G,<)$.

###  2.7. First-order logic

We assume general familiarity with first-order logic on graphs and relational
structures. Recall from the introduction that we are primarily interesting in
the First-Order Model Checking algorithmic problem, which asks given as input
a structure $S$ and a first-order formula $\phi$, if $\phi$ is satisfied by
$S$, which is denoted by $S\models\phi$. We consider the complexity of this
problem parametrized by the size $|{\phi}|$. In general, this problem is
$\textrm{AW}[*]$-complete [15, Theorem 1]. In fact, the proof shows more
precisely that

######  Theorem 2.4 ([15, Proposition 2]).

First-Order Model Checking on the class of all graphs is
$\textrm{AW}[*]$-complete.

On classes of structures with bounded twin-width, FO model checking is FPT as
long as a witness of twin-width is given.

######  Theorem 2.5 ([10, Theorem 1]).

There is an algorithm which, given a binary structure $S$ on $n$ vertices, a
contraction sequence of width $k$ for $S$, and a FO formula $\phi$, decides if
$S\models\phi$ in time $f(k,\phi)\cdot n$.

_Interpretations_ and _transductions_ are ways to describe transformations of
structures using logical formulæ. For two relational signatures
$\Sigma,\Delta$, a _FO interpretation_ $\Phi$ from $\Sigma$ to $\Delta$
consists of, for each relation $R\in\Delta$ of arity $r$, a FO formula
$\phi_{R}(x_{1},\dots,x_{r})$ over the language $\Sigma$, and one last formula
$\phi_{dom}(x)$ again over $\Sigma$. Given a $\Sigma$-structure $S$, the
result $\Phi(S)$ of the interpretation is the $\Delta$-structure obtained by

  * •

choosing the same domain as $S$,

  * •

interpreting each relation $R\in\Delta$ as the set of tuples
$(v_{1},\dots,v_{r})$ such that $S\models\phi_{R}(v_{1},\dots,v_{r})$,

  * •

and finally taking the substructure induced by $\textstyle\left\\{v\ |\
S\models\phi_{dom}(v)\right\\}$.

For instance, the square of a graph $G$ is defined as the graph with vertices
$V(G)$, and in which $x,y$ are adjacent if and only if their distance in $G$
is at most 2. This is a first-order interpretation in which the edge relation
is interpreted by the formula

$\phi(x,y)=E(x,y)\lor\left(\exists z.\ E(x,z)\land E(z,y)\right)$

where $E(x,x)$ denotes adjacency. The domain formula is trivial since we do
not wish to delete vertices in this interpretation. It is well-known that the
composition of two FO interpretations can itself be written as a FO
interpretation.

_Transductions_ generalise interpretation with a non-deterministic coloring
step. Consider relational signatures $\Sigma$ and $\Sigma^{+}$, where
$\Sigma^{+}$ consists of $\Sigma$ augmented by $r$ new _unary_ relations
$C_{1},\dots,C_{r}$. If $S$ is a structure over the signature $\Sigma$, we
denote by $S^{+}$ the set of structures over $\Sigma^{+}$ whose domain and
interpretation of $\Sigma$ coincide with that of $S$. Thus, a $T\in S^{+}$ is
uniquely described by the interpretation of $C_{1},\dots,C_{r}$ within $V(S)$.
A FO transduction $\Phi:\Sigma\to\Delta$ is described by the choice of
$\Sigma^{+}$ augmenting $\Sigma$ with unary relations, together with a FO
interpretation $\Phi_{I}$ from $\Sigma^{+}$ from $\Delta$. The result of the
transduction $\Phi$ on a $\Sigma$-structure $S$ is then the set of structures

$\Phi(S)=\textstyle\left\\{\Phi_{I}(T)\ |\ T\in S^{+}\right\\}$

Additional operations such as duplication of vertices are often allowed in
transductions, but these will not be needed in this work. Like
interpretations, transductions can be composed.

Given classes $\mathcal{C},\mathcal{D}$ of relational structures, we say that
$\mathcal{C}$ _interprets_ (resp.  _transduces_) $\mathcal{D}$ if there is a
FO interpretation (resp. transduction) $\Phi$ such that
$\Phi(\mathcal{C})\supseteq\mathcal{D}$. The interpretation $\Phi$ is allowed
to also output structures which are not in $\mathcal{D}$. We furthermore say
that $\mathcal{C}$ _efficiently interprets_ $\mathcal{D}$ if there is also an
algorithm which given as input $D\in\mathcal{D}$, finds in polynomial time
some $C\in\mathcal{C}$ such that $\Phi(C)=D$. It is straightforward to show
that this additional condition gives a FPT reduction for model checking.

######  Lemma 2.6.

If $\mathcal{C}$ efficiently interprets $\mathcal{D}$, then there is a FPT
reduction from FO Model Checking on $\mathcal{D}$ to FO Model Checking on
$\mathcal{C}$.

Recall that $\mathcal{O}_{\mathfrak{S}}$ denotes the class of bi-orders, which
are encodings of permutations. The following is a folklore result, see e.g.
[9, Lemma 10] for a very similar claim.

######  Lemma 2.7.

The class $\mathcal{O}_{\mathfrak{S}}$ of bi-orders efficiently interprets the
class of all graphs.

Thus, using Lemmas 2.6 and 2.4, FO Model Checking on
$\mathcal{O}_{\mathfrak{S}}$ is $\textrm{AW}[*]$-complete.

FO transductions also preserve twin-width, up to some function.

######  Theorem 2.8 ([10, Theorem 39]).

If $\mathcal{S}$ is a class of binary structures with bounded twin-width and
$\Phi$ is a FO transduction defined on $\mathcal{S}$, then $\Phi(\mathcal{S})$
also has bounded twin-width.

A class of structures $\mathcal{S}$ is said to be _monadically NIP_ if
$\mathcal{S}$ does not transduce the class of all graphs. Because the class of
all graphs does not have bounded twin-width, Theorem 2.8 implies that classes
with bounded twin-width are monadically NIP. The weaker notion of (non-
monadicically) NIP also exists, with a slightly more technical definition.
Braunfeld and Laskowski recently proved that NIP and monadically NIP are
equivalent notions for hereditary classes of structures [13], thus the
distinction is irrelevant in this work.

###  2.8. Enumerative combinatorics

A class $\mathcal{S}$ of graphs (or binary relational structures) is _small_
if there exists $c$ such that $\mathcal{S}$ contains at most $c^{n}\cdot n!$
structures on the vertex set $[n]$. For instance, the class of trees is small,
and more generally proper minor closed classes of graphs are small as shown by
Norine et al. [24]. This was further generalised to classes of bounded twin-
width by Bonnet et al.

######  Theorem 2.9 ([7, Theorem 2.4]).

Classes of structures with bounded twin-width are small.

The reverse implication does not hold for graphs: there are small hereditary
classes of graphs with unbounded twin-width [8]. These counterexamples have
bounded maximum degree. One of the main results of [9] is that for classes of
ordered graphs, bounded twin-width is equivalent to being small. We generalise
it to tournaments.

One may also wish to count structures up to isomorphism, rather than counting
labelled structures as in the definition of small classes. A strengthening of
Theorem 2.9 when counting up to isomorphism was proved in [11].

######  Theorem 2.10 ([11, Corollary 7.3]).

For any class $\mathcal{C}$ of structures with bounded twin-width, there is a
constant $c$ such that $\mathcal{C}$ has at most $c^{n}$ structures on $n$
vertices counted up to isomorphism.

##  3\. Forbidden classes of tournaments

This section defines the three minimal classes $\mathcal{F}_{=}$,
$\mathcal{F}_{\leqslant}$, and $\mathcal{F}_{\geqslant}$ of obstructions to
twin-width in tournaments. Each of them corresponds to some encoding of the
class of all permutations. For $R\in\\{=,\leqslant,\geqslant\\}$ and any
permutation $\sigma$, we will define a tournament $\mathcal{F}_{R}(\sigma)$.
The class $\mathcal{F}_{R}$ is the hereditary closure of all
$\mathcal{F}_{R}(\sigma)$.

Let $R\in\\{=,\leqslant,\geqslant\\}$, and let $\sigma\in\mathfrak{S}_{n}$ be
a permutation on $n$ elements. The tournament $\mathcal{F}_{R}(\sigma)$
consists of $2n$ vertices, called $x_{1},\dots,x_{n},y_{1},\dots,y_{n}$. Let
$X=\\{x_{1},\dots,x_{n}\\}$ and $Y=\\{x_{1},\dots,y_{n}\\}$. Each of $X,Y$ is
a chain under the natural order, i.e. there is an edge from $x_{i}$ to
$x_{j}$, resp. from $y_{i}$ to $y_{j}$, if and only if $i<j$. The edges
between $X$ and $Y$ encode $\sigma$ in a way specified by the relation $R$:
there is an edge oriented from $y_{j}$ to $x_{i}$ if and only if
$i\,R\,\sigma^{-1}(j)$. See Figure 1 for an example.

$x_{1}$$y_{1}$$x_{2}$$y_{2}$$x_{3}$$y_{3}$$x_{4}$$y_{4}$$x_{5}$$y_{5}$$\mathcal{F}_{=}(\sigma)$$x_{1}$$y_{1}$$x_{2}$$y_{2}$$x_{3}$$y_{3}$$x_{4}$$y_{4}$$x_{5}$$y_{5}$$\mathcal{F}_{\leqslant}(\sigma)$$x_{1}$$y_{1}$$x_{2}$$y_{2}$$x_{3}$$y_{3}$$x_{4}$$y_{4}$$x_{5}$$y_{5}$$\mathcal{F}_{\geqslant}(\sigma)$
Figure 1. The three classes of obstructions to twin-width in tournaments. For
readability, edges oriented from some $x_{i}$ to some $y_{j}$ have been
omitted. Each class consists of some encoding of the class of all
permutations, represented here with the permutation $\sigma=31452$.

Thus in $\mathcal{F}_{=}(\sigma)$ the edges oriented from $Y$ to $X$ form a
matching which encodes $\sigma$. In $\mathcal{F}_{\leqslant}(\sigma)$ and
$\mathcal{F}_{\geqslant}(\sigma)$, these edges form a half-graph which orders
$X$ and $Y$ by inclusion of neighbourhoods, so that the order on $X$ is the
natural one, and the order on $Y$ encodes $\sigma$. Precisely, in
$\mathcal{F}_{\geqslant}(\sigma)$, for any $i,j\in[n]$, we have

(1) $\displaystyle N^{-}(x_{i})\cap Y\subseteq N^{-}(x_{j})\cap Y$
$\displaystyle\iff i\leqslant j$ (2) $\displaystyle\text{and}\quad
N^{-}(y_{i})\cap X\subseteq N^{-}(y_{j})\cap X$
$\displaystyle\iff\sigma^{-1}(i)\leqslant\sigma^{-1}(j),$

while in $\mathcal{F}_{\leqslant}(\sigma)$, the direction of inclusions is
reversed.

######  Lemma 3.1.

For each $R\in\\{=,\leqslant,\geqslant\\}$, the class $\mathcal{F}_{R}$
efficiently interprets the class $\mathcal{O}_{\mathfrak{S}}$ of permutations
represented as bi-orders. Precisely, there is an interpretation $\Phi_{R}$,
and for any permutation $\sigma\in\mathfrak{S}_{n}$, $n\geqslant 2$, there is
a $\sigma^{\prime}\in\mathfrak{S}_{n+1}$ computable in polynomial time such
that $\mathcal{O}_{\sigma}=\Phi_{R}(\mathcal{F}_{R}(\sigma^{\prime}))$.

###### Proof.

We will first show that $\mathcal{F}_{R}(\sigma)$ transduces
$\mathcal{O}_{\sigma}$, and then how to remove the coloring step of the
transduction by slightly extending $\sigma$.

Let $X=\\{x_{1},\dots,x_{n}\\}$ and $Y=\\{y_{1},\dots,y_{n}\\}$ be as in the
definition of $\mathcal{F}_{R}(\sigma)$. The transduction uses coloring to
guess the set $X$. It then defines two total orders on $Y$, which together
describe $\sigma$. The first ordering is given by the direction of edges
inside $Y$. The second depends on $R$:

  * •

If $R$ is $=$, edges oriented from $Y$ to $X$ are a perfect matching. The
direction of edges in $X$, interpreted through this matching, defines the
second order on $Y$.

  * •

If $R$ is $\geqslant$ or $\leqslant$, the second order is inclusion,
respectively inverse inclusion, of in-neighbourhoods intersected with $X$, see
(2).

With the knowledge of which subset is $X$, each of these orders is clearly
definable with a first-order formula. Finally, the transduction deletes
vertices of $X$, leaving only $Y$ and the two orders which encode $\sigma$.

Let us now show how to deterministically define the partition $X,Y$, at the
cost of extending $\sigma$ with one fixed value. Here, we assume $n\geqslant
2$.

  * •

If $R$ is $=$, define $\sigma^{\prime}\in\mathfrak{S}_{n+1}$ by
$\sigma^{\prime}(n+1)=n+1$ and $\sigma^{\prime}(i)=\sigma(i)$ for any
$i\leqslant n$. Then, in $\mathcal{F}_{=}(\sigma^{\prime})$, the unique vertex
with out-degree 1 is $y_{n+1}$. Its out-neighbour is $x_{n+1}$, which verifies
$X=N^{-}(x_{n+1})\cup\\{x_{n+1}\\}\setminus\\{y_{n+1}\\}$.

  * •

If $R$ is $\leqslant$, define $\sigma^{\prime}(1)=n+1$ and
$\sigma^{\prime}(i+1)=\sigma(i)$. Then $y_{n+1}$ is the unique vertex with
out-degree $1$, and its out-neighbour is $x_{1}$, which satisfies
$X=N^{+}(x_{1})\cup\\{x_{1}\\}$.

  * •

If $R$ is $\geqslant$, we once again define $\sigma^{\prime}(1)=n+1$ and
$\sigma^{\prime}(i+1)=\sigma(i)$. Then $x_{1}$ has in-degree $1$, and its in-
neighbour is $y_{n+1}$. The only other vertex which may have in-degree $1$ is
$y_{1}$, and this happens if and only if $\sigma^{\prime}(2)=1$. When this is
the case, the direction of the edge $x_{1}\to y_{1}$ still allows to
distinguish $x_{1}$ in FO logic. Then, having defined $x_{1}$, we obtain
$y_{n+1}$ as its in-neighbour, which satisfies $X=N^{+}(y_{n+1})$.

In all three cases, $\mathcal{F}_{R}(\sigma^{\prime})$ contains two extra
vertices compared to $\mathcal{F}_{R}(\sigma)$. These extra vertices can be
uniquely identified in first-order logic, and can then be used to define $X$.
Combined with the previous transduction, this gives an interpretation of
$\mathcal{O}_{\sigma}$ in $\mathcal{F}_{R}(\sigma^{\prime})$. ∎

We can now prove that the classes $\mathcal{F}_{R}$ are complex. *

###### Proof.

Item 4 is straightforward by Lemmas 3.1 and 2.7, since efficient
interpretations can be composed. By Lemmas 2.6 and 2.4, this in turn implies
Item 5.

Item 3 implies Item 2 by a simple counting argument: in an isomorphism class,
there are at most $n!$ choices of labelling of vertices with $\\{1,\dots,n\\}$
(less when the graph has automorphism). Furthermore, each of Items 3 and 4
implies Item 1, by Theorem 2.9 and Theorem 2.8 respectively. Thus it only
remains to prove Item 3.

By Lemma 3.1, for all $\sigma\in\mathfrak{S}_{n}$ there is some
$\mathcal{F}_{R}(\sigma^{\prime})$ on $2n+2$ vertices such that
$\Phi_{R}(\mathcal{F}_{R}(\sigma^{\prime}))=\sigma$, where $\Phi_{R}$ is an
interpretation. Since interpretations preserve isomorphism, it follows that
there are at least $n!$ non-isomorphic tournaments on $2n+2$ vertices in
$\mathcal{F}_{R}$. Furthermore, using the same arguments as in Lemma 3.1, it
is easy to show that these $\mathcal{F}_{R}(\sigma^{\prime})$ have no non-
trivial automorphism. Thus, there are exactly $(2n+2)!$ distinct labellings of
$\mathcal{F}_{R}(\sigma^{\prime})$ with $\\{1,\dots,2n+2\\}$. In total, this
gives $(2n+2)!\cdot n!$ distinct graphs on vertices $\\{1,\dots,2n+2\\}$ in
$\mathcal{F}_{R}$, proving Item 3. ∎

Thus the classes
$\mathcal{F}_{=},\mathcal{F}_{\leqslant},\mathcal{F}_{\geqslant}$ are
obstructions to fixed parameter tractability of FO model checking and twin-
width. The rest of the paper shows that they are the only obstructions. One
may also verify that all three are minimal, i.e. none of them is contained in
another.

##  4\. Binary search tree orders

This section presents the good order for twin-width in tournaments. It is
based on _binary search trees_ (BST), which we define in a tournament $T$ as a
rooted ordered binary tree $S$ (meaning that each node has a left and right
child, either of which may be missing), whose nodes are the vertices of $T$,
and such that for any $x\in S$

  * •

the left child of $x$ (if any) and its descendants are in $N_{T}^{-}(x)$, and

  * •

the right child of $x$ (if any) and its descendants are in $N_{T}^{+}(x)$,

see Figure 2.

Figure 2. A binary search tree in a tournament. The direction of omitted edges
is not constrained.

The _order_ associated to $S$, denoted $<_{S}$, is the left-to-right order,
i.e. the one which places a node $x$ after its left child and its descendants,
but before its right child and its descendants. Such an order is called a _BST
order_.

Remark that because $T$ is only a tournament and not an order as in a standard
BST, there is no restriction on the direction of edges between the left and
right subtrees of $x$. On the other hand, if $x$ is an ancestor of $y$, then
there is an edge oriented from $x$ to $y$ if and only if $x<_{S}y$. Thus we
have

######  Remark 4.1.

In a tournament $T$, any branch $B$ of a BST $S$ forms a chain which coincides
with $<_{S}$. That is, for $x,y\in B$, the edge in $T$ is oriented from $x$ to
$y$ if and only if $x<_{S}y$.

We will now define _chain quasi-orders_ , which are FO definable quasi-orders
with which we will approximate BST orders. Let $C$ be a chain in $T$. Its
_chain quasi-order_ $\preceq_{C}^{+}$ is defined as follows. Enumerate the
vertices of $C$ as $c_{1},\dots,c_{k}$ so that edges are oriented from $c_{i}$
to $c_{j}$ when $i<j$. Define $A_{i}=\bigcap_{j\leqslant i}N^{+}(c_{j})$, and
$B_{i}=A_{i-1}\cap N^{-}(c_{i})$. Then each of $B_{1},\dots,B_{k}$ and $A_{k}$
is an equivalence class of $\preceq_{C}^{+}$, and the classes are ordered as

$B_{1}\prec_{C}^{+}c_{1}\prec_{C}^{+}B_{2}\prec_{C}^{+}c_{2}\prec_{C}^{+}\dots
B_{k}\prec_{C}^{+}c_{k}\prec_{C}^{+}A_{k},$

see Figure 3. This can be seen as the left-to-right order of a partial BST
consisting only of a single branch $c_{1},\dots,c_{k}$, with $c_{1}$ as root
and $c_{k}$ as leaf. It is also a coarsening of the lexicographic order: the
latter would refine the order inside each class $B_{i}$ using
$c_{i+1},\dots,c_{k}$.

The dual quasi-order $\preceq_{C}^{-}$ is defined in the same way, but
reversing the direction of all edges. Thus, we now enumerate $C$ so that edges
are from $c_{i}$ to $c_{j}$ when $i>j$, while $A_{i}=\bigcap_{j\leqslant
i}N^{-}(c_{i})$ and $B_{i}=A_{i-1}\cap N^{+}(c_{i})$. The rest of the
definition is the same.

$c_{1}$$B_{1}$$c_{2}$$B_{2}$$c_{3}$$B_{3}$$c_{4}$$B_{4}$$A_{4}$ Figure 3.
Example of construction of the quasi-order $\preceq_{C}^{+}$. The quasi-order
is from left to right, and the triangles are equivalence classes. The
direction of omitted edges (from $B_{i}$ to $B_{j}\cup\\{c_{j}\\}$ for $i<j$)
is not constrained. For $\preceq_{C}^{-}$, the direction of all edges would be
reversed.

Although we will not use it directly, it is worth remarking that chain quasi-
orders can be defined by a first-order transduction. This ensures that they
are well behaved with regards to twin-width. While BST orders lack this first-
order definability property, they can be approximated by chain quasi-orders in
the following sense.

######  Lemma 4.2.

Let $T$ be a tournament and $S$ be a BST with associated order $<_{S}$. There
is a function $f(k)=2^{O(k)}$ independent of $T$ and $S$ satisfying the
following. For any family $\mathcal{P}$ of at least $f(k)$ disjoint intervals
of $<_{S}$, there is a chain $C$ in $T$, an orientation $o\in\\{+,-\\}$ and a
subfamily $\mathcal{P}^{\prime}\subset\mathcal{P}$ such that
$|{\mathcal{P}^{\prime}}|\geqslant k$ and such that the intervals of
$\mathcal{P}^{\prime}$ are non-overlapping for $\preceq_{C}^{o}$.

Furthermore, $C$, $o$, and $\mathcal{P}^{\prime}$ can be computed in linear
time.

###### Proof.

Let $T$ be a tournament, $S$ a BST of $T$ and $<_{S}$ the corresponding order.
Consider a family $\mathcal{P}$ of at least $f(k)$ disjoint intervals of
$<_{S}$, where $f(k)=2^{O(k)}$ will be determined later.

We choose a branch $B=b_{0},\dots,b_{p}$ of $S$ by the following process.
First $b_{0}$ is the root of $S$. For each (yet to be determined) $b_{i}$, let
$S_{i}$ be the subtree of $S$ rooted in $b_{i}$, and define the weight $w_{i}$
to be the number of classes of $\mathcal{P}$ intersected by $S_{i}$. Then
$b_{i+1}$ is chosen to be the child of $b_{i}$ which maximizes $w_{i+1}$. This
choice ensures that

(3) $2w_{i+1}+1\geqslant w_{i}.$

For each $i<p$, let $d_{i}$ be the child of $b_{i}$ other than $b_{i+1}$
(sometimes $d_{i}$ does not exist), and let $D_{i}$ be the subtree of $S$
rooted at $d_{i}$ ($D_{i}$ is empty if $d_{i}$ does not exist). Furthermore,
let $L,R$ be the sets of vertices which are before, resp. after the leaf
$b_{p}$ in the order $<_{S}$. For any $0\leqslant i\leqslant j\leqslant p$,
let

$L_{i,j}\stackrel{{\scriptstyle\text{def}}}{{=}}\bigcup_{\begin{subarray}{c}i\leqslant\ell<j\\\
b_{\ell}\in L\end{subarray}}\\{b_{\ell}\\}\cup D_{\ell},\qquad\text{and}\qquad
R_{i,j}\stackrel{{\scriptstyle\text{def}}}{{=}}\bigcup_{\begin{subarray}{c}i\leqslant\ell<j\\\
b_{\ell}\in R\end{subarray}}\\{b_{\ell}\\}\cup D_{\ell}.$

Roughly speaking, $L_{i,j}$, resp. $R_{i,j}$ consists of subtrees branching
out of $B$ on the left, resp. right, between $b_{i}$ and $b_{j}$.

######  Claim 4.3.

For any $i,j$, the subtree $S_{i}$ is partitioned into
$L_{i,j}<_{S}S_{j}<_{S}R_{i,j}$.

###### Proof.

Clearly $L_{i,j},S_{j},R_{i,j}$ partition $S_{i}$. Furthermore, if $\ell<j$
and $b_{\ell}\in L$, then $b_{\ell}<_{S}S_{j}$, and in turn
$D_{\ell}<_{S}b_{\ell}$. This proves $L_{i,j}<_{S}S_{j}$, and symmetrically
$S_{j}<_{S}R_{i,j}$. $\blacksquare$

######  Claim 4.4.

For $0\leqslant i<j\leqslant p$, if $w_{i}\geqslant w_{j}+3$, then there is a
part $P\in\mathcal{P}$ such that $P\subset L_{i,j}$ or $P\subset R_{i,j}$.

###### Proof.

There are at least three parts of $\mathcal{P}$ which intersect $S_{i}$ but
not $S_{j}$. Since these three parts and $S_{i}$ are all intervals of $<_{S}$,
one of these parts, say $P$, is contained in $S_{i}$. Thus $P$ is a subset of
$S_{i}$ but does not intersect $S_{j}$, which using 4.3 implies that $P\subset
L_{i,j}$ or $P\subset R_{i,j}$. $\blacksquare$

Construct a sequence $i_{0}<\dots<i_{2k}$ of indices in $\\{0,\dots,p\\}$
inductively by taking $i_{0}=0$, and choosing $i_{\ell+1}$ minimal such that
$w_{i_{\ell+1}}\leqslant w_{i_{\ell}}-3$. Using (3) and the minimality of
$i_{\ell+1}$, we obtain for all $\ell$ that

(4) $\displaystyle 2w_{i_{\ell+1}}+1$ $\displaystyle\geqslant
w_{i_{\ell+1}-1}>w_{i_{l}}-3,$ (5) $\displaystyle\text{hence}\quad
2w_{i_{\ell+1}}+3$ $\displaystyle\geqslant w_{i_{l}}.$

We can now define $f$ by $f(0)=1$ and $f(k+1)=4f(k)+9$. By assumption,
$w_{0}=|{\mathcal{P}}|\geqslant f(k)$, and it follows from (5) that the
construction of $i_{\ell}$ can be carried out up to $i_{2k}$.

Define $L^{\prime}_{\ell}=L_{i_{\ell-1},i_{\ell}}$, and similarly
$R^{\prime}_{\ell}=R_{i_{\ell-1},i_{\ell}}$, see Figure 4. By 4.4, for any
$\ell\in[2k]$, either $L^{\prime}_{\ell}$ or $R^{\prime}_{\ell}$ contains a
part of $\mathcal{P}$. Thus, either there are at least $k$ distinct
$L^{\prime}_{\ell}$ containing a part of $\mathcal{P}$, or there are at least
$k$ distinct $R^{\prime}_{\ell}$ containing a part of $\mathcal{P}$. Without
loss of generality, assume that we are in the former case. We will now forget
about vertices which are not in $L$.

$b_{0}$$b_{1}$$b_{2}$$b_{3}$$b_{4}$$b_{5}$$b_{6}$$b_{7}$$D_{0}$$D_{1}$$D_{3}$$D_{6}$$D_{5}$$D_{4}$$D_{2}$$b_{i_{0}}$$b_{i_{1}}$$b_{i_{2}}$$b_{i_{3}}$$R^{\prime}_{1}$$R^{\prime}_{2}$$L^{\prime}_{3}$$L^{\prime}_{2}$$\mathcal{P}$$\mathcal{P}^{\prime}$
Figure 4. Sketch of the proof of Lemma 4.2. In the upper half, the BST $T$
with the extracted branch $B$; circled in red, the extracted subsequence
$b_{i_{\ell}}$; in green arrows, the chain $C=B\cap
L=\\{b_{2},b_{4},b_{5},b_{6}\\}$. Below the tree, from top to bottom: the
partition in $L^{\prime}_{\ell}$ and $R^{\prime}_{\ell}$; the initial family
(here partition) $\mathcal{P}$, with the parts contained in some
$L^{\prime}_{\ell}$ or $R^{\prime}_{\ell}$ highlighted; the final family
$\mathcal{P}^{\prime}$, obtained by selecting a part of $\mathcal{P}$ inside
each possible $L^{\prime}_{\ell}$.

Define $C=L\cap B$. By Remark 4.1, this is a chain, whose order coincides with
$<_{S}$. Furthermore, at any node $x$ of $C$, the branch $B$ does descend on
the right side, since $x<_{S}b_{p}$. Thus, the order in $C$ also coincides
with the ancestor-descendent order of $S$. (Remark here that if we were in $R$
instead of $L$, the order of $C$ would be the inverse of the ancestor-
descendant order.) Now, if $C$ is enumerated as $c_{0}<_{S}\dots<_{S}c_{t}$,
and $C_{i}$ is the subtree branching out on the left of $c_{i}$, defined
similarly to $D_{i}$, then the chain quasi-order $\preceq_{C}^{+}$ restricted
to $L$ is exactly

$C_{0}\prec_{C}^{+}c_{0}\prec_{C}^{+}C_{1}\prec_{C}^{+}c_{1}\prec_{C}^{+}\dots\prec_{C}^{+}c_{t}$

where each subtree $C_{i}$ is an equivalence class. (In $R$, we would instead
use $\preceq_{C}^{-}$.) From this description, we obtain that any $L_{i,j}$ is
an interval of $\preceq_{C}^{+}$ restricted to $L$.

For each $L^{\prime}_{\ell}$, select a part of $\mathcal{P}$ included in
$L^{\prime}_{\ell}$ if any, and define $\mathcal{P}^{\prime}$ as the
collection of selected parts. Thus $\mathcal{P}^{\prime}\subset\mathcal{P}$,
and we know from the choice of the family
$\\{L^{\prime}_{\ell}\\}_{\ell\in[2k]}$ that
$|{\mathcal{P}^{\prime}}|\geqslant k$. Furthermore, if $X\neq Y$ are parts of
$\mathcal{P}^{\prime}$, there are $s\neq t$ such that $X\subseteq
L^{\prime}_{s}$ and $Y\subseteq L^{\prime}_{t}$. Since each
$L^{\prime}_{\ell}$ is an interval of $(L,\preceq_{C}^{+})$, this implies that
$X$ and $Y$ are non-overlapping for $\preceq_{C}^{+}$. Thus
$\mathcal{P}^{\prime}$ satisfies all desired properties.

Finally, given the BST $S$ and the family $\mathcal{P}$, it is routine to
compute the weights $w_{i}$ of all nodes in $S$ by a bottom-up procedure; this
only requires to compute the left-most and right-most parts of $\mathcal{P}$
intersecting each subtree. From this, it is simple to choose in linear time
the branch $B$, the indices $i_{\ell}$, the better side $L$ or $R$, and
finally to compute $C$ and $\mathcal{P}^{\prime}$. ∎

##  5\. Extracting forbidden tournaments

In this section, we prove that any class of tournaments with unbounded twin-
width contains one of the classes of obstructions described in section 3, by
combining BST and chain orders from the previous section with the techniques
developed in [9] for ordered graphs. We in fact show a stronger statement:
either all BST orders are witness of bounded twin-width, or the class contains
one of the classes of obstructions.

If $\mathcal{T}$ is a class of tournaments, we denote by $\mathcal{T}^{BST}$
the class of ordered tournaments $(T,<_{S})$ where $T\in\mathcal{T}$ and
$<_{S}$ is the order of some BST $S$ on $T$. With this notation, Theorem 1.5
is restated as

######  Theorem 5.1.

Let $\mathcal{T}$ be a hereditary class of tournaments. If $\mathcal{T}^{BST}$
has unbounded twin-width, then $\mathcal{T}$ contains one of the classes
$\mathcal{F}_{=},\mathcal{F}_{\leqslant},\mathcal{F}_{\geqslant}$.

We fix a class $\mathcal{T}$ such that $\mathcal{T}^{BST}$ has unbounded twin-
width for the remainder of this section. We will show that one can find the
following more and more constrained structures in $\mathcal{T}$:

  1. (1)

high rank grids with regards to BST orders,

  2. (2)

high rank grids between two chain quasi-orders,

  3. (3)

some encoding of arbitrary permutations between two chain orders,

  4. (4)

some encoding of arbitrary permutations between two transitive subtournaments,

  5. (5)

and finally one of the classes
$\mathcal{F}_{=},\mathcal{F}_{\leqslant},\mathcal{F}_{\geqslant}$.

###  5.1. High rank grids

Recall that a rank-$k$ grid in a matrix is a $k$-division in which every cell
is $k$-diverse, i.e. has at least $k$ distinct rows and $k$ distinct columns.

######  Claim 5.2.

For any $k$, there exists $(T,<_{S})\in\mathcal{T}^{BST}$ and intervals
$A_{1}<_{S}\dots<_{S}A_{k}<_{S}B_{1}<_{S}\dots<_{S}B_{k}$ of $V(T)$ such that
for any $i,j\in[k]$, the adjacency matrix of $A_{i}$ versus $B_{j}$ is
$k$-diverse.

###### Proof.

By Theorem 2.3, ordered structures with sufficiently large twin-width have
rank-$k$ divisions in their adjacency matrix, for any given $k$. Applied to
$\mathcal{T}^{BST}$ which has unbounded twin-width, we obtain
$(T,<_{S})\in\mathcal{T}^{BST}$ and a rank-$2k$ division consisting of two
partitions $A_{1}<_{S}\dots<_{S}A_{2k}$ and $B_{1}<_{S}\dots<_{S}B_{2k}$ of
$V(T)$ into intervals such that the adjacency matrix of $A_{i}$ versus $B_{j}$
is $k$-diverse. We only need to ensure that the $A_{i}$s are disjoint from the
$B_{j}$s.

If the last element of $A_{k}$ is smaller than the first of $B_{k+1}$, then
$A_{1}<_{S}\dots<_{S}A_{k}<_{S}B_{k+1}<_{S}\dots<_{S}B_{2k}$ satisfy the
desired property. Otherwise, the last element of $B_{k}$ is smaller than the
first of $A_{k+1}$, and symmetrically
$B_{1}<_{S}\dots<_{S}B_{k}<_{S}A_{k+1}<_{S}\dots<_{S}A_{2k}$ are as desired.
$\blacksquare$

######  Claim 5.3.

For any $k$, there exists $T\in\mathcal{T}$, two chain quasi-orders
$\preceq^{A},\preceq^{B}$ in $T$, and disjoint subsets
$A_{1},\dots,A_{k},B_{1},\dots,B_{k}$ of $V(T)$ such that the $A_{i}$s, resp.
$B_{j}$s, are non-overlapping for $\preceq^{A}$, resp. $\preceq^{B}$, and for
any $i,j\in[k]$, the adjacency matrix of $A_{i}$ versus $B_{j}$ is
$k$-diverse.

###### Proof.

Applying 5.2 with $f(k)$ where $f$ is the function of Lemma 4.2, there exists
$T\in\mathcal{T}$ and intervals
$A_{1}<_{S}\dots<_{S}A_{f(k)}<_{S}B_{1}<_{S}\dots<_{S}B_{f(k)}$ of some BST
order $<_{S}$ such that the adjacency matrix of $A_{i}$ versus $B_{j}$ is
$k$-diverse. Applying Lemma 4.2 to the $A_{i}$s and to the $B_{j}$s separately
yields subfamilies of size at least $k$, both of which are non-overlapping for
some chain quasi-order. $\blacksquare$

At this point, we can already conclude that $\mathcal{T}$ has unbounded twin-
width through the model-theoretic arguments of [9, section 9]. Indeed, since
the subsets $(A_{i})_{i\in[k]}$ of 5.3 are non-overlapping for $\preceq^{A}$,
they can be enlarged into intervals of $\preceq^{A}$ while preserving
disjointness. The chain quasi-order $\preceq^{A}$ can be described in first-
order logic by a transduction which guesses $A$, and each interval $A_{i}$ can
then be described by its starting point and endpoint. Using the terminology of
[9], this makes $(A_{i})_{i\in[k]}$ and similarly $(B_{j})_{j\in[k]}$
_definable disjoint families_. That $A_{i}$ versus $B_{j}$ is $k$-diverse
implies that the _$\Delta$ -type_ of $A_{i}$ over $B_{j}$ has cardinality at
least $k$, when $\Delta$ only contains the formula $\theta(x;y)=E(x,y)$. Since
the above exists for any $k$, the class $\mathcal{T}$ is _unrestrained_ ,
hence it has unbounded twin-width by [9, Theorem 55].

The rest of the proof of Theorem 5.1 is required to obtain the canonical
forbidden tournaments $\mathcal{F}_{=}$, $\mathcal{F}_{\leqslant}$, or
$\mathcal{F}_{\geqslant}$.

###  5.2. Chain order representations

The next step is to extract encodings of permutations from high rank grids
using results of [9]. Unfortunately, we need a slightly stronger statement
than the one found in [9]: this extraction is done by selecting at most one
column or row from each block of columns or rows of the division.

Let us first recall the six classes
$\mathcal{M}_{=},\mathcal{M}_{\neq},\mathcal{M}_{\leqslant_{R}},\mathcal{M}_{\geqslant_{R}},\mathcal{M}_{\leqslant_{C}},\mathcal{M}_{\geqslant_{C}}$
of matrix obstructions to twin-width described in [9].222The classes are
called $\mathcal{F}_{=}$, etc. in [9], we use $\mathcal{M}_{=}$ to avoid
ambiguity with tournaments defined in section 3.  Similarly to the classes of
tournaments described in section 3, each class $\mathcal{M}_{s}$ consists of
the hereditary closure of encodings $\mathcal{M}_{s}(\sigma)$ of arbitrary
permutations $\sigma$. If $\sigma$ is a permutation on $n$ elements, the
$n\times n$ matrix $\mathcal{M}_{s}(\sigma)=(m_{i,j})_{i,j\in[n]}$ is
described by

$\displaystyle\mathcal{M}_{=}(\sigma):$ $\displaystyle m_{i,j}=1$
$\displaystyle\iff j=\sigma(i)$ $\displaystyle\mathcal{M}_{\neq}(\sigma):$
$\displaystyle m_{i,j}=1$ $\displaystyle\iff j\neq\sigma(i)$
$\displaystyle\mathcal{M}_{\leqslant_{R}}(\sigma):$ $\displaystyle m_{i,j}=1$
$\displaystyle\iff j\leqslant\sigma(i)$
$\displaystyle\mathcal{M}_{\geqslant_{R}}(\sigma):$ $\displaystyle m_{i,j}=1$
$\displaystyle\iff j\geqslant\sigma(i)$
$\displaystyle\mathcal{M}_{\leqslant_{C}}(\sigma):$ $\displaystyle m_{i,j}=1$
$\displaystyle\iff i\leqslant\sigma^{-1}(j)$
$\displaystyle\mathcal{M}_{\geqslant_{C}}(\sigma):$ $\displaystyle m_{i,j}=1$
$\displaystyle\iff i\geqslant\sigma^{-1}(j)$

Thus $\mathcal{M}_{=}(\sigma)$ is the usual permutation matrix,
$\mathcal{M}_{\neq}(\sigma)$ is its complement, and
$\mathcal{M}_{\leqslant_{R}},\mathcal{M}_{\geqslant_{R}},\mathcal{M}_{\leqslant_{C}},\mathcal{M}_{\geqslant_{C}}$
are obtained from the permutation matrix by propagating the ‘1’s down, up,
left, and right respectively.

######  Theorem 5.4.

There is a function $f:\mathbb{N}\to\mathbb{N}$ such that for any $0,1$-matrix
$M$ with a rank-$f(k)$ division $\mathcal{D}=(\mathcal{R},\mathcal{C})$, there
is some
$s\in\\{=,\neq,\leqslant_{R},\geqslant_{R},\leqslant_{C},\geqslant_{C}\\}$
such that for any permutation $\sigma$ on $k$ elements,
$\mathcal{M}_{s}(\sigma)$ is a submatrix of $M$.

Furthermore, $\mathcal{M}_{s}(\sigma)$ can be extracted from $M$ by picking at
most one row from each part of $\mathcal{R}$, and at most one column from each
part of $\mathcal{C}$.

###### Proof.

The first half of the statement is exactly [9, Theorem 27] restricted to
$0,1$-matrices. Although it is not stated, the proof of [9] also verifies the
additional requirement that only one row or column is extracted from each
part. We only need to carefully analyse it.

First, [9, Lemma 25] shows that matrices with rank-$f_{1}(k)$ divisions have
submatrices with rank-$k$ Latin divisions—a somewhat technical variant of rank
divisions. Crucially, the proof constructs a Latin division from a high-rank
division by deleting rows or columns, and merging parts of the division. Then,
[9, Lemma 30] extracts some encoding of permutations from these Latin
divisions by deleting additional rows and columns, and finally picking a
single row, resp. column, by part. Finally, [9, Lemma 33] shows that these
encodings of permutations can be refined to be one of
$\mathcal{M}_{=},\mathcal{M}_{\neq},\mathcal{M}_{\leqslant_{R}},\mathcal{M}_{\geqslant_{R}},\mathcal{M}_{\leqslant_{C}},\mathcal{M}_{\geqslant_{C}}$.

To summarize, the proof of [9, Theorem 27] consists only of extractions of
submatrices, and merging of parts of the division, with one step at which a
single row or column is picked per part of the division. This ensures the
desired property. ∎

Using Theorem 5.4, we can obtain encodings of arbitrary permutations in
$\mathcal{T}$. If $M$ is a $0,1$-matrix, we say that a tournament $T$ contains
a _chain order representation_ of $M$ if there are disjoint subsets $A,B$ of
$V(T)$ and two chain quasi-orders $\preceq_{1},\preceq_{2}$ on $T$ such that:

  * •

$A$ is totally ordered by $\preceq_{1}$, meaning that no two elements of $A$
are equivalent for $\preceq_{1}$,

  * •

$B$ is totally ordered by $\preceq_{2}$, and

  * •

the adjacency matrix of $A$ versus $B$ w.r.t. these orders is $M$.

One should not confuse $A,B$ with the chains inducing the orders
$\preceq_{1},\preceq_{2}$. See Figure 5 for an example.

$A$$B$ Figure 5. Chain representation of a permutation.

######  Claim 5.5.

For any $\sigma\in\mathfrak{S}_{k}$, there exist
$s\in\\{=,\neq,\leqslant_{R},\geqslant_{R},\leqslant_{C},\geqslant_{C}\\}$
such that some $T\in\mathcal{T}$ contains a chain order representation of
$\mathcal{M}_{s}(\sigma)$.

###### Proof.

Consider a rank-$f(k)$ division as in 5.3, where $f$ is the function of
Theorem 5.4. It consists of subsets
$A_{1},\dots,A_{f(k)},B_{1},\dots,B_{f(k)}$ such that the family of subsets
$(A_{i})_{i\in[f(k)]}$, resp. $(B_{i})_{i\in[f(k)]}$, is non-overlapping for
$\preceq^{A}$, resp. $\preceq^{B}$.

We choose some order on
$\mathcal{A}\stackrel{{\scriptstyle\text{def}}}{{=}}\bigcup_{i}A_{i}$ and
$\mathcal{B}\stackrel{{\scriptstyle\text{def}}}{{=}}\bigcup_{i}B_{i}$
compatible with $\preceq^{A}$ and $\preceq^{B}$ respectively, and apply
Theorem 5.4. This yields subsets $A\subset\mathcal{A}$ and
$B\subset\mathcal{B}$ such that the adjacency matrix $M_{A,B}$ of $A$ versus
$B$ is $\mathcal{M}_{s}(\sigma)$ for some
$s\in\\{=,\neq,\leqslant_{R},\geqslant_{R},\leqslant_{C},\geqslant_{C}\\}$.
Furthermore, each $A\cap A_{i}$ and $B\cap B_{i}$ contains at most one
element. Since for $i\neq j$, $A_{i}$ and $A_{j}$ are non-overlapping for
$\preceq^{A}$, this implies that for any $a\neq a^{\prime}$ in $A$, the
singletons $\\{a\\}$ and $\\{a^{\prime}\\}$ are non-overlapping, which
precisely means that $a$ and $a^{\prime}$ are not equivalent under
$\preceq^{A}$. Thus, $\preceq^{A}$ restricted to $A$ is in fact the total
order used to obtain the adjacency matrix $\mathcal{M}_{s}(\sigma)$, and the
same holds for $\preceq^{B}$ restricted to $B$. $\blacksquare$

###  5.3. Permutations between chains

5.5 proves that there are chain order representations of arbitrary
permutations. Such a representation involves four subsets: the $A,B$ which
induce $\mathcal{M}_{s}(\sigma)$ as adjacency matrix, and the two chains which
indirectly order $A$ and $B$. To simplify this picture, this section shows
that one can find encodings of permutations between two chains themselves, in
the following sense.

######  Claim 5.6.

For any permutation $\sigma\in\mathfrak{S}_{n}$, there exists in some
$T\in\mathcal{T}$ one of the following two structures:

  1. (1)

Either two disjoint subsets $A=\\{a_{1}<_{A}\dots<_{A}a_{n}\\}$,
$B=\\{b_{1}<_{B}\dots<_{B}b_{n}\\}$ of vertices such that

     * •

$A$ is a chain which corresponds to the order $<_{A}$ up to reversal, meaning
that either for all $i<j$ there is an edge $a_{i}\to a_{j}$, or for all $i<j$
there is an edge $a_{j}\to a_{i}$,

     * •

similarly $B$ is a chain corresponding to $<_{B}$ up to reversal, and

     * •

the adjacency matrix of $(A,<_{A})$ versus $(B,<_{B})$ is
$\mathcal{M}_{s}(\sigma)$ for some
$s\in\\{=,\neq,\leqslant_{R},\geqslant_{R},\leqslant_{C},\geqslant_{C}\\}$.

  2. (2)

Or a subset $A=\\{a_{1}<\dots<a_{n}\\}$ and a chain order $\preceq$ such that

     * •

$\preceq$ totally orders $A$,

     * •

$A$ is a chain which corresponds to $<$ up to reversal, and

     * •

the bi-order $(A,<,\preceq)$ is isomorphic to either $\mathcal{O}_{\sigma}$ or
$\mathcal{O}_{\sigma^{-1}}$.

###### Proof.

Let $\tau$ be a permutation, which will be chosen as a function of $\sigma$,
so as to apply Lemma 2.1. By 5.5, there exists a chain order representation of
$\tau$, consisting of disjoint subsets $A,B$ ordered by
$\preceq_{1},\preceq_{2}$ respectively, such that the adjacency matrix of $A$
versus $B$ for these orders is $\mathcal{M}_{s}(\tau)$ for some
$s\in\\{=,\neq,\leqslant_{R},\geqslant_{R},\leqslant_{C},\geqslant_{C}\\}$. We
enumerate $A=\\{a_{1},\dots,a_{n}\\}$ and $B=\\{b_{1},\dots,b_{n}\\}$ so that

$a_{i}\prec_{1}a_{j}\iff i<j\qquad\text{and}\qquad
b_{i}\prec_{2}b_{j}\iff\tau(i)<\tau(j)$

Thus, the map $\phi:A\to B$ defined as $\phi(a_{i})=b_{i}$ is the bijection
implicitly defined by $\mathcal{M}_{s}(\tau)$. We further define the order
$\preceq^{\prime}_{1}$ on $B$ as the image of $\preceq_{1}$ by $\phi$, and
similarly $\preceq^{\prime}_{2}$ is the inverse image of $\preceq_{2}$. Or,
more simply

$a_{i}\prec^{\prime}_{2}a_{j}\iff\tau(i)<\tau(j)\qquad\text{and}\qquad
b_{i}\prec^{\prime}_{1}b_{j}\iff i<j$

Recall that the biorder $\mathcal{O}_{\tau}=([n],<,<_{\tau})$ consists of the
natural order $<$, and the permutation order defined by $i<_{\tau}j$ if and
only if $\tau(i)<\tau(j)$. It is isomorphic to
$(A,\preceq_{1},\preceq^{\prime}_{2})$, and to
$(B,\preceq^{\prime}_{1},\preceq_{2})$, by the maps $i\mapsto a_{i}$ and
$i\mapsto b_{i}$ respectively. On this structure, we define a coloring
$\lambda:[n]^{2}\to\\{0,1\\}^{2}$ which combines the adjacency matrices of
$T[A]$ and $T[B]$, that is

$\lambda(i,j)=(a,b)\quad\text{where $a=1$, resp.\leavevmode\nobreak\ $b=1$,
iff $a_{i}\to a_{j}$, resp.\leavevmode\nobreak\ $b_{i}\to b_{j}$, is an edge}$

We now suppose that $\tau$ was chosen so that Lemma 2.1 can be applied to
obtain a monochromatic embedding of $\sigma$. That is, there exists
$Q\subset[n]$ such that $\mathcal{O}_{\tau}[Q]$ is isomorphic to
$\mathcal{O}_{\sigma}$, and the coloring $\lambda$ restricted to $Q\times Q$
depends only on the orders $<,<_{\tau}$.

Let
$A^{\prime}\stackrel{{\scriptstyle\text{def}}}{{=}}\textstyle\left\\{a_{i}\ |\
i\in Q\right\\}$ and
$B^{\prime}\stackrel{{\scriptstyle\text{def}}}{{=}}\textstyle\left\\{b_{i}\ |\
i\in Q\right\\}$ be the corresponding subsets. They form a chain
representation of $\mathcal{M}_{s}(\sigma)$. Furthermore, the direction of
edges in $T[A^{\prime}]$, resp. $T[B^{\prime}]$, depends only on the orders
$\preceq_{1},\preceq^{\prime}_{2}$, resp. $\preceq^{\prime}_{1},\preceq_{2}$.
By Lemma 2.2, this means that $T[A^{\prime}]$ is a transitive tournament whose
order corresponds to—in the sense of equal to or inverse of—either
$\preceq_{1}$ or $\preceq^{\prime}_{2}$, and similarly in $B^{\prime}$. We now
have to consider two cases.

  1. (1)

If edges in $T[A^{\prime}]$ correspond to the order $\preceq_{1}$, and edges
in $T[B^{\prime}]$ correspond to the order $\preceq_{2}$, then the chain
orders become redundant: we have obtained $\mathcal{M}_{s}(\sigma)$ as
adjacency matrix between two chains, up to some reversal of orders. This is
case 1 of the claim.

  2. (2)

Otherwise, if for instance the edges in $T[A^{\prime}]$ correspond to the
order $\preceq^{\prime}_{2}$, then $A^{\prime}$ is equipped with both the
orders $\preceq_{1}$ (as chain order) and $\preceq^{\prime}_{2}$ (from the
direction of edges), which together encode $\sigma$ as a bi-order. This is
case 2 of the claim. The situation is similar when the edges of
$T[B^{\prime}]$ correspond to $\preceq^{\prime}_{1}$.

∎

###  5.4. Canonical obstructions

In this section, we finally extract the obstructions of section 3 from the
structure described by 5.6.

######  Claim 5.7.

For any $k$ there exists a permutation $\sigma$ containing a $k$-grid and some
$s\in\\{=,\leqslant,\geqslant\\}$ such that
$\mathcal{F}_{s}(\sigma)\in\mathcal{T}$.

###### Proof.

We start with a permutation $\sigma_{1}$ containing sufficiently large grids,
which we will choose function of the desired $k$. We apply 5.6 to
$\sigma_{1}$, and consider the two possible cases.

#### Case 1

Assume first that we are in case 1 of 5.6, i.e. there are two chains $A,B$
with adjacency matrix $\mathcal{M}_{s}(\sigma_{1})$ for some
$s\in\\{=,\neq,\leqslant_{R},\geqslant_{R},\leqslant_{C},\geqslant_{C}\\}$. We
assume that $\sigma_{1}$ was chosen to contain a $(k+1)$-grid.

In this representation of $\sigma_{1}$, the direction of edges inside $A,B$ is
only controlled up to reversal of their order. This is not an issue: reversing
the order in $A$, resp. $B$, corresponds to reversing the order of columns,
resp. rows, of $\mathcal{M}_{s}(\sigma_{1})$, which yields
$\mathcal{M}_{s^{\prime}}(\sigma_{2})$ for some other $s^{\prime}$, and some
new permutation $\sigma_{2}$. This $\sigma_{2}$ is obtained by pre- or post-
composing $\sigma_{1}$ with the map $i\mapsto(n+1)-i$. This transformation
preserves grids, hence $\sigma_{2}$ also has a $(k+1)$-grid. Thus we can
assume that the direction of edges in $A,B$ exactly matches the order of rows
and columns in the matrix.

Next, we can assume that $s$ is one of $=,\leqslant_{R},\geqslant_{R}$.
Indeed, if this is not the case, we swap the roles of $A$ and $B$, which
corresponds to transposing and complementing (i.e. swapping ‘0’ for ‘1’ and
vice versa) the adjacency matrix. If the matrix was
$\mathcal{M}_{\neq}(\sigma_{2})$ before, this yields
$\mathcal{M}_{=}(\sigma_{2}^{-1})$ instead. If the matrix was
$\mathcal{M}_{\leqslant_{C}}(\sigma_{2})$, the situation is only slightly more
complex: transposing and complementing yields
$\mathcal{M}_{>_{R}}(\sigma_{2}^{-1})$, meaning the matrix defined as
$\mathcal{M}_{\geqslant_{R}}(\sigma_{2}^{-1})$, except for entries
$(i,\sigma_{2}^{-1}(i))$ which are ‘0’ instead of ‘1’. However, dropping the
first row and the column with index $\sigma_{2}(n)$—both of which contain only
‘0’s—yields a matrix of the form $\mathcal{M}_{\geqslant_{R}}(\sigma_{3})$.
One can then verify that $\sigma_{3}$ still contains a $k$-grid.

In all cases, we obtain some permutation $\sigma_{3}$ with a $k$-grid, and two
chains between which the adjacency matrix is $\mathcal{M}_{=}(\sigma_{3})$,
$\mathcal{M}_{\leqslant_{R}}(\sigma_{3})$, or
$\mathcal{M}_{\geqslant_{R}}(\sigma_{3}$). This gives exactly one of the
structures
$\mathcal{F}_{=}(\sigma_{3}^{-1}),\mathcal{F}_{\leqslant}(\sigma_{3}^{-1}),\mathcal{F}_{\geqslant}(\sigma_{3}^{-1})$,
with the rows of the matrix corresponding to the set called $Y$ in section 3.

#### Case 2

We now assume that we are in case 2 of 5.6, i.e. there is a set of vertices
$A$ with a chain order $\preceq$, and a second order $<$, such that the edges
of $A$ coincide with $<$, possibly up to reversal, and $(A,<,\preceq)$ is
isomorphic to either $\mathcal{O}_{\sigma_{1}}$ or
$\mathcal{O}_{\sigma_{1}^{-1}}$. The reversal of $<$, and swapping
$\sigma_{1}$ for $\sigma_{1}^{-1}$ both preserve the size of grids. Thus we
can assume that edges in $A$ are $u\to v$ if and only if $u<v$, and that
$(A,<,\preceq)$ is isomorphic to $\mathcal{O}_{\sigma_{1}}$.

Consider the chain $C$ and orientation $o$ which induce $\preceq$, i.e.
$\preceq\,=\,\preceq_{C}^{o}$. For simplicity, we will assume that the
orientation $o$ is ‘$+$’, the proof is similar in the case of ‘$-$’.

A simple grid argument (and very specific case of Lemma 2.1) allows to extract
a similar substructure for a smaller $\sigma_{2}$, with the assumption that
either $C$ and $A$ are disjoint, or $A\subseteq C$. But the latter is clearly
impossible unless $\sigma_{2}$ is the identity or its reverse, which we can
assume is not the case. Thus, we can now assume that $A$ and $C$ are disjoint,
and that the encoded permutation $\sigma_{2}$ still contains large grids.

Enumerate $A$ in the order $a_{1}\preceq_{C}^{+}\dots\preceq_{C}^{+}a_{n}$.
For each $i$ define $c_{i}\in C$ to be minimal w.r.t. the internal order of
$C$ with the property that $a_{i}\not\in N^{+}(c_{i})$. Because $C$ and $A$
are disjoint, such a $c_{i}$ must exist except possibly when $i=n$. At the
cost of removing $a_{n}$ from $A$ if necessary, we assume there is also some
$c_{n}$ matching $a_{n}$. The nodes $c_{i}$ verify that there is an edge
$c_{i}\to c_{j}$ if and only if $i<j$. We can now assume that the chain $C$
consists only of $c_{1},\dots,c_{n}$, as the other elements are not relevant
to the order on $A$. At this point, we have the following structure: $C$ is a
chain for the natural order $c_{1},\dots,c_{n}$, $A$ is a chain for the
permuted order corresponding to $\sigma_{2}$, and there are edges $a_{i}\to
c_{i}$ for all $i$, and $c_{i}\to a_{j}$ for all $i<j$. What remains
unspecified is the direction of edges $a_{i}c_{j}$ with $i<j$.

We will again apply Lemma 2.1 to control these edges. Consider the bi-order
$\mathcal{O}_{\sigma_{2}}=([n],<,<_{\sigma_{2}})$, and add a tournament on the
vertices of this bi-order, where for $i<j$ the direction of the edge $ij$
matches that of $a_{i}c_{j}$. Assuming that $\sigma_{2}$ contains a
sufficiently large grid, we can apply Lemma 2.1 to this bi-order plus
tournament structure to extract an encoding of any specified permutation
$\sigma_{3}$. This encoding has exactly the same shape as before: two chains
$C,A$, where $C$ induces a total chain order on $A$, but with the additional
requirement that for all $i<j$, the direction of the edge $a_{i}c_{j}$ only
depends on whether or not $i<j$ and whether or not $i<_{\sigma_{3}}j$. Since
we only consider edges with $i<j$, the dependency on $i<j$ is meaningless.
Then, there are only four cases to consider.

  1. (1)

If for all $i<j$, there is an edge $c_{j}\to a_{i}$, then $A$ and $C$ induce
the structure $\mathcal{F}_{=}(\sigma_{3})$, and we are done as we can assume
that $\sigma_{3}$ contains the desired permutation $\sigma$ as pattern.

  2. (2)

Similarly, if for all $i<j$, there is an edge $a_{i}\to c_{j}$, then $A$ and
$C$ induce the structure $\mathcal{F}_{\geqslant}(\sigma_{3})$.

  3. (3)

Assume now that for $i<j$, there is an edge $a_{i}\to c_{j}$ if and only if
$\sigma_{3}(i)<\sigma_{3}(j)$. Given a desired permutation $\sigma$ on $n$
elements, we choose $\sigma_{3}$ to be the permutation on $2n$ elements
defined by

$\sigma_{3}(2i-1)=\sigma(i)\qquad\sigma_{3}(2i)=n+i$

Renaming $A=\\{a_{1},\dots,a_{2n}\\}$ and $C=\\{c_{1},\dots,c_{2n}\\}$, we now
extract the odd indices in $A$ and the even indices in $C$, that is we define
$a^{\prime}_{i}=a_{2i-1}$ and $c^{\prime}_{i}=c_{2i}$. For any $i,j$, remark
that $\sigma_{3}(2i-1)<\sigma_{3}(2j)$ always holds—this will allow us to get
rid of the dependency on $<_{\sigma_{3}}$.

If $i>j$, then we have $2i-1>2j$, hence there is an edge $c^{\prime}_{j}\to
a^{\prime}_{i}$ (from the chain order structure) but if $i\leqslant j$, we
instead have the edge $a^{\prime}_{i}\to c^{\prime}_{j}$ (by hypothesis on the
orientation of edges $a_{i}c_{j}$ when $i<j$). Finally, on the extracted
vertices $a^{\prime}_{1},\dots,a^{\prime}_{n}$, there is an edge
$a^{\prime}_{i}\to a^{\prime}_{j}$ if and only if
$\sigma_{3}(2i-1)<\sigma_{3}(2j-1)$, that is if and only if
$\sigma(i)<\sigma(j)$. Thus, the structure induced by the $a^{\prime}_{i}$ and
$b^{\prime}_{j}$ is exactly $\mathcal{F}_{\geqslant}(\sigma)$.

  4. (4)

The proof is similar when there is an edge $a_{i}\to c_{j}$ if and only if
$\sigma_{3}(i)<\sigma_{3}(j)$.

$\blacksquare$

To conclude the proof of Theorem 5.1, we apply 5.7 to arbitrarily large $k$.
By pigeonhole principle, this yields a family of permutations
$(\sigma_{n})_{n\in\mathbb{N}}$ with arbitrarily large grids, and a _fixed_
$s\in\\{=,\leqslant,\geqslant\\}$ such that
$\mathcal{F}_{s}(\sigma_{n})\in\mathcal{T}$. Since the pattern closure of such
a family contains all permutations, it follows that
$\mathcal{F}_{s}\subseteq\mathcal{T}$.

##  6\. Dense oriented graphs and relational structures

In this final section, we generalise our main result in two directions: we
replace tournaments by oriented graphs with bounded independent sets, and
consider relational structures formed from such oriented graphs augmented by
arbitrary binary relations.

###  6.1. Generalised binary search trees

We first generalise the notion of BST to arbitrary oriented graphs. A BST on
an oriented graph $D$ is a rooted ordered _ternary_ tree $S$ (meaning that
each node has a left, center, and right child, any of which may be missing)
satisfying the following condition. For any node $x$ of the tree, let
$L_{x},C_{x},R_{x}$ denote the left, center, and right subtrees of $x$. Then

$L_{x}\subseteq N^{-}(x)\qquad C_{x}\cap N(x)=\varnothing\qquad L_{r}\subseteq
N^{+}(x).$

The left-to-right order $<_{S}$ corresponding to the tree is the order
satisfying for all node $x$

$L_{x}<_{S}x<_{S}C_{x}<_{S}R_{x}.$

The choice of placing $C_{x}$ after and not before $x$ here is arbitrary.

With this definition, we still verify that a branch $B$ of the tree is an
acyclic subgraph in which the direction of edges matches $<_{S}$. However, it
is not necessarily a chain. Indeed, if $x\in B$ is such that the branch $B$
descends into the central subtree of $x$, then $x$ is non-adjacent to all its
descendants in $B$. Nonetheless, $B$ can be transformed into a chain at a
limited cost. Let $X\subset B$ be the set of all such center-branching nodes
in $B$. Then $X$ is an independent set (and thus $|{X}|\leqslant\alpha(D)$),
while the rest $B\setminus X$ of the branch is a chain.

Next, we generalise chain quasi-orders. For $C$ a chain in $D$ enumerated as
$C=\\{c_{1},\dots,c_{k}\\}$ such that $c_{i}\to c_{j}$ iff $i<j$, we define

$A_{i}=\Big{(}\bigcap_{j\leqslant i}N^{+}(c_{i})\Big{)}\setminus
C\qquad\text{and}\qquad B_{i}=A_{i-1}\setminus N^{+}(c_{i}).$

The chain quasi-order $\preceq_{C}^{+}$ is then defined by

$B_{1}\prec_{C}^{+}c_{1}\prec_{C}^{+}B_{2}\prec_{C}^{+}c_{2}\prec_{C}^{+}\dots
B_{k}\prec_{C}^{+}c_{k}\prec_{C}^{+}A_{k},$

with $B_{1},\dots,B_{k}$ and $A_{k}$ being the equivalence classes. That is,
we order a node $x$ according to the smallest $i$ such that $x\not\in
N^{+}(c_{i})$. The dual quasi-order $\preceq_{C}^{-}$ is defined in the same
way, but reversing the direction of all edges.

We can now generalise the partition extraction lemma to oriented graphs with
bounded $\alpha$.

######  Lemma 6.1.

Let $D$ be an oriented graph with independence number $\alpha$, and let $S$ be
a BST of $D$ with associated order $<_{S}$. There is a function
$f(k)=2^{O(k)}$ depending only on $\alpha$ satisfying the following. For any
family $\mathcal{P}$ of at least $f(k)$ disjoint intervals of $<_{S}$, there
is a chain $C$ in $D$, an orientation $o\in\\{+,-\\}$ and a subfamily
$\mathcal{P}^{\prime}\subset\mathcal{P}$ such that
$|{\mathcal{P}^{\prime}}|\geqslant k$ and such that the parts of
$\mathcal{P}^{\prime}$ are non-overlapping for $\preceq_{C}^{o}$.

Furthermore, $C$, $o$, and $\mathcal{P}^{\prime}$ can be computed in linear
time.

###### Proof.

The proof of Lemma 4.2 can be applied to directed graphs with essentially no
modification. The only issue is that it does not yield a chain quasi-order,
because the branches of $S$ are not themselves chains. Instead, the quasi-
order $\preceq_{C}^{o}$ compatible with the resulting partition
$\mathcal{P}^{\prime}$ can be described by the following structure (up to
inversion of all edges). There is a sequence $C=\\{c_{1},\dots,c_{k}\\}$ of
vertices. Each $c_{i}$ has a _type_ : either _complete_ or _anti-complete_. If
$c_{i}$ is complete, then for all $j>i$ there is an edge $c_{i}\to c_{j}$. If
$c_{i}$ is anti-complete, then for all $j>i$ there is no edge between $c_{i}$
and $c_{j}$. We then define subsets $A_{i}$ by induction: $A_{0}$ is
$V(T)\setminus C$, and $A_{i}$ is defined as $A_{i-1}\cap N^{+}(c_{i})$ when
$c_{i}$ is complete or as $A_{i-1}\setminus N(c_{i})$ when $c_{i}$ is anti-
complete. Then $B_{i}$ is defined as $A_{i-1}\setminus A_{i}$, and the quasi-
order is

$B_{1}\prec_{C}^{+}c_{1}\prec_{C}^{+}B_{2}\prec_{C}^{+}c_{2}\prec_{C}^{+}\dots
B_{k}\prec_{C}^{+}c_{k}\prec_{C}^{+}A_{k},$

When there are no anti-complete nodes in $C$, this structure is exactly a
chain quasi-order.

Remark now that the anti-complete nodes in $C$ induce an independent set. It
follows that there are at most $\alpha$ anti-complete nodes. Then, we can
simply remove any anti-complete node $c_{i}$, and remove from
$\mathcal{P}^{\prime}$ any part which intersects $B_{i}$, at the cost of at
most $\alpha$ parts of $\mathcal{P}^{\prime}$. ∎

###  6.2. Extracting permutation encodings

We now fix $\Sigma$ a binary relational signature, with a distinguished
relation $A$, and consider $\Sigma$-structures in which $A$ is interpreted as
an oriented graph with independence number bounded by some constant $k$.

The notion of chain order representation of permutations of section 5.2 has a
natural generalisation in this context: a chain order representation of
$\sigma$ in a structure $S$ consists of two disjoint subsets $X,Y$ of
vertices, two chain orders $\preceq^{X},\preceq^{Y}$ in the oriented graph
represented by $A^{S}$ which totally order $X$ and $Y$ respectively, and
finally an encoding $\mathcal{M}_{s}(\sigma)$ of $\sigma$ as the adjacency
matrix of $X$ and $Y$ for _any_ of the relations of $\Sigma$.

Using Lemma 6.1, it is straightforward to generalise Theorem 1.5.

######  Theorem 6.2.

Let $\mathcal{S}$ be a hereditary class of $\Sigma$-structures in which $A$ is
interpreted as oriented graphs with bounded independence number. If there are
structures $S\in\mathcal{S}$ with BST orders $<$ for which
$\operatorname{tww}(S,<)$ is arbitrarily large, then $\mathcal{S}$ contains
chain order representations of all permutations.

The proof is the same as the first half of Theorem 1.5, that is sections 5.1
and 5.2. One can then prove a result comparable to Theorem 1.5.

######  Theorem 6.3.

Let $\mathcal{S}$ be a hereditary class of $\Sigma$ containing chain order
representations of all permutations. Then $\mathcal{S}$

  1. (1)

has unbounded twin-width;

  2. (2)

contains at least $(\left\lfloor\frac{n}{c}\right\rfloor)!$ tournaments on $n$
vertices counted up to isomorphism, for some universal constant $c$;

  3. (3)

efficiently interprets the class of all graphs;

  4. (4)

and has $\textrm{AW}[*]$-hard FO model checking problem.

It is then straightforward to obtain the analogous of our main theorem for
these structures.

######  Theorem 6.4.

Let $\mathcal{S}$ be a class of $\Sigma$-structures in which $A$ is
interpreted as oriented graphs with independence number at most some constant
$k$. Under the assumption $\textrm{FPT}\neq\textrm{AW}[*]$, the following are
equivalent:

  1. (1)

$\mathcal{S}$ has bounded twin-width,

  2. (2)

FO model checking in $\mathcal{S}$ is FPT,

  3. (3)

FO model checking in $\mathcal{S}$ is not $\textrm{AW}[*]$-hard,

  4. (4)

$\mathcal{S}$ does not interpret the class of all graphs,

  5. (5)

$\mathcal{S}$ is monadically NIP,

  6. (6)

$\mathcal{S}$ contains at most $c^{n}$ structures on $n$ vertices for some
constant $c$, counted up to isomorphism.

Furthermore, there is an FPT algorithm which approximates the twin-width of
such $\Sigma$-structures by a function depending of $\Sigma$ and $k$.

Starting from the chain representation of arbitrary permutations, it is also
possible using Lemma 2.1 to extract some canonical structure, that is a chain
order representation of permutations where all unspecified edges and remaining
relations only depend on the two orders which encode the permutation. Doing so
leads to a finite collection of classes
$\mathcal{F}_{1},\dots,\mathcal{F}_{n}$ of obstructions satisfying the
following

######  Theorem 6.5.

Let $\mathcal{S}$ be a class of $\Sigma$-structures in which $A$ is
interpreted as an oriented graph with independence number at most some
constant $k$. Then $\mathcal{S}$ has bounded twin-width if and only if it does
not contain any $\mathcal{F}_{i}$ as a subset.

Naturally, the collection of classes $\mathcal{F}_{1},\dots,\mathcal{F}_{n}$
depends on the signature $\Sigma$ and the bound $k$.

##  7\. Conclusion

For hereditary classes of tournaments—or more generally dense oriented
graphs—we have characterised FPT FO model checking, NIP, and single-
exponential growth: the three notions are equivalent, and coincide with
bounded twin-width. Furthermore, each of these notions shows a dichotomic gap:
between FPT and $\textrm{AW}[*]$-hardness for the complexity of model
checking, between being monadically NIP and interpreting all graphs for the
model theoretic part, and between growth $c^{n}$ and
$\left(\frac{n}{c}\right)!$ for enumeration.

At the core of our proof is a simple procedure to choose an order on any given
tournament, akin to binary search trees. These BST orders have the crucial
property that they are always good orders for twin-width.

The equivalences we prove between e.g. FPT FO model checking and bounded twin-
width or single-exponential growth do not hold in the case of arbitrary
graphs: graphs with bounded degree are counterexamples. However, they are
related to interesting and widely open questions such as the conjecture that a
class has FPT FO model checking if and only if it is NIP. In a different
direction, it is natural to wonder if techniques we have developed based on
BST orderings can be used to prove new results on tournaments.

## Acknowledgments

The authors would like to thank Édouard Bonnet for stimulating discussions on
the topics of this work, and Szymon Toruńczyk for helpful explanations on the
notion of restrained classes.

## References

  * [1] Nir Ailon, Moses Charikar, and Alantha Newman.  Aggregating inconsistent information: Ranking and clustering.  J. ACM, 55(5), nov 2008.
  * [2] Noga Alon, Graham Brightwell, H.A. Kierstead, A.V. Kostochka, and Peter Winkler.  Dominating sets in k-majority tournaments.  Journal of Combinatorial Theory, Series B, 96(3):374–387, 2006\.
  * [3] Jakub Balabán and Petr Hlinený.  Twin-width is linear in the poset width.  In Petr A. Golovach and Meirav Zehavi, editors, 16th International Symposium on Parameterized and Exact Computation, IPEC 2021, September 8-10, 2021, Lisbon, Portugal, volume 214 of LIPIcs, pages 6:1–6:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [4] Manuel Bodirsky.  Ramsey classes: examples and constructions.  Surveys in combinatorics, 424:1, 2015.
  * [5] Mikołaj Bojańczyk.  personal communication, jul 2022.
  * [6] Édouard Bonnet, Dibyayan Chakraborty, Eun Jung Kim, Noleen Köhler, Raul Lopes, and Stéphan Thomassé.  Twin-width VIII: delineation and win-wins.  CoRR, abs/2204.00722, 2022.
  * [7] Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant.  Twin-width II: small classes.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), pages 1977–1996, 2021.
  * [8] Édouard Bonnet, Colin Geniet, Romain Tessera, and Stéphan Thomassé.  Twin-width VII: groups.  CoRR, abs/2204.12330, 2022.
  * [9] Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, and Szymon Toruńczyk.  Twin-width IV: ordered graphs and matrices.  CoRR, abs/2102.03117, 2021, to appear at STOC 2022.
  * [10] Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant.  Twin-width I: tractable FO model checking.  J. ACM, 69(1):3:1–3:46, 2022.
  * [11] Édouard Bonnet, Jaroslav Nesetril, Patrice Ossona de Mendez, Sebastian Siebertz, and Stéphan Thomassé.  Twin-width and permutations.  CoRR, abs/2102.06880, 2021.
  * [12] Youssef Boudabbous and Maurice Pouzet.  The morphology of infinite tournaments; application to the growth of their profile.  European Journal of Combinatorics, 31(2):461–481, 2010.  Combinatorics and Geometry.
  * [13] Samuel Braunfeld and Michael C Laskowski.  Existential characterizations of monadic nip.  arXiv preprint arXiv:2209.05120, 2022.
  * [14] Maria Chudnovsky, Alexandra Fradkin, and Paul Seymour.  Tournament immersion and cutwidth.  J. Comb. Theory, Ser. B, 102:93–101, 01 2012.
  * [15] Rodney G Downey, Michael R Fellows, and Udayan Taylor.  The parameterized complexity of relational database queries and an improved characterization of W[1].  DMTCS, 96:194–213, 1996.
  * [16] Fedor V. Fomin and Michał Pilipczuk.  On width measures and topological problems on semi-complete digraphs.  Journal of Combinatorial Theory, Series B, 138:78–165, 2019.
  * [17] Alexandra Fradkin and Paul Seymour.  Tournament pathwidth and topological containment.  Journal of Combinatorial Theory, Series B, 103(3):374–384, 2013\.
  * [18] Jakub Gajarskỳ, Petr Hlinenỳ, Daniel Lokshtanov, Jan Obdralek, Sebastian Ordyniak, MS Ramanujan, and Saket Saurabh.  FO model checking on posets of bounded width.  In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 963–974. IEEE, 2015.
  * [19] Jakub Gajarský, Petr Hliněný, Jan Obdržálek, Daniel Lokshtanov, and M. S. Ramanujan.  A new perspective on fo model checking of dense graph classes.  ACM Trans. Comput. Logic, 21(4), jul 2020.
  * [20] Ronald L Graham, Bruce L Rothschild, and Joel H Spencer.  Ramsey theory, volume 20.  John Wiley & Sons, 1991.
  * [21] Sylvain Guillemot and Dániel Marx.  Finding small patterns in permutations in linear time.  In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 82–101, 2014.
  * [22] Mithilesh Kumar and Daniel Lokshtanov.  Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Tournaments.  In Nicolas Ollinger and Heribert Vollmer, editors, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), volume 47 of Leibniz International Proceedings in Informatics (LIPIcs), pages 49:1–49:13, Dagstuhl, Germany, 2016. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [23] Adam Marcus and Gábor Tardos.  Excluded permutation matrices and the Stanley-Wilf conjecture.  J. Comb. Theory, Ser. A, 107(1):153–160, 2004.
  * [24] Serguei Norine, Paul Seymour, Robin Thomas, and Paul Wollan.  Proper minor-closed families are small.  Journal of Combinatorial Theory, Series B, 96(5):754–757, 2006\.
  * [25] Michał Pilipczuk.  Tournaments and Optimality: New Results in Parameterized Complexity.  PhD thesis, University of Bergen, August 2013.