# First Order Logic and Twin-Width in Tournaments

Colin Geniet, Stéphan Thomassé

► To cite this version:

Colin Geniet, Stéphan Thomassé. First Order Logic and Twin-Width in Tournaments. 31st Annual European Symposium on Algorithms (ESA 2023), Sep 2023, Amsterdam, Netherlands. pp.53:1–53:14, 10.4230/LIPIcs.ESA.2023.53 . hal-04249625

HAL Id: hal-04249625

https://hal.science/hal-04249625v1

Submitted on 19 Oct 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# First Order Logic and Twin-Width in Tournaments

Colin Geniet

<figure><img src="image_2.png" /></figure>

Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France

Stéphan Thomassé

<figure><img src="image_3.png" /></figure>

Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France

## 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 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 FPT time for an ordered structure $(T, <)$, this provides a FPT approximation of twin-width for tournaments.

**2012 ACM Subject Classification** Theory of computation → Finite Model Theory; Mathematics of computing → Graph algorithms; Mathematics of computing → Graph enumeration

**Keywords and phrases** Tournaments, twin-width, first-order logic, model checking, NIP, small classes

**Digital Object Identifier** 10.4230/LIPIcs.ESA.2023.53

**Related Version** Full Version: https://arxiv.org/abs/2207.07683 [16]

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

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

# 1 Introduction

Tournaments can represent the outcome of a ranking of candidates, which need not be a total order. E.g., in the Condorcet voting paradox, 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 preference relation. Classical algorithmic problems arise from trying to choose a subset of winners: the DOMINATING SET (DS) problem asks for a subset $D$ which is preferred to any other candidate, i.e. for any $y \notin D$, there is some $x \in D$ which is preferred to $y$; and the FEEDBACK VERTEX SET (FVS) problem asks to build a preference order by ignoring a subset of candidates.

These problems can be parameterized by the size $k$ of the desired solution. A problem is fixed parameter tractable (FPT) if it admits an algorithm running in time $O(f(k) \cdot n^c)$, for some function $f$ and constant $c$. It is known that FVS is FPT for tournaments [18], whereas DS is unlikely to be FPT. However general tournaments may not be representative of usual instances: for example, majority voting tournaments with a fixed number $r$ of 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 $r$-majority tournaments, because the size of a minimum dominating set is bounded by $f(r)$. This exemplifies how difficult problems can become easy on restricted classes, here bounded VC-dimension.

<figure><img src="image_4.png" /></figure>

© Colin Geniet and Stéphan Thomassé;
licensed under Creative Commons License CC-BY 4.0

31st Annual European Symposium on Algorithms (ESA 2023).

Editors: Inge Li Gørtz, Martin Farach-Colton, Simon J. Puglisi, and Grzegorz Herman; Article No. 53;
pp. 53:1–53:14

<figure><img src="image_5.png" /></figure>

Leibniz International Proceedings in Informatics
LIPICS
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
## 53:2 First Order Logic and Twin-Width in Tournaments

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

$$ \exists x_1, x_2, \dots, x_k. \forall y. (y = x_1) \lor (y \to x_1) \lor \dots \lor (y = x_k) \lor (y \to x_k). $$

That k-FVS is also expressible in first-order logic 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, which is easily expressed in FO. Thus k-DS and k-FVS are instances of the FO MODEL CHECKING (or FOMC) problem: given as input a tournament T and a first-order formula $\phi$, does T satisfies $\phi$? FO model checking is difficult on the class of all graphs [12], and using back-and-forth FO encodings, one can show that it is just as hard on tournaments. We investigate which subclasses of tournaments admit an FPT algorithm for FO model checking.

### 1.1 Main results

We prove a dichotomy: in any class $\mathcal{T}$ of tournaments (closed under subtournaments), FOMC is either FPT or AW[*]-complete. The key of this dichotomy is twin-width (tww), a complexity parameter introduced by Bonnet et al. [7]: FOMC in $\mathcal{T}$ is FPT if $\mathcal{T}$ has bounded twin-width, and AW[*]-complete otherwise. This dichotomy coincides with a model theoretic characterisation: the class $\mathcal{T}$ has bounded twin-width if and only if it is NIP, meaning that arbitrary graphs cannot be described from tournaments in $\mathcal{T}$ through a fixed FO formula. This equivalence of twin-width and NIP, called *delineation*, was conjectured for tournaments in [4]. The equivalence between NIP and FPT FO model checking also confirms the *nowhere FO dense* conjecture of Gajarský et al. [15] for tournaments.

Furthermore, the dichotomy for FO model checking coincides with a gap in the growth function of the class $\mathcal{T}$, i.e. the number of tournaments of $\mathcal{T}$ on $n$ vertices up to isomorphism. If $\mathcal{T}$ has bounded twin-width, then its growth is at most $2^{O(n)}$, whereas it is at least $(\lfloor n/2 \rfloor - 1)!$ when twin-width is unbounded. This exponential/factorial gap generalises the Marcus-Tardos theorem on permutations avoiding a fixed pattern [19]. It may also be compared to results of Boudabbous and Pouzet [9] which show that hereditary classes of tournaments have growth either at most polynomial or at least exponential.

**Theorem 1.1.** Let $\mathcal{T}$ be a hereditary class of tournaments. Under the assumption $\text{FPT} \neq \text{AW[*]}$, the following are equivalent:

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

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

3. FO model checking in $\mathcal{T}$ is not AW[*]-complete,

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

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

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

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

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

**Theorem 1.2.** There are three hereditary classes $\mathcal{F}_=$, $\mathcal{F}_\leq$, $\mathcal{F}_\geq$ such that a hereditary class $\mathcal{T}$ of tournaments has unbounded twin-width if and only if one of $\mathcal{F}_=$, $\mathcal{F}_\leq$, $\mathcal{F}_\geq$ 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 an FPT algorithm, which given as input a tournament $T$, produces either a witness $\text{tww}(T) \le f(k)$, or a witness that $\text{tww}(T) \ge k$.

These results can be generalised to oriented graphs with bounded independence number, and to relational structures consisting of a tournament augmented by arbitrary binary relations, see the full version of this paper.

## 1.2 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 appears in the founding works of Guillemot and Marx [17] and Bonnet et al. [7], and the relation between twin-width and orders has been deeply explored in [6]. However it is difficult to witness lower bounds on twin-width with this approach: one needs to somehow prove that all orders contain grids. To this purpose, we want to construct in any tournament $T$ an order $<$ which, if $T$ has small twin-width, is a witness of this fact, i.e. $\text{tww}(T, <) \le f(\text{tww}(T))$.

A tentative approach to obtain such an order is to describe it in FO logic. Indeed, FO transductions preserve twin-width up to some function [7, Theorem 39]. Thus, if $\Phi$ is a transduction which on any tournament $T$ gives some order $<$, then $\text{tww}(T, <) \le f(\text{tww}(T))$ as desired. With a few additional requirements, such as $<$ being efficiently computable, it would be straightforward to obtain our results from the case of ordered graphs [6]. However this approach is impossible: to transduce a total order on the iterated lexicographic product of the 3-cycle with itself, one needs a first-order formula with size increasing in the number of iterations [3]. Remark that this counter-example has twin-width 1.

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 [6]. We then extract a subtournament $T' \subset T$ which still has a substantial (but logarithmically smaller) high-rank grid, and in which $<$ is roughly described by a FO transduction. This is enough to witness that $T$ has large twin-width. Using Ramsey arguments, we extract from $T'$ an obstruction $\mathcal{F}_=$, $\mathcal{F}_\le$, or $\mathcal{F}_>$. The construction of the order is remarkably simple: we consider a binary search tree (BST), 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. To summarize, the crucial property is

**► Lemma 1.4.** There is a function $f$ such that for any tournament $T$ and BST order $<$
$\text{tww}(T, <) \le f(\text{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 [6, Theorem 2], which is FPT. 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 obstructions $\mathcal{F}_=$, $\mathcal{F}_\le$, $\mathcal{F}_>$.

**► 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 $\text{tww}(T, <)$ is arbitrarily large. Then $\mathcal{T}$ contains one of the classes $\mathcal{F}_=$, $\mathcal{F}_\le$, $\mathcal{F}_>)$ as a subclass.

Finally, the classes $\mathcal{F}_=$, $\mathcal{F}_\le$, $\mathcal{F}_>$ are complex in all the senses considered by Theorem 1.1.
53:4 First Order Logic and Twin-Width in Tournaments

► **Theorem 1.6.** For each $R \in \{=, \leq, \geq\}$, the class $\mathcal{F}_R$

1. has unbounded twin-width;

2. contains at least ($\lfloor n/2 \rfloor - 1$)! tournaments on $n$ vertices counted up to isomorphism;

3. contains at least ($\lfloor n/2 \rfloor - 1$)! $n!$ tournaments on vertex set $\{1, \dots, n\}$ counted up to equality;

4. efficiently interprets the class of all graphs;

5. and has $AW[*]$-hard FO model checking problem.

Theorems 1.5 and 1.6 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}_\leq$, $\mathcal{F}_\geq$, hence its tournaments must still have bounded twin-width when paired with BST orders. Finally, Theorems 1.2 and 1.6 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 [7, Theorem 1], FO model checking has an FPT algorithm when a witness of bounded twin-width is given. Combined with Theorem 1.3, this gives an FPT algorithm for classes of tournaments with bounded twin-width. By [7, Theorem 39], a class of structures with bounded twin-width cannot transduce all graphs. Finally, by [8, 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$.

1.3 Context and related parameters

It is interesting to compare twin-width to other classical complexity measures for tournaments. Bounded twin-width implies bounded VC-dimension, since classes with unbounded VC-dimension contain all possible bipartite subgraphs, which is against single-exponential growth. *Cutwidth* was introduced by Chudnovsky, Fradkin and Seymour [11] to study tournament immersions. Bounded cutwidth is certified by a vertex ordering which can be shown to exclude grids, hence it is also a witness of bounded twin-width. Another parameter, closely related to subdivisions in tournaments, is *pathwidth*, studied by Fradkin and Seymour [14]. Bounded pathwidth of tournaments implies bounded cliquewidth, which in turn also implies bounded twin-width, see [7]. Thus, we have the following chain of inclusions (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, see Fomin and Pilipczuk [13, 21].

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.

1.4 Organisation of the paper

Section 2 summarises our definitions and notations. In section 3 the classes $\mathcal{F}_=$, $\mathcal{F}_\leq$, $\mathcal{F}_\geq$ of obstructions to twin-width are defined, and we prove Theorem 1.6. 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 Lemma 1.4 using the former lemma, combined with results of [6]. See the extended version of this paper [16] for the full proof of Theorem 1.5, which builds on that of Lemma 1.4.
## 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\}$.

### 2.1 Tournaments, relational structures

A tournament $T$ consists of a set of vertices $V(T)$, and for each $u \neq v \in V(T)$, an arc oriented either $u \to v$ or $v \to u$ (but not both). If $x \in V(T)$, then $N^+(x) = \{y \mid x \to y\}$ and $N^-(x) = \{y \mid y \to x\}$ are the in- and out-neighbourhood respectively. A tournament is transitive if it contains no directed cycle, in which case it defines a total order on its vertices. We call *chain* a subset $X \subset V(D)$ which induces a transitive tournament.

Relational structures generalise graphs and tournaments. A relational signature is a finite set $\Sigma$ of relation symbols $R$, each with an arity $r \in \mathbb{N}$. A $\Sigma$-structure consists of a domain $A$ (vertices), and for each symbol $R \in \Sigma$ of arity $r$, an interpretation $R^S \subseteq A^r$ (hyperedges). E.g., tournaments and graphs are structures over a signature with a single binary relation. We restrict ourselves to *binary* structures, i.e. where all relation symbols have arity 2. An *ordered structure* $S$ is a structure over a relation $\Sigma$ with a special symbol $<$, whose interpretation $<^S$ is a total order on the domain of $S$.

If $S$ is a structure with domain $A$ and $B \subseteq A$, the substructure $S[B]$ induced by $B$ has domain $B$, and interprets each relation $R$ as the restriction of $R^S$ to $B$. All classes of structures considered here are *hereditary*, i.e. closed under induced substructures.

### 2.2 Matrices

A matrix is a map $M : R \times C \to \Gamma$, where $R, C$ are the *ordered sets* of rows and columns of the matrix, and $\Gamma$ and its alphabet (usually, $\Gamma = \{0, 1\}$). A submatrix of $M$ is the restriction of $M$ to some subsets of rows and columns. A *division* $\mathcal{D}$ of $M$ consist of partitions $R, C$ of the rows and 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”.

For a tournament $T$ and a total order $<$ on $V(T)$, the adjacency matrix $A_{(T, <)}$ has $V(T)$ ordered by $<$ as rows and columns, and contains a “1” at position $(u, v)$ if and only if $u \to v$. This generalises to binary structures over any signature $\Sigma$, with $\{0, 1\}^{\Sigma}$ as alphabet.

### 2.3 Orders, Quasi-orders

A quasi-order $\leq$ is a reflexive and transitive binary relation. The associated equivalence relation is $x \sim y$ iff $x \leq y \land y \leq x$. The strict component of the quasi-order is $x \prec y$ iff $x \leq y$ and $y \not\leq x$. The quasi-order is *total* if for all $x, y$, either $x \leq y$ or $y \leq x$. An *interval* of a quasi-order $\leq$ is a set of the form $\{z \mid x \leq z \leq y\}$ for some $x, y$, called *endpoints*. An interval is a union of equivalence classes of $\sim$. Two subsets $X, Y$ are *overlapping* if there exist $x_1, x_2 \in X$ and $y_1, y_2 \in Y$ such that $x_1 \leq y_1$ and $x_2 \geq y_2$. Equivalently, $X, Y$ are non-overlapping iff there are disjoint intervals $I_X, I_Y$ such that $X \subseteq I_X$ and $Y \subseteq I_Y$.

### 2.4 Permutations

We denote by $\mathfrak{S}_n$ the group of permutations on $n$ elements. The permutation matrix $M_\sigma$ has 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 \le i, j < k$ contains a $k$-grid.
53:6 First Order Logic and Twin-Width in Tournaments

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 $\mathfrak{O}_\mathfrak{S}$ for the class of all finite bi-orders.

2.5 Twin-width

Twin-width, denoted e.g. tww(G), is a complexity parameter defined on graphs, and more
generally on binary structures. We refer the reader to [7] for the definition, based on
contraction sequences – it will not be used in this work. Instead, we rely on the following
characterisation 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'* 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.1** ([6, Theorem 2]). There are functions *f*, *g* such that for any graph (or binary structure) *G* and any order *<* on *V*(*G*),

if tww(G, <) ≥ 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 tww(G, <) ≥ 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.6 First-order logic

Recall from the introduction that we are interesting in FO MODEL CHECKING: given as input a structure *S* and a first-order formula *φ*, test if *S* |= *φ*. We consider the complexity of this problem parametrized by the size |*φ*|. In general, this problem is AW[*]-complete.

► **Theorem 2.2** ([12]). FO MODEL CHECKING is AW[*]-complete on the class of all graphs.

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

**Theorem 2.3** ([7, Theorem 1]). *Given a binary structure *S* on *n* vertices, a contraction sequence of width *k* for *S*, and a FO formula *φ*, one can test if *S* |= *φ* in time *f*(*k*, *φ*) · *n*.*

Interpretations are transformations of structures described 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$. If $S$ is a $\Sigma$-structure, the result $\Phi(S)$ is obtained by

choosing the same domain as S,

interpreting $R \in \Delta$ as $\{(v_1, \dots, v_r) \mid S \models \phi_R(v_1, \dots, v_r)\}$, the tuples satisfying $\phi_R$,

and finally taking the substructure induced by $\{v \mid S \models \phi_{dom}(v)\}$.

For instance, the square of a graph *G* has the same vertices as *G*, with an edge *xy* iff the
distance of *x* and *y* in *G* is at most 2. This is a FO interpretation with edges defined by

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

where $E(x, x)$ denotes adjacency. The domain formula just “true” since we do not wish to
delete vertices in this case. FO interpretations are closed under composition.
*Transductions* generalise interpretation with a non-deterministic coloring step. Let $\Sigma^+$ be the signature obtained by adding $r$ new unary relations $C_1, \dots, C_r$ to $\Sigma$. If $S$ is a $\Sigma$-structure, we denote by $S^+$ the set of $\Sigma^+$-structures obtained from $S$ by choosing an arbitrary interpretation of each $C_i$ as a subset of $V(S)$. Now a FO transduction $\Phi : \Sigma \to \Delta$ is described by the choice of $\Sigma^+$ augmenting $\Sigma$ with unary relations, and a FO interpretation $\Phi_I$ from $\Sigma^+$ from $\Delta$. The result of $\Phi$ is the set of $\Delta$-structures $\Phi(S) = \{\Phi_I(T) \mid T \in S^+\}$. That is, the interpretation of the unary relations $C_1, \dots, C_r$ on $S$ are chosen non-deterministically, and then $\Phi_I$ is applied.<fnref n="1" /> Like interpretations, transductions can be composed.
Given classes $C, D$ of structures, we say that *C interprets* (resp. *transduces*) $D$ if there is a FO interpretation (resp. transduction) $\Phi$ such that $\Phi(C) \supseteq D$. We furthermore say that *C efficiently interprets D* if there is also an algorithm which given as input $D \in D$, finds in polynomial time some $C \in C$ such that $\Phi(C) = D$. It is straightforward to show that this additional condition gives an FPT reduction for model checking.

**Lemma 2.4.** If *C* efficiently interprets *D*, then there is an FPT reduction from FO *MODEL CHECKING* on *D* to FO *MODEL CHECKING* on *C*.

Recall that $O_S$ denotes the class of bi-orders, which are encodings of permutations. The following is a folklore result, see e.g. [6, Lemma 10] for a very similar claim.

**Lemma 2.5.** The class $O_S$ of bi-orders efficiently interprets the class of all graphs.

Thus, using Lemma 2.4 and Theorem 2.2, FO *MODEL CHECKING* on $O_S$ is AW[*]-complete. FO transductions also preserve twin-width, up to some function.

**Theorem 2.6** ([7, Theorem 39]). If $S$ is a class of binary structures with bounded twin-width and $\Phi$ is a FO transduction defined on $S$, then $\Phi(S)$ also has bounded twin-width.

A class of structures $S$ is said to be *monadically NIP* if $S$ does not transduce the class of all graphs. Theorem 2.6 implies that classes with bounded twin-width are monadically NIP. The weaker notion of (non-monadically) NIP also exists, however Braunfeld and Laskowski recently proved that NIP and monadically NIP are equivalent for hereditary classes [10].

## 2.7 Enumeration

A class $S$ of graphs (or binary relational structures) is *small* if there exists $c$ such that $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. [20]. This was further generalised to classes of bounded twin-width by Bonnet et al.

**Theorem 2.7** ([5, Theorem 2.4]). *Classes of structures with bounded twin-width are small.*

# 3 Forbidden classes of tournaments

This section defines the three minimal classes $\mathcal{F}_=$, $\mathcal{F}_{\leq}$, and $\mathcal{F}_{\geq}$ of obstructions to twin-width in tournaments. Each of them corresponds to some encoding of the class of all permutations. For $R \in \{=, <, \geq\}$ 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)$.

<footnote n="1">¹ Additional operations such as duplication of vertices are often allowed in transductions, but these will not be needed in this work.</footnote>
<figure><img src="image_6.png" /><figcaption>■ **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$.</figcaption></figure>

Let $R \in \{=, \leq, \geq\}$, 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 = \{y_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 $iR\sigma^{-1}(j)$. See Figure 1 for an example.

Thus in $\mathcal{F}_-(\sigma)$ the edges oriented from $Y$ to $X$ form a matching which encodes $\sigma$. In $\mathcal{F}_-(\sigma)$ and $\mathcal{F}_+(\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}_+(\sigma)$, for any $i, j \in [n]$, we have

$$ (N^-(x_i) \cap Y) \subseteq (N^-(x_j) \cap Y) \iff i \leq j \quad (1) $$

$$ \text{and} \quad (N^-(y_i) \cap X) \subseteq (N^-(y_j) \cap X) \iff \sigma^{-1}(i) \leq \sigma^{-1}(j), \quad (2) $$

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

**Lemma 3.1.** For each $R \in \{=, \leq, \geq\}$, the class $\mathcal{F}_R$ efficiently interprets the class $\mathcal{O}_{\mathfrak{S}}$ of bi-orders. Precisely, there is an interpretation $\Phi_R$, and for any permutation $\sigma \in \mathfrak{S}_n$, $n \geq 2$, there is a $\sigma' \in \mathfrak{S}_{n+1}$ computable in polynomial time such that $\mathcal{O}_{\sigma} = \Phi_R(\mathcal{F}_R(\sigma'))$.

**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 $\geq$ or $\leq$, 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 \ge 2$.

■ If $R$ is $=, \leq, \geq$, define $\sigma' \in \mathfrak{S}_{n+1}$ by $\sigma'(n+1) = n+1$ and $\sigma'(i) = \sigma(i)$ for any $i \leq n$. Then, in $\mathcal{F}_=(\sigma')$, 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 $\leq$, define $\sigma'(1) = n+1$ and $\sigma'(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 $\geq$, we once again define $\sigma'(1) = n+1$ and $\sigma'(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'(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')$ 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 $O_\sigma$ in $\mathcal{F}_R(\sigma')$. $\quad$

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

**▶ Theorem 1.6.** For each $R \in \{=, \leq, \geq\}$, the class $\mathcal{F}_R$

1. has unbounded twin-width;

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

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

4. efficiently interprets the class of all graphs;

5. and has AW[*]-hard FO model checking problem.

**Proof.** Item 4 is straightforward by Lemmas 2.5 and 3.1, since efficient interpretations can be composed. By Lemma 2.4 and Theorem 2.2, 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 if there are automorphisms). Furthermore, each of Items 3 and 4 implies Item 1, by Theorem 2.7 and Theorem 2.6 respectively. Thus it only remains to prove Item 3.

By Lemma 3.1, for any permutation $\sigma \in \mathfrak{S}_n$ there is some $\mathcal{F}_R(\sigma')$ on $2n+2$ vertices such that $\Phi_R(\mathcal{F}_R(\sigma')) = \sigma$, where $\Phi_R$ is a fixed 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, the arguments of Lemma 3.1, it is easy to show that these $\mathcal{F}_R(\sigma')$ have no non-trivial automorphism. Thus, there are exactly $(2n+2)!$ distinct labellings of $\mathcal{F}_R(\sigma')$ 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. $\quad$

Thus the classes $\mathcal{F}_=, \mathcal{F}\leq, \mathcal{F}\geq$ 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><img src="image_7.png" /><figcaption>Figure 2 A binary search tree in a tournament. The direction of omitted edges is not constrained.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Figure 3 Example of construction of the quasi-order $\leq_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 $\leq_C^-$, the direction of all edges would be reversed.</figcaption></figure>

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* $\leq_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 \leq 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 $\leq_C^+$, and the classes are ordered as

$$B_1 \leq_C^+ c_1 \leq_C^+ B_2 \leq_C^+ c_2 \leq_C^+ \dots B_k \leq_C^+ c_k \leq_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 $\leq_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 \leq i} N^-(c_j)$ and $B_i = A_{i-1} \cap N^+(c_i)$. The rest of the definition is the same.

**Lemma 4.2.** *There is a first-order transduction $\Phi$ which non-deterministically computes any chain quasi-order. That is, for any tournament $T$ and chain quasi-order $\leq_C^o$, $(T, \leq_C^o) \in \Phi(T)$.*

**Proof.** The transduction first guesses $C$ and $o$, and obtains the order within $C$ from the edges of $T$. It is then simple to express the definition of $\leq_C^o$ in first-order logic. $\quad$

We now prove our main technical lemma on BSTs, which shows that BST orders can to some extent be approximated by chain quasi-orders.
**► Lemma 4.3.** Let $T$ be a tournament and $S$ be a BST with order $<_S$. There is a function $f(k) = 2^{O(k)}$ independent of $T$ and $S$ such that 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}' \subset \mathcal{P}$ such that $|\mathcal{P}'| \ge k$ and such that the intervals of $\mathcal{P}'$ are non-overlapping for $\le_C^o$.

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

**Proof.** Let $T$ be a tournament, $S$ a BST of $T$ and $<_S$ the corresponding order. Let $\mathcal{P}$ be a family 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

$$2w_{i+1} + 1 \ge w_i. \qquad (3)$$

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 \le i \le j \le p$, let

$$L_{i,j} \stackrel{\text{def}}{=} \bigcup_{\substack{i \le l < j \\ b_l \in L}} \{b_l\} \cup D_l, \quad \text{and} \quad R_{i,j} \stackrel{\text{def}}{=} \bigcup_{\substack{i \le l < j \\ b_l \in R}} \{b_l\} \cup D_l.$$

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.4.** 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 $l < j$ and $b_l \in L$, then $b_l <_S S_j$, and in turn $D_l <_S b_l$. This proves $L_{i,j} <_S S_j$, and symmetrically $S_j <_S R_{i,j}$. ◁

**► Claim 4.5.** For $0 \le i < j \le p$, if $w_i \ge 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.** At least three parts of $\mathcal{P}$ 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 by Claim 4.4 implies $P \subset L_{i,j}$ or $P \subset R_{i,j}$. ◁

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

$$2w_{i_{l+1}} + 3 \ge w_{i_l}. \qquad (4)$$

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

Define $L'_l = L_{i_{l-1}, i_l}$, and similarly $R'_l = R_{i_{l-1}, i_l}$, see Figure 4. By Claim 4.5, for any $l \in [2k]$, either $L'_l$ or $R'_l$ contains a part of $\mathcal{P}$. Thus, either there are at least $k$ distinct $L'_l$ containing a part of $\mathcal{P}$, or there are at least $k$ distinct $R'_l$ containing a part of $\mathcal{P}$. Assume the former case without loss of generality. We will now forget the vertices which are not in $L$.

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
<figure><img src="image_9.png" /><figcaption>Figure 4 Sketch of the proof of Lemma 4.3. 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'_\ell$ and $R'_\ell$; the initial family (here partition) $\mathcal{P}$, with the parts contained in some $L'_\ell$ or $R'_\ell$ highlighted; the final family $\mathcal{P}'$, obtained by selecting a part of $\mathcal{P}$ inside each possible $L'_\ell$.</figcaption></figure>

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'_\ell$, select a part of $\mathcal{P}$ included in $L'_\ell$ if any, and define $\mathcal{P}'$ as the collection of selected parts. Thus $\mathcal{P}' \subset \mathcal{P}$, and we know from the choice of the family $\{L'_\ell\}_{\ell \in [2k]}$ that $|\mathcal{P}'| \ge k$. Furthermore, if $X \neq Y$ are parts of $\mathcal{P}'$, there are $s \neq t$ such that $X \subseteq L'_s$ and $Y \subseteq L'_t$. Since each $L'_\ell$ is an interval of $(L, \preceq_C^+)$, this implies that $X$ and $Y$ are non-overlapping for $\preceq_C^+$. Thus $\mathcal{P}'$ 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, one can in linear time choose the branch $B$, the indices $i_\ell$, the better side $L$ or $R$, and finally compute $C$ and $\mathcal{P}'$. $\llcorner$

5 BST orders witness twin-width

In this section, we prove Lemma 1.4, i.e. that BST orders are good for twin-width. The proof heavily uses model-theoretic results from [6]. Due to space constraints, the combinatorial proof of the stronger result Theorem 1.5 is omitted, see the extended version of this paper [16].

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, Lemma 1.4 can be restated as
**► Lemma 5.1.** If $\mathcal{T}$ is a hereditary class of tournaments with bounded twin-width, then $\mathcal{T}^{\text{BST}}$ also has bounded twin-width.

**Proof.** Fix $\mathcal{T}$ a class of tournaments with twin-width at most $t$, and assume by contradiction that $\mathcal{T}^{\text{BST}}$ has unbounded twin-width. Then by Theorem 2.1, for any $k$ there is some $(T, <_S) \in \mathcal{T}^{\text{BST}}$ whose adjacency matrix contains a rank-$k$ division. That is, there are partitions $A_1, \dots, A_k$ and $B_1, \dots, B_k$ of $V(T)$ into intervals of $<_S$ such that the adjacency matrix of any $A_i$ versus $B_j$ is $k$-diverse.

If $k$ is chosen to be $k = f(\ell)$ where $f$ is the function of Lemma 4.3, then we obtain two chain quasi-orders $\leq_A, \leq_B$ in $T$, and subfamilies $A_{i_1}, \dots, A_{i_\ell}$ and $B_{j_1}, \dots, B_{j_\ell}$ which are non-overlapping for $\leq_A$ and $\leq_B$ respectively. We can in fact assume that $A_{i_1}, \dots, A_{i_\ell}$ are disjoint intervals of $\leq_A$, by replacing them by their closure

$$ \bar{A}_{i_t} \stackrel{\text{def}}{=} \{x \mid \exists y, z \in A_{i_t}, y \leq_A x \leq_A z\} $$

Let $T^+$ be the structure $T$ augmented by the quasi-orders $\leq_A$ and $\leq_B$. In $T^+$, each interval $\bar{A}_{i_t}$ can be described by its two endpoints. Using the terminology of [6, section 9], this means that $\bar{A}_{i_1}, \dots, \bar{A}_{i_\ell}$ is a definable disjoint family. Naturally, the same holds for $\bar{B}_{j_1}, \dots, \bar{B}_{j_\ell}$. Finally, $A_i$ versus $B_j$ being $k$-diverse is a very special case of the model-theoretic notion of $A$ having $k$ distinct $\Delta$-types over $B$, when $\Delta$ consists only of the formula "being adjacent".

Let $\mathcal{T}^+$ denote the class of tournaments in $\mathcal{T}$ augmented by any two chain quasi-orders. We have just proved that for arbitrary large $k, \ell$, there are structures $T^+ \in \mathcal{T}^+$ containing two families of $\ell$ disjoint subsets $(\bar{A}_{i_t})_{t \in [\ell]}$ and $(\bar{B}_{j_t})_{t \in [\ell]}$ definable by a fixed formula, and such that each $\bar{A}_{i_t}$ has $k$ distinct $\Delta$-types over each $\bar{B}_{j_t}$. That is, the class $\mathcal{T}^+$ is unrestrained in the sense of [6, Definition 50]. By [6, Theorem 54], it follows that $\mathcal{T}^+$ is not monadically NIP, hence has unbounded twin-width. But it follows from Lemma 4.2 that $\mathcal{T}^+$ is obtained from $\mathcal{T}$ by a first-order transduction, contradicting that $\mathcal{T}$ has bounded twin-width. ◀

References

1. Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent information: Ranking and clustering. *J. ACM*, 55(5), November 2008. doi:10.1145/1411509.1411513.

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. doi:10.1016/j.jctb.2005.09.003.

3. Mikołaj Bojańczyk. personal communication. July 2022.

4. É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. doi:10.48550/arXiv.2204.00722.

5. É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. doi:10.1137/1.9781611976465.118.

6. É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. arXiv:2102.03117.

7. É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. doi:10.1145/3486655.

8. Édouard Bonnet, Jaroslav Nesetril, Patrice Ossona de Mendez, Sebastian Siebertz, and Stéphan Thomassé. Twin-width and permutations. *CoRR*, abs/2102.06880, 2021. arXiv:2102.06880.
53:14 First Order Logic and Twin-Width in Tournaments

9 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. doi:10.1016/j.ejc.2009.03.027.

10 Samuel Braunfeld and Michael C Laskowski. Existential characterizations of monadic nip. *arXiv preprint*, 2022. doi:10.48550/arXiv.2209.05120.

11 Maria Chudnovsky, Alexandra Fradkin, and Paul Seymour. Tournament immersion and cutwidth. *J. Comb. Theory, Ser. B*, 102:93–101, January 2012. doi:10.1016/j.jctb.2011.05.001.

12 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.

13 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. doi: 10.1016/j.jctb.2019.01.006.

14 Alexandra Fradkin and Paul Seymour. Tournament pathwidth and topological containment. *Journal of Combinatorial Theory, Series B*, 103(3):374–384, 2013. doi:10.1016/j.jctb.2013.03.001.

15 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), July 2020. doi:10.1145/3383206.

16 Colin Geniet and Stéphan Thomassé. First order logic and twin-width in tournaments and dense oriented graphs, 2022. arXiv:2207.07683.

17 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. doi:10.1137/1.9781611973402.7.

18 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. doi:10.4230/LIPIcs.STACS.2016.49.

19 Adam Marcus and Gábor Tardos. Excluded permutation matrices and the Stanley-Wilf conjecture. *J. Comb. Theory, Ser. A*, 107(1):153–160, 2004. doi:10.1016/j.jcta.2004.04.002.

20 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. doi: 10.1016/j.jctb.2006.01.006.

21 Michał Pilipczuk. *Tournaments and Optimality: New Results in Parameterized Complexity*. PhD thesis, University of Bergen, August 2013. URL: https://bora.uib.no/bora-xmlui/bitstream/handle/1956/7650/dr-thesis-2013-Michal-Pilipczuk.pdf?sequence=1.