case, he chooses a vertex $a$ in $G$. Let $A_{i}=A_{i-1}\cup\\{a\\}$ and
$B_{i}=B_{i-1}\cup\\{b\\}$. If no isomorphism $\pi_{i}:G[A_{i}]\rightarrow
G[B_{i}]$ extending $\pi_{i-1}$ exists such that $\pi(a)=b$, then Spoiler wins
the game. Otherwise, the game continues until $i=q$ (notice that $\pi_{i}$ is
uniquely determined by $\pi_{i-1}$ and the vertices $a$ and $b$). If $i$
reaches $q$ and $\pi_{q}$ is an isomorphism from $G[A_{q}]$ to $H[B_{q}]$ then
Duplicator wins the game.

If Duplicator has a winning strategy for $q$ then we write $G\equiv^{q}H$, and
we say that $G$ and $H$ are _$q$ -back-and-forth equivalent_. The meaning of
the $q$-back-and-forth equivalence is clarified by the following classical
result.

######  Theorem 43 ([Lib04, Theorem 3.5]).

Two graphs (and more generally two possibly infinite relational structures)
are $q$-back and forth equivalent if and only if they satisfy the same first
order sentences of quantifier rank $q$.

Let $\mathcal{U}=\\{M_{1},\dots,M_{p}\\}$ be a finite set of unary relations.
A _compressed_ $\mathcal{U}$-colored caterpillar is a pair $(P,f)$, where $P$
is a $\mathcal{U}$-colored path and
$f:V(P)\times\mathcal{P}([p])\rightarrow\mathbb{N}$. The $\mathcal{U}$-colored
caterpillar represented by $(P,f)$ is the caterpillar $\Upsilon(P;f)$ obtained
by $P$ by adding at each vertex $v$ of $P$, for each $I\subseteq[p]$, $f(v,I)$
vertices that belong exactly to the relations $M_{i}$ with $i\in I$ (see
Figure 16); these vertices are called the _$I$ -children_ of $v$ in
$\Upsilon(P,f)$. We further denote by $L_{P,f}(v,I)$ the set of all the
$I$-children of $v$ in $\Upsilon(P,f)$.

Figure 16: A compressed $\\{M_{1},M_{2}\\}$-colored caterpillar and the
caterpillar $G$ it represents. (White vertices are in no unary relations,
green ones are in $M_{1}$, red ones are in $M_{2}$ and bicolored ones are both
in $M_{1}$ and $M_{2}$.)

######  Fact 44.

Let $(P,f)$ be a compressed caterpillar, and let $H=\Upsilon(P,f)$. Then, for
every $v\in V(P)$ and every $I\subseteq[p]$, every permutation of
$L_{P,f}(v,I)$ defines an automorphism of $H$.

######  Corollary 45.

Let $\mathcal{U}=\\{M_{1},\dots,M_{p}\\}$ be a set of unary relations, let
$\mathsf{I}$ be an interpretation of graphs in $\mathcal{U}$-colored graphs,
let $(P,f)$ be a compressed caterpillar, and let $H=\Upsilon(P,f)$.

Then, for every $v\in V(P)$ and every $I\subseteq[p]$, the vertices of
$L_{P,f}(v,I)$ are clones in $\mathsf{I}(H)$. In particular, $L_{P,f}(v,I)$ is
either an independent set or a clique of $\mathsf{I}(H)$.

######  Proof 17.1.

According to Fact 44, every permutation of f $L_{P,f}(v,I)$ defines an
automorphism of $H$, hence an automorphism of $\mathsf{I}(H)$.

Let $\mathcal{U}=\\{M_{1},\dots,M_{p}\\}$ be a set of unary relations.

######  Proposition 46.

Let $\Delta$ be an integer. The class of $\mathcal{U}$-colored caterpillars
with maximum degree $\Delta$ is a non-copying transduction of the class
$\mathscr{P}$ of paths.

######  Proof 17.2.

Let $\mathcal{U}^{\prime}=\mathcal{U}\cup\\{S,T\\}$, where $S$ and $T$ are two
unary symbols (not in $\mathcal{U}$). Let $G$ be a $\mathcal{U}$-colored
caterpillar, and let $(P,f)$ be a compressed caterpillar with
$\Upsilon(P,f)=G$. Let $v_{1},\dots,v_{n}$ be the vertices of $P$ (in order).
For each $i\in[n]$ we associate with $v_{i}$ a path
$\mathcal{U}^{\prime}$-colored path $Q_{i}$ consisting of a vertex marked $S$,
a vertex marked the same way as $v_{i}$, for each $I\subseteq[p]$,
$f(v_{i},I)$ vertices marked by all the $M_{i}$ with $i\in I$, then a vertex
marked $T$. We consider the interpretation $\mathsf{I}=(\neg S(x)\vee\neg
T(x),\eta(x,y)$, where $\eta(x,y)$ expresses that $x$ and $y$ are at distance
at most $\Delta+2$, and

  * •

either one of $x$ and $y$ is adjacent to a vertex marked $S$ and no vertex
between $x$ and $y$ is marked $S$,

  * •

or both $x$ and $y$ are adjacent to a vertex marked $S$ and there is only one
vertex marked $S$ between $x$ and $y$.

Let $Q$ be the path obtained by concatenating the paths $Q_{1},\dots,Q_{n}$.
Then, $\mathsf{I}(Q)=G$ (cf Figure 17). It follows that the non-copying
transduction defined by $\mathsf{I}$ witnesses that the class of
$\mathcal{U}$-colored caterpillars with maximum degree $\Delta$ is a non-
copying transduction of $\mathscr{P}$.

Figure 17: Encoding a caterpillar with bounded degree in a path. Mark $S$ is
blue, mark $T$ is orange.

Let $(P,f_{1})$ and $(P,f_{2})$ be two compressed caterpillars based on the
same $\mathcal{U}$-colored path such that
$\min(f_{1}(v,I),q)=\min(f_{2}(v,I),q)$ and $f_{1}(v,I)\leq f_{2}(v,I)$ for
all $v\in V(P)$ and all $I\subseteq[p]$, and let $H_{1}=\Upsilon(P,f_{1})$ and
$H_{2}=\Upsilon(P,f_{1})$, where $H_{1}$ is naturally identified with an
induced subgraph of $H_{2}$.

######  Lemma 47.

For every formula $\varphi(x,y)$ with quantifier rank at most $q-2$ and for
every two vertices $u,v$ in $H_{1}$ we have

$H_{1}\models\varphi(u,v)\qquad\iff\qquad H_{2}\models\varphi(u,v).$

######  Proof 17.3.

This follows from a standard argument based on an Ehrenfeucht-Fraïssé game.

######  Corollary 48.

For every interpretation $\mathsf{I}=(M_{1}(x),\eta(x,y))$ where $\eta$ has
quantifier rank at most $q-2$, the graph $\mathsf{I}(H_{1})$ is an induced
subgraph of $\mathsf{I}(H_{2})$.

######  Lemma 49.

Let $\mathcal{U}=\\{M_{1},\dots,M_{p}\\}$ be a set of unary relations, let
$\mathsf{I}=(M_{1}(x),\eta(x,y)$ be an interpretation of graphs in
$\mathcal{U}$-colored graphs, let $q$ be at least the quantifier rank of
$\eta$ plus two, and let $G=\Upsilon(P,f)$. Define the function
$\widehat{f}:V(P)\times\mathcal{P}([p])\rightarrow\\{0,\dots,q\\}$ by
$\widehat{f}(v,I)=\min(f(v,I),q)$, and let
$\widehat{G}=\Upsilon(P,\widehat{f})$.

Then, the graph $\mathsf{I}(G)$ is obtained from $\mathsf{I}(\widehat{G})$ as
follows: for each $v\in V(P)$ and each $I\subseteq[p]$ with $1\in 1$ and
$f(v,I)>q$, select arbitrarily a vertex $\ell(v,I)\in L_{P,\widehat{f}}(v,I)$
and blow the vertex $\ell(v,I)$ in $\mathsf{I}(\widehat{G})$ into a clique or
an independent set of size $f(v,I)-\widehat{f}(v,I)+1$ (depending on whether
$L_{P,\widehat{f}}(v,I)$ is, in $\mathsf{I}(\widehat{G})$, a clique or an
independent set).

######  Proof 17.4.

We prove the statement of the lemma by induction over

$W(f):=\sum_{v\in V(P)}\sum_{I\subseteq[p]}|f(v,I)-\widehat{f}(v,I)|.$

If $W(f)=0$, then $f=\widehat{f}$, $\widehat{G}=G$ and
$\mathsf{I}(\widehat{G})=\mathsf{I}(G)$. Hence, the base case obviously holds.
Assume that the statement holds for $W(f)=k\geq 0$ and let $f$ be such that
$W(f)=k+1$. Then, there exists a vertex $v_{0}\in V(P)$ and a subset
$I_{0}\subseteq[p]$ with $f(v_{0},I_{0})>0$. Let
$f(v,I)=f(v,I)-\delta_{v,v_{0}}\cdot\delta_{I,I_{0}}$, where $\delta$ is
Kronecker’s symbol. Note that $G^{\prime}=G-v_{0}$ is the
$\mathcal{U}$-colored caterpillar represented by $(P,f^{\prime})$. If $1\notin
I$, it directly follows from Corollary 48 that
$\mathsf{I}(G^{\prime})=\mathsf{I}(G)$. Thus, the statement of the theorem
holds by the induction hypothesis. Otherwise, by Corollary 48, we have
$\mathsf{I}(G^{\prime})=\mathsf{I}(G)-v_{0}$. By construction, there exists a
vertex $u_{0}\in V(P)$ such that $v_{0}$ is an $I$-child of $u_{0}$ in $G$. As
the set of $I_{0}$-children of $u_{0}$ in $G^{\prime}$ has size at least two
and are clones in $\mathsf{I}(G^{\prime})$, there is no choice about how to
define the adjacencies of $v_{0}$, and the statement of the lemma holds.

######  Theorem 50.

Let $\mathscr{C}$ be a (non-copying) transduction of the class of all
caterpillars. If the class $\mathscr{C}$ has bounded maximum degree, then
$\mathscr{C}$ is a transduction of the class of all paths. Otherwise, there
exists a class $\mathscr{C}^{\prime}$ with bounded degree that is a
transduction of the class of all caterpillars, such that the graphs in
$\mathscr{C}$ are obtained from graphs in $\mathscr{C}^{\prime}$ by blowing
each vertex either into an independent set or into a complete graph (of
arbitrary size).

######  Proof 17.5.

Let $\mathscr{C}$ be a $\mathsf{T}$-transduction of the hereditary closure
$\mathscr{D}$ of the class of all caterpillars444as the hereditary closure of
a class is non-copying transduction equivalent to it, we can consider the
hereditary closure of the class of all the caterpillars instead of the class
of all the caterpillars., where $\mathsf{T}$ is non-copying. Let $\mathsf{I}$
be the transduction defining $\mathsf{T}$. According to Lemma 6, we may assume
that $\mathsf{I}=(M_{1}(x),\eta(x,y))$, where $M_{1}$ is a unary relation and
$\eta$ is a local formula. Let $q$ be the quantifier-rank of $\eta$. Let
$\mathscr{C}^{\prime}$ be the class containing, for each graph
$G\in\mathscr{C}$, the induced subgraph of $G$ obtained by deleting all the
isolated vertices. Note that
$\mathscr{C}^{\prime}\subseteq\mathsf{T}(\mathscr{D})$.

Assume that $\mathscr{C}$ has bounded degree, and let $\Delta$ be the maximum
degree of the graphs in $\mathscr{C}$. Let $G\in\mathscr{C}^{\prime}$ and let
$H$ be a graph with a minimum number of vertices such that $H\in\mathscr{D}$
and $G\in\mathsf{T}(H)$. As $G\in\mathsf{T}(H)$, there exists a unary
expansion $H^{+}$ of $H$ with $G=\mathsf{I}(H^{+})$. Let $(P,f)$ be a
compressed $\mathcal{U}$-colored caterpillar representing $H^{+}$, let
$\widehat{f}$ be defined from $f$ as in Lemma 49 and let $\widehat{H}^{+}$ be
the $\mathcal{U}$-colored caterpillar represented by $(P,\widehat{f})$.
According to Lemma 49 we get that $\mathsf{I}(G)$ contains a subset $X$ of
clones of $G=\mathsf{I}(H^{+})$ of size $\max_{v\in V(P)}\max_{1\in
I\subseteq[p]}f(v,I)$. As $G$ contains no isolated vertex, any neighbor of
some $v\in X$ has degree at least $|X|-1$. Hence, $\max_{v\in V(P)}\max_{1\in
I\subseteq[p]}f(v,I)\leq\Delta+1$. It follows that if we choose
$q\geq\Delta+1$, we have $\mathsf{I}(\widehat{H}^{+})=\mathsf{I}(H^{+})=G$.
Note that $\widehat{H}^{+}$ is a $\mathcal{U}$-colored caterpillar with
maximum degree at most $\Delta^{\prime}=2^{p}(\Delta+1)+2$. It follows that
$\mathscr{C}^{\prime}$ is a non-copying transduction of the class
$\mathscr{D}^{\prime}$ of all the caterpillars with maximum degree
$\Delta^{\prime}$. Hence, according to Proposition 46, the class
$\mathscr{D}^{\prime}$ is a non-copying transduction of the class
$\mathscr{P}$ of all paths. As $\mathscr{E}$ is also a non-copying
transduction of $\mathscr{P}$ (consider the transduction defined by the
interpretation $(\top,\bot)$ that delete all the edges) and as
$\mathscr{D}\subseteq\mathscr{D}^{\prime}+\mathscr{E}$ (every graph in
$\mathscr{D}$ is the disjoint union of a graph in $\mathscr{D}^{\prime}$ and
isolated vertices), we deduce from Fact 25 that $\mathscr{D}$ is a non-copying
transduction of $\mathscr{P}$.

We now consider the case where $\mathscr{C}$ does not have bounded degree.
Then, the conclusion directly follows from Lemma 49 where we choose $q$ to be
the quantifier rank of $\eta$ plus two.

###  18 A distributive lattice among some low classes

Recall that a lattice is a partially ordered set in which every pair of
elements has a unique supremum (also called a least upper bound or join) and a
unique infimum (also called a greatest lower bound or meet). We shall see in
Theorem 73 that the transduction quasi-order is not a lattice. However, we now
give some non-trivial examples of the existence of the greatest lower bound of
two incomparable classes.

The class of all cubic trees is the greatest lower bound of the class of all
trees and of the class of all cubic graphs.

######  Proof 18.1.

That the class of all cubic trees is a lower bound of the class of all trees
and the class of all cubic graphs is obvious, as it is included in both
classes.

Let $\mathscr{C}$ be a lower bound of the class of all trees and the class of
all cubic graphs. Being a transduction of the class of all cubic graphs,
$\mathscr{C}$ is a perturbation of a class $\mathscr{D}$ with bounded degree
(by Proposition 40). Trees have cliquewidth $3$ and the property of a class of
having bounded cliquewidth is preserved by transduction (see [Col07], for
instance). Thus, being a transduction of the class of all trees, the class
$\mathscr{D}$ has bounded cliquewidth. As the class $\mathscr{D}$ is also
weakly sparse, it has bounded treewidth [GW00a]. Thus, $\mathscr{C}$ is a
perturbation of a class with both bounded degree and bounded treewidth. Hence,
according to Proposition 42, $\mathscr{C}$ is a transduction of the class of
all cubic trees.

Also, we have: The class of all paths is the greatest lower bound of the class
of all caterpillars and of the class of all cubic graphs.

######  Proof 18.2.

That the class of all paths is a lower bound of the class of all caterpillars
and of the class of all cubic graphs is obvious, as it is included in both
classes.

Let $\mathscr{C}$ be a lower bound of the class of all caterpillars and of the
class of all cubic graphs. Being a transduction of the class of all cubic
graphs, $\mathscr{C}$ is a perturbation of a class $\mathscr{D}$ with bounded
degree (by Proposition 40). Note that it follows that $\mathscr{D}$ is a
perturbation of $\mathscr{C}$. As $\mathscr{C}$ is a transduction of the class
of all caterpillars, so is $\mathscr{D}$. According to Theorem 50,
$\mathscr{D}$ (and hence $\mathscr{C}$) is a non-copying transduction of the
class of all paths.

Note that in the above, the class of cubic graphs can be replaced by any class
of bounded degree transducing all paths, for instance the class of all cubic
trees or the class of all grids.

The lattice structure shown in Figure 18 is effectively present in the quasi-
order, in the sense that the meets and joins shown in the figure are actually
meets and joins in the general quasi-order.

|
---|---
$\textstyle{\text{\scriptsize tree}\cup\text{\scriptsize
cubic}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$tree$\textstyle{\text{\scriptsize
caterpillar}\cup\text{\scriptsize
cubic}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\text{\scriptsize
caterpillar}\cup\text{\scriptsize cubic
tree}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\text{\scriptsize
star forest}\cup\text{\scriptsize
cubic}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$caterpillar$\textstyle{\text{\scriptsize
star forest}\cup\text{\scriptsize cubic
tree}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$cubic$\textstyle{\text{\scriptsize
star forest}\cup\text{\scriptsize
path}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$cubic
treestar forestpathedgeless Figure 18: The lattice structure induced by the
classes of all trees, by the class of all caterpillars (i.e. the class of all
connected graphs with pathwidth $1$ [PT99]), by the class of all star forests,
by the class of edgeless graphs, by the class of all paths, by the class of
all cubic trees, and by the class of all cubic graphs.

##  Part IV Applications

Our applications are divided into three parts. In structural graph theory, it
is common to weaken properties by not insisting that they hold globally but
only at every local scale, as in [Gro03]. As might be expected, this interacts
well with the locality of first-order logic, and we give some applications in
the first section. The next section is concerned with the minimum and maximum
classes for properties $\Pi$ of the transduction quasi-order, which serve as
canonical obstructions for $\Pi$ or capture all the complexity of $\Pi$,
respectively. This leads to transduction dualities, which are a framework for
dichotomy statements akin to the Grid Minor Theorem [RS86] stating that a
class has bounded tree-width if and only if it does not contain arbitrarily
large grids as minors (and which can be seen as an MSO-transduction duality
for weakly sparse classes between the class of trees and the class of grids).
Finally, we turn to dense analogues, which uses the transduction quasi-order
to generalize various properties of weakly sparse classes to general
hereditary classes.

###  19 Local properties

We begin with yet another application of the local normal form, showing that
all transductions of certain graph classes that are locally well-behaved can
be obtained by perturbations of such classes. For a transduction downset $\Pi$
(a class property $\Pi$ is a _transduction downset_ if it is preserved by
transductions), the set of classes of graphs that are _locally_ $\Pi$, denoted
$\mbox{\sf loc-}\Pi$, is the set of all classes $\mathscr{C}$ such that for
every integer $d$, the class $\mathcal{B}_{d}^{\mathscr{C}}$ of all balls of
radius $d$ of graphs in $\mathscr{C}$ belongs to $\Pi$, and we denote by
$\overline{\mbox{\sf loc-}\Pi}$ the set of all the classes that are
perturbations of a class in $\mbox{\sf loc-}\Pi$.

######  Theorem 51.

Let $\Pi$ be a transduction downset. Then $\overline{\mbox{\sf loc-}\Pi}$ is a
transduction downset.

######  Proof 19.1.

Let $\mathscr{C}\in\overline{\mbox{\sf loc-}\Pi}$ and let $\mathsf{T}$ be a
transduction. By definition, there exists a perturbation $\mathsf{P}_{0}$ and
a class $\mathscr{C}^{\prime}\in\mbox{\sf loc-}\Pi$ with
$\mathscr{C}\subseteq\mathsf{P}_{0}(\mathscr{C}^{\prime})$. According to
Theorem 8, the transduction $\mathsf{T}\circ\mathsf{P}_{0}$ is subsumed by the
composition $\mathsf{P}\circ\mathsf{T}_{\rm imm}\circ\mathsf{C}$ of a copying
transduction, an immersive transduction, and a perturbation. Consider
$H\in\mathsf{T}_{\rm imm}\circ\mathsf{C}(G)$, for $G\in\mathscr{C}^{\prime}$.
For every integer $d$, there exists an integer $d^{\prime}$ such that for
every vertex $v\in V(H)$ there is a vertex $v^{\prime}\in V(G)$ (the
projection of $v$) with the property that $B_{d}(H,v)$ is an induced subgraph
of $\mathsf{T}_{\rm imm}\circ\mathsf{C}(B_{d^{\prime}}(G,v^{\prime}))$, thus
in a fixed transduction of $B_{d^{\prime}}(G,v^{\prime})$. As
$\mathscr{C}^{\prime}$ is locally $\Pi$, the class
$\mathscr{C}_{d^{\prime}}^{\prime}=\\{B_{d^{\prime}}(G,v^{\prime})\colon
G\in\mathscr{C}^{\prime},v^{\prime}\in V(G)\\}$ belongs to $\Pi$. As $\Pi$ is
a transduction downset, the class $\\{B_{d}(H,v)\colon H\in\mathsf{T}_{\rm
imm}\circ\mathsf{C}(\mathscr{C}^{\prime})\\}$ is also in $\Pi$. As this holds
for every integer $d$, $\mathsf{T}_{\rm
imm}\circ\mathsf{C}(\mathscr{C}^{\prime})\in\mbox{\sf loc-}\Pi$. Hence,
$\mathsf{T}(\mathscr{C})\in\overline{\mbox{\sf loc-}\Pi}$.

Since having bounded linear cliquewidth, having bounded cliquewidth, and
having bounded twin-width are transduction downsets (See [Col07, BKTW20]), we
have the following corollaries.

######  Corollary 52.

Every transduction of (a perturbation of) a class with locally bounded linear
cliquewidth is a perturbation of a class with locally bounded linear
cliquewidth.

######  Corollary 53.

Every transduction of (a perturbation of) a class with locally bounded
cliquewidth is a perturbation of a class with locally bounded cliquewidth.

######  Corollary 54.

Every transduction of (a perturbation of) a class with locally bounded twin-
width is a perturbation of a class with locally bounded twin-width.

Assume that a transduction downset $\Pi$ is included in a set of classes
$\Pi^{\prime}$. Then it directly follows from Theorem 51 that every
transduction of a class that is locally $\Pi$ is a perturbation of a class
that is locally $\Pi^{\prime}$. Recall that a class is _$\chi$ -bounded_ if
there is a function $f$ such that every graph $G\in\mathscr{C}$ with clique
number $\omega$ has chromatic number at most $f(\omega)$. It is known that
every transduction of a class with bounded expansion is $\chi$-bounded
[NOdMP+21, Corollary 4.1]. Hence, we have

######  Corollary 55.

Every transduction of a locally bounded expansion class is a perturbation of a
locally $\chi$-bounded class.

We now turn to the local versions of some the most important model-theoretic
properties in the quasi-order, namely (monadic) stability and (monadic)
dependence. Recall (section 2.3) that dependence and stability correspond to
the impossibility to define arbitrarily large _power set graphs_ (that is,
bipartite graphs with vertex set $[n]\cup 2^{[n]}$ where $i$ is adjacent to
$I$ whenever $i\in I$) and arbitrarily large half-graphs (see Section 2.3),
respectively. Further model-theoretic dividing lines may be derived by
considering monadic expansions, i.e. expansions by unary predicates. We say
that a class $\mathscr{C}^{+}$ of colored graphs is a _monadic expansion_ of a
class $\mathscr{C}$ of graphs if each colored graph in $\mathscr{C}^{+}$ is a
monadic expansion of some graph in $\mathscr{C}$.

  * •

A class $\mathscr{C}$ of graphs is _monadically dependent_ if every monadic
expansion of $\mathscr{C}$ is dependent;

  * •

a class $\mathscr{C}$ of graphs is _monadically stable_ if every monadic
expansion of $\mathscr{C}$ is stable.

These dividing lines are characterized by the impossibility to transduce some
classes.

######  Theorem 56 ([BS85]).

A class $\mathscr{C}$ is _monadically dependent_ (or _monadically NIP_) if the
class of all graphs is not a transduction of $\mathscr{C}$; it is _monadically
stable_ if the class of all half-graphs is not a transduction of
$\mathscr{C}$.

The distinction between the classical versions of these properties and their
monadic variants is actually not so important in the setting of hereditary
classes, as witnessed by the following theorem.

######  Theorem 57 ([BL22a]).

Let $\mathscr{C}$ be a hereditary class of graphs. Then,

  * •

$\mathscr{C}$ is monadically dependent iff $\mathscr{C}$ is dependent;

  * •

$\mathscr{C}$ is monadically stable iff $\mathscr{C}$ is stable.

We also introduce monadically straight classes. Recall the definitions of
trivially perfect graphs and forest orders from section 1.1.

A class $\mathscr{C}$ is monadically straight if the class of trivially
perfect graphs (equivalently, the class of forest orders) is not transducible
from $\mathscr{C}$.

We believe that monadic straightness could well be an important dividing line
in the transduction quasi-order (and maybe from a general model-theoretic
point of view).

As above, we may consider the local versions of these properties, which we
will prove to be equivalent to their non-local versions.

######  Theorem 58.

For a class $\mathscr{C}$ of graphs we have the following equivalences:

  1. 1.

$\mathscr{C}$ is locally monadically dependent if and only if $\mathscr{C}$ is
monadically dependent;

  2. 2.

$\mathscr{C}$ is locally monadically straight if and only if $\mathscr{C}$ is
monadically straight;

  3. 3.

$\mathscr{C}$ is locally monadically stable if and only if $\mathscr{C}$ is
monadically stable.

######  Proof 19.2.

The proof will follow from the following claim.

######  Claim 59.

Let $\mathscr{C}$ be a class such that the class
$\mathscr{C}^{\prime}=\\{n(G\operatorname{+}K_{1})\mid
n\in\mathbb{N},G\in\mathscr{C}\\}$ is a transduction of $\mathscr{C}$. Then,
for every class $\mathscr{D}$ we have $\mathscr{C}\sqsubseteq_{\rm
FO}\mathscr{D}$ if and only if there exists some integer $r$ with
$\mathscr{C}\sqsubseteq_{\rm FO}\mathcal{B}_{r}^{\mathscr{D}}$.

  * _Proof of the claim_.

Let $\mathsf{H}$ be the hereditary transduction; which closes a class by
taking induced subgraphs (see Figure 3).

As $\mathcal{B}_{r}^{\mathscr{D}}\sqsubseteq_{\rm FO}\mathscr{D}$ (as
witnessed by $\mathsf{H}$), if there exists some integer $r$ with
$\mathscr{C}\sqsubseteq_{\rm FO}\mathcal{B}_{r}^{\mathscr{D}}$, then
$\mathscr{C}\sqsubseteq_{\rm FO}\mathscr{D}$. Now assume
$\mathscr{C}\sqsubseteq_{\rm FO}\mathscr{D}$. First, note that the class
$\mathscr{C}^{\prime}$ is addable (as
$n(G+K_{1})\operatorname{\uplus}m(G+K_{1})=(m+n)(G+K_{1})$). As
$\mathscr{C}^{\prime}\sqsubseteq_{\rm FO}\mathscr{C}$ (by assumption), we have
$\mathscr{C}^{\prime}\sqsubseteq_{\rm FO}\mathscr{D}$. Let $\mathsf{T}$ be a
transduction such that $\mathscr{C}^{\prime}\subseteq\mathsf{T}(\mathscr{D})$.
According to Lemma 15, there exist of a copy operation $\mathsf{C}$ and an
immersive transduction $\mathsf{T}_{\rm imm}$, such that $\mathsf{T}$ is
subsumed by $\mathsf{T}_{\rm imm}\circ\mathsf{C}$. Let
$\mathscr{D}^{\prime}=\mathsf{C}(\mathscr{D})$. According to Lemma 14, there
is an integer $r$ such that $\mathscr{C}\sqsubseteq_{\rm
FO}^{\circ}\mathcal{B}_{r}^{\mathscr{D}^{\prime}}$. Note that, for every graph
$G$ and every positive integer $r$, every ball of radius $r$ of
$\mathsf{C}(G)$ is an induced subgraph of $\mathsf{C}(B)$, for some ball $B$
of radius $r$ of $G$. Consequently,
$\mathcal{B}_{r}^{\mathscr{D}^{\prime}}\subseteq\mathsf{H}\circ\mathsf{C}(\mathcal{B}_{r}^{\mathscr{D}})$.
Thus, we have $\mathscr{C}\sqsubseteq_{\rm
FO}\mathcal{B}_{r}^{\mathscr{D}^{\prime}}\sqsubseteq_{\rm
FO}\mathcal{B}_{r}^{\mathscr{D}}$. $\vartriangleleft$

The class $\\{n(G\operatorname{+}K_{1})\mid n\in\mathbb{N},G\in\mathscr{G}\\}$
is obviously a transduction of $\mathscr{G}$. Hence, according to Claim 59, a
class $\mathscr{C}$ is locally monadically dependent if and only if it is
monadically dependent. The class $\\{n(G\operatorname{+}K_{1})\mid
n\in\mathbb{N},G\in\mathscr{T\\!\\!P}\\}$ is a transduction of
$\mathscr{T\\!\\!P}$. Hence, according to Claim 59, a class $\mathscr{C}$ is
locally monadically straight if and only if it is monadically straight. The
class $\\{n(G\operatorname{+}K_{1})\mid n\in\mathbb{N},G\in\mathscr{H}\\}$ is
a transduction of $\mathscr{H}$. Hence, according to Claim 59, a class
$\mathscr{C}$ is locally monadically stable if and only if it is monadically
stable.

Although the class of unit interval graphs has unbounded clique-width, every
proper hereditary subclass of unit interval graphs has bounded clique-width
[Loz08, Theorem 3]. This is in particular the case for the class of unit
interval graphs with bounded radius. As classes with bounded cliquewidth are
monadically dependent, the class of unit interval graphs is locally
monadically dependent, hence monadically dependent.

We next prove the analogue of Theorem 58 for stability and dependence, after
recalling their definitions.

For a formula $\varphi(\bar{x},\bar{y})$ and a bipartite graph $H=(I,J,E)$, we
say a graph $G$ encodes $H$ via $\varphi$ if there are sets
$A=\set{\bar{a}_{i}}{i\in I}\subseteq V(G)^{|x|},B=\set{\bar{b}_{j}}{j\in
J}\subseteq V(G)^{|y|}$ such that
$G\models\varphi(\bar{a}_{i},\bar{b}_{j})\Leftrightarrow H\models E(i,j)$ for
all $i,j\in I\times J$.

Given a class $\mathscr{C}$ of graphs, $\varphi$ encodes $H$ in $\mathscr{C}$
if there is some $G\in\mathscr{C}$ encoding $H$ via $\varphi$.

Recall that a formula $\varphi(\bar{x},\bar{y})$ with its free variables
partitioned into two parts is dependent over a class $\mathscr{C}$ of graphs
if there is some finite bipartite graph $H$ such that $\varphi$ does not
encode $H$ in $\mathscr{C}$, while $\varphi$ is stable over $\mathscr{C}$ if
there is some half-graph $H$ such that $\varphi$ does not encode $H$ in
$\mathscr{C}$. The class $\mathscr{C}$ is dependent, resp. stable, if every
partitioned formula is dependent, resp. stable, over $\mathscr{C}$ (cf Section
2.3).

######  Lemma 60.

If a class $\mathscr{C}$ of graphs is independent (resp. unstable), then there
is a strongly local formula that is independent (resp. unstable).

######  Proof 19.3.

We make use of the standard fact that dependence of formulas is preserved by
Boolean combinations [Sim15, Lemma 2.9]. Suppose $\varphi(\bar{x},\bar{y})$ is
independent. Using Gaifman normal form and Lemma 2, we may rewrite $\varphi$
as a Boolean combination of basic local sentences and strongly local formulas.
Since no sentence can be independent, some strongly local formula must be.

The argument for stability is identical, using the fact that stability of
formulas is preserved by Boolean combinations [Pal18, Remark 3.4].

######  Corollary 61.

A class of graphs is dependent (resp. stable) if and only if it is locally
dependent (resp. locally stable).

###  20 Maximum classes, minimum classes, and transduction dualities

For some properties, there is a unique (up to transduction-equivalence)
maximum class with that property, which can be thought of as essentially
exhibiting all the complexity of classes with the property. For example, the
maximum class of bounded cliquewidth is the class of trivially perfect graphs
(or forest-orders; or trees, if considering MSO-transductions) and the maximum
class of bounded linear cliquewidth is the class of half-graphs (or linear
orders; or paths, if considering MSO-transductions), and these statements
capture the “tree-like” and “order-like” behavior of these classes.

Dually, for some properties there is a unique minimum class without that
property, which can be considered a canonical obstruction to that property.
Model-theoretic properties are often defined by such canonical obstructions,
such as (monadic) stability and the class of linear orders or (monadic)
dependence and the class of all graphs.

Some properties may admit both types of characterization, which we will term a
_(singleton) transduction duality_ ; this is in analogy with the well-
established theory of homomorphism dualities [NT00], which suggests many
further lines of inquiry. More generally, a _transduction duality_
$(\Pi,\Psi)$ consists of two sets $\Pi$ and $\Psi$ of graph classes such that
for any graph class $\mathscr{C}$, either there is some $\mathscr{F}\in\Pi$
such that $\mathscr{C}\sqsubseteq_{\rm FO}\mathscr{F}$, or there is some
$\mathscr{D}\in\Psi$ such that $\mathscr{D}\sqsubseteq_{\rm FO}\mathscr{C}$
This formalizes a structural dichotomy stating that the obstructions to being
in $\Pi$ are caputred by $\Psi$. For example, while the classes of shrubdepth
$\leq d$ form a strictly increasing chain in the transduction quasi-order
[GHN+19, Theorem 4.5] and so the bounded shrubdepth property does not admit a
maximum class, [POdMS22] shows a transduction duality where
$\Pi=\\{\mathscr{T}_{n}|n\in\mathbb{N}\\}$ where $\mathscr{T}_{n}$ is the
class of trees of height $n$, and $\Psi$ is the singleton class of paths.

####  20.1 A transduction duality for structurally bounded degree

Given a class property $\Pi$, the class property structurally $\Pi$ is the set
of graph classes that are transducible from a class in $\Pi$. From Proposition
40, we see that the class of cubic graphs is the maximum class of structurally
bounded degree. We now establish a transduction duality by showing the class
of star forests is the minimum class not of structurally bounded degree. The
proof will largely follow from known results on the model-theoretic property
of _mutual algebraicity_.

Given a structure $M$, an $n$-ary relation $R(\bar{x})$ is mutually algebraic
if there is a constant $K$ such that for each $m\in M$, the number of tuples
$\bar{b}\in M^{n}$ such that $M\models R(\bar{b})$ and $m\in\bar{b}$ is at
most $K$. Note a unary relation is always mutually algebraic. Given a
structure $M$, a formula $\varphi(\bar{x})$ is mutually algebraic if it
defines a mutually algebraic relation in $M^{|\bar{x}|}$.

A relational structure $M$ is bounded degree if every atomic relation is
mutually algebraic.

A relational structure $M$ is mutually algebraic if every formula with
parameters from $M$ is equivalent to a Boolean combination of mutually
algebraic formulas with parameters from $M$.

A hereditary class $\mathscr{C}$ is mutually algebraic if every model of
$\operatorname{\text{Th}}(\mathscr{C}):=\bigcap_{M\in\mathscr{C}}\operatorname{\text{Th}}(M)$
is mutually algebraic.

We remark that [Las13, Theorem 3.3] shows that mutual algebraicity of a theory
is equivalent to monadic NFCP. NFCP is a model-theoretical property that is
stronger than stability at the level of theories, although not at the level of
individual formulas. At the level of formulas, NFCP has appeared in [FPST18]
in the context of graph algorithms.

There are two main points in what follows. If $M$ is not mutually algebraic,
then (some elementary extension of) $M$ transduces an equivalence relation
with infinitely many infinite classes by [BL22b, Theorem 3.2]. If $M$ is
mutually algebraic, then some expansion naming finitely many constants is
quantifier-free interdefinable with a bounded degree structure $M^{\prime}$ by
[LT22, Lemma 4.3], which is thus transduction-equivalent to $M$. There is then
some work to transfer these results to hereditary graph classes.

######  Proposition 62.

Let $\mathscr{C}$ be a hereditary class of relational structures in a finite
language. Then the following hold.

  1. 1.

$\mathscr{C}$ is mutually algebraic if and only if $\mathscr{C}$ is (non-
copying, quantifier-free) transduction-equivalent to a hereditary class of
bounded degree structures,

  2. 2.

If $\mathscr{C}$ is mutually algebraic, then so is every transduction of
$\mathscr{C}$,

  3. 3.

$\mathscr{C}$ is mutually algebraic if and only if $\mathscr{C}$ does not
transduce the class of all equivalence relations.

######  Proof 20.1.

(1) $(\Rightarrow)$ By [LT22, Proposition 4.12], if $\mathscr{C}$ is mutually
algebraic then there are bounded degree hereditary classes
$\widetilde{\mathscr{C}}_{1},\dots,\widetilde{\mathscr{C}}_{m}$ such that each
$\widetilde{\mathscr{C}}_{i}$ is (non-copying, quantifier-free) transduction-
equivalent to some $\mathscr{C}_{i}\subset\mathscr{C}$ and
$\bigcup_{i\in[m]}\mathscr{C}_{i}=\mathscr{C}$. Thus $\mathscr{C}$ is (non-
copying, quantifier-free) transduction-equivalent to
$\bigcup_{i\in[m]}\widetilde{\mathscr{C}}_{i}$

(2) Mutual algebraicity of $\mathscr{C}$ is clearly preserved by simple
interpretations. By [Las13, Theorem 3.3], mutual algebraicity is preserved by
coloring. We now show mutual algebraicity is preserved by copying. Suppose
$\mathscr{C}$ is mutually algebraic, and by (1) let
$T\colon\mathscr{D}\to\mathscr{C}$ be a non-copying transduction with
$\mathscr{D}$ bounded degree. Then $T$ also induces a non-copying transduction
from $C_{k}(\mathscr{D})$ to $C_{k}(\mathscr{C})$. Taking copies preserves
being bounded degree, bounded degree classes are mutually algebraic by [LT22,
Lemma 4.3], and we have already shown that non-copying transductions preserve
mutual algebraicity.

(1) $(\Leftarrow)$ By [LT22, Lemma 4.3], bounded degree classes are mutually
algebraic, and we have shown mutual algebraicity is preserved by
transductions.

(3) $(\Rightarrow)$ The class of all equivalence relations is not mutually
algebraic, and mutual algebraicity is preserved by transductions.

$(\Leftarrow)$ From the proof of [BL22b, Theorem 3.2(4)], if $\mathscr{C}$ is
not mutually algebraic then there is a formula $\varphi(x,y)$ and $M\models
Th(\mathscr{C})$ containing elements
$\set{b_{i}}{i\in\mathbb{N}}\cup\set{a_{i,j}}{i,j\in\mathbb{N}}$ such that
$M\models\varphi(a_{i,j},b_{k})\iff i=k$. By compactness, for every
$n\in\mathbb{N}$ there is some $M_{n}\in\mathscr{C}$ containing elements
$\set{b_{i}}{i\in[n]}\cup\set{a_{i,j}}{i,j\in[n]}$ such that
$M_{n}\models\varphi(a_{i,j},b_{k})\iff i=k$. Adding unary predicates
$A:=\set{a_{i,j}}{i,j\in[n]}$ and $B:=\set{b_{i}}{i\in[n]}$, we have that
$M_{n}$ transduces an equivalence relation with $n$ classes of size $n$ by the
formula $\varphi(x,y):=A(x)\wedge A(y)\wedge\exists
z(B(z)\wedge\varphi(x,z)\wedge\varphi(y,z))$, and similarly can transduce any
substructure of that equivalence relation.

When $\mathscr{C}$ is a class of graphs rather than relational structures, we
may strengthen the result.

######  Theorem 63.

Let $\mathscr{C}$ be a hereditary graph class. Then the following are
equivalent.

  1. 1.

$\mathscr{C}$ is mutually algebraic;

  2. 2.

$\mathscr{C}$ is transduction-equivalent to (in particular, is a perturbation
of) a hereditary class of bounded degree graphs;

  3. 3.

$\mathscr{C}$ is a transduction of the class
${\mathscr{C}}\\!\\!\textit{\calligra ubic}\,$ of all cubic graphs,

  4. 4.

$\mathscr{C}$ does not (non-copying) transduce the class $\mathscr{T}_{2}$ of
all star forests.

######  Proof 20.2.

Proposition 62 immediately gives $(2)\Rightarrow(1)$, Proposition 40 gives
$(2)\Leftrightarrow(3)$, and from the fact that the class of star forests is
transduction-equivalent to the class of all equivalence relations also gives
$(1)\Leftrightarrow(4)$. It nearly gives $(1)\Rightarrow(2)$, but a priori
only produces a class $\mathscr{D}_{0}$ of bounded degree relational
structures, rather than graphs, such that $\mathscr{D}_{0}\equiv^{\circ}_{{\rm
FO}}\mathscr{C}$.

From [LT22, Definition 4.10], we see the relations of $\mathscr{D}_{0}$ are
given by relations of arity no greater than those of $\mathscr{C}$, so they
are unary and binary. The class $\mathscr{D}_{0}^{-}$ obtained by forgetting
the unary relations still transduces $\mathscr{C}$ since the transduction can
add the unary relations back. We may view $\mathscr{D}_{0}^{-}$ as a class of
directed edge-colored graphs, and we let $\mathscr{D}_{1}$ be the class of
2-subdivisions of the class of graphs obtained from $\mathscr{D}_{0}^{-}$ by
symmetrizing the edge relations and forgetting the edge-colors. Then
$\mathscr{D}_{1}$ still has bounded degree, and $\mathscr{D}_{1}$ transduces
$\mathscr{D}_{0}^{-}$ as follows: we define a colored directed edge by taking
a 2-subdivided edge, coloring the subdivision vertex closer to what will be
the out-vertex of the directed edge with a special color, and then coloring
the other subdivision vertex with the color of the desired directed edge. Thus
$\mathscr{D}_{1}$ transduces $\mathscr{C}$. As every transduction of a class
with bounded degree is a perturbation of a class with bounded degree, we are
finished.

In particular, we have the following singleton transduction-duality:

$\mathscr{T}_{2}\not\sqsubseteq_{\rm
FO}\mathscr{C}\qquad\iff\qquad\mathscr{C}\sqsubseteq_{\rm
FO}{\mathscr{C}}\\!\\!\textit{\calligra ubic}\,.$

There is a correspondence between dualities and covers in the homomorphism
quasi-order [NT00], and we see a continued connection here.

######  Corollary 64.

The only two $\sqsubseteq_{\rm FO}$-covers of the class of edgeless graphs are
star forests and paths.

######  Proof 20.3.

Suppose $\mathscr{C}$ is a hereditary graph class that does not transduce star
forests. By Theorem 63, $\mathscr{C}$ is transduction-equivalent to a class
$\mathscr{D}$ of graphs with bounded degree. Suppose there is no bound on the
size of connected components in $\mathscr{D}$. Since $\mathscr{D}$ has bounded
degree, we can find arbitrarily long induced paths in the graphs in
$\mathscr{D}$, hence we can transduce $\mathscr{P}$ in $\mathscr{D}$.

If there is a bound on the size of connected components, then $\mathscr{D}$ is
FO-transduction equivalent to the class of edgeless graphs by Proposition 39.

####  20.2 The absence of maximum classes

We prove a strong negative result, implying that no property containing all
bounded expansion classes admits a maximum class. The idea is that we may
“diagonalize” against all the countably many transductions from any candidate
maximum class. On the other hand, we prove a positive result for countable
sets of nowhere dense classes or classes of bounded expansion.

######  Proposition 65.

Up to transduction equivalence, the class of all graphs is the only class that
is an $\sqsubseteq_{\rm FO}$-upper bound for all classes with bounded
expansion.

######  Proof 20.4.

Assume $\mathscr{B}$ is a monadically dependent bound for all classes with
bounded expansion. To a monadically dependent hereditary class $\mathscr{C}$
we associate the mapping
$h_{\mathscr{C}}\colon\mathbb{N}^{+}\rightarrow\mathbb{N}$ as follows:
$h_{\mathscr{C}}(i)$ is the largest integer $n$ such that the exact
$i$-subdivision of $K_{n}$ belongs to $\mathscr{C}$ (this is well-defined by
the assumption that $\mathscr{C}$ is monadically dependent). We now consider
an enumeration $\mathsf{T}_{1},\mathsf{T}_{2},\dots$ of all first-order
transductions (there are countably many) and let
$\mathscr{C}_{i}=\mathsf{T}_{i}(\mathscr{B})$. We further define the function
$h\colon\mathbb{N}^{+}\rightarrow\mathbb{N}$ by
$h(i)=h_{\mathscr{C}_{i}}(i)+1$. By taking $\mathscr{D}$ to be the hereditary
closure of the set $\set{i\text{-subdivided }K_{h(i)}\colon
i\in\mathbb{N}^{+}}$ we get a bounded expansion class with
$h_{\mathscr{D}}(i)\geq h(i)$ for every integer $i$. As $\mathscr{B}$ is a
bound of all bounded expansion classes, there exists a transduction, say
$\mathsf{T}_{k}$, such that
$\mathscr{D}\subseteq\mathsf{T}_{k}(\mathscr{B})=\mathscr{C}_{k}$. However,
this implies $h_{\mathscr{D}}(i)\leq h_{\mathscr{C}_{k}}(i)$ for every integer
$i$, which contradicts $h_{\mathscr{D}}(k)\geq h(k)\geq
h_{\mathscr{C}_{k}}(k)+1$.

However, we show that for countable sets of classes with bounded expansion, we
can find an upper bound with bounded expansion.

######  Lemma 66.

Let $\mathscr{C}_{1},\dots,\mathscr{C}_{k},\dots$ be countably many classes of
graphs.

Then, there exists a class $\mathscr{B}$ such that
$\mathscr{C}_{i}\sqsubseteq_{\rm FO}^{\circ}\mathscr{B}$ holds for all
$i\in\mathbb{N}$, and such that

  * •

if every $\mathscr{C}_{i}$ has bounded expansion, then $\mathscr{B}$ has
bounded expansion;

  * •

if every $\mathscr{C}_{i}$ is nowhere dense, then $\mathscr{B}$ is nowhere
dense.

######  Proof 20.5.

Let $\mathscr{B}$ contain, for each $i\in\mathbb{N}$ the $i$-subdivision of
all the graphs in $\mathscr{C}_{i}$.

By construction, the non-copying transduction $\mathsf{T}_{i}$ which connects
vertices at distance exactly $i+1$ and keep only marked vertices is such that
$\mathsf{T}_{i}(\mathscr{B})\supseteq\mathscr{C}_{i}$. Thus,
$\mathscr{C}_{i}\sqsubseteq_{\rm FO}^{\circ}\mathscr{B}$ holds for all
$i\in\mathbb{N}$.

Assume that the $k$-th subdivision $H^{(k)}$ of a graph $H$ belongs to
$\mathscr{B}$, where $H$ has minimum degree at least $3$. Then, $H^{(k)}$ is
the $i$-subdivision of some graph $H^{\prime}\in\mathscr{C}_{i}$ for some
$i\leq k$. It follows that
$\mathscr{B}\,\widetilde{\nabla}\,k\subseteq\bigcup_{i=1}^{k}\mathscr{C}_{i}\,\widetilde{\nabla}\,k$.
Consequently, if all the $\mathscr{C}_{i}$’s have bounded expansion then
$\mathscr{B}$ has bounded expansion, and if all the $\mathscr{C}_{i}$’s are
nowhere dense then $\mathscr{B}$ is nowhere dense.

####  20.3 Bounded twin-width

Graph classes of bounded twin-width were introduced in [BKTW20], and have been
intensively studied since. While we will not need their definition for this
section, we note that the property of bounded twin-width is preserved by FO-
transductions, and any further required facts will be referenced. We provide a
counterexample to a conjecture, stated in different terminology, that the
cubic graphs are the minimum class of unbounded twin-width.

Let $\mathscr{C}$ be a hereditary graph class. Then $\mathscr{C}$ is
_delineated_ if for every hereditary subclass
$\mathscr{D}\subseteq\mathscr{C}$, $\mathscr{D}$ has bounded twin-width if and
only if $\mathscr{D}$ is monadically dependent.

In [BCK+22, Conjecture 66], it was conjectured that if $\mathscr{C}$ is not
delineated then $\mathscr{C}$ transduces the class $\mathscr{S}$ of subcubic
graphs. This is equivalent to conjecturing that $\mathscr{S}$ is the minimum
class of unbounded twin-width. In one direction, suppose $\mathscr{S}$ is the
minimum such class; if $\mathscr{C}$ is not delineated then it has unbounded-
twin width, and so $\mathscr{S}\sqsubseteq_{\rm FO}\mathscr{C}$. In the other
direction, suppose the original conjecture holds. If $\mathscr{C}$ has
unbounded twin-width then either it is not monadically dependent or it is not
delineated (witnessed by considering $\mathscr{C}$ as a subclass of itself);
in either case, $\mathscr{S}\sqsubseteq_{\rm FO}\mathscr{C}$.

A graph class $\mathscr{C}$ is small (resp. unlabeled-small) if there is
$c\in\R$ such that the number of labeled structures of size $n$ in
$\mathscr{C}$ is $O(c^{n}\cdot n!)$ (resp. the number of unlabeled structures
of size $n$ in $\mathscr{C}$ is $O(c^{n})$).

######  Lemma 67.

Let $\mathscr{C}$ be an unlabeled-small class of graphs with bounded degree.
Then every transduction $\mathscr{D}$ of $\mathscr{C}$ is also unlabeled-
small.

######  Proof 20.6.

Let $\mathsf{T}$ be a transduction so that
$\mathscr{D}\subseteq\mathsf{T}(\mathscr{C})$. By Theorem 8, we may decompose
$\mathsf{T}$ into the composition of a copy operation, an immersion, and a
perturbation. Note that copying and perturbations both preserve being
unlabeled-small since every structure in the image has a pre-image that is no
larger, and that copying also preserves being bounded-degree; thus these
operations have no effect and we may assume $\mathsf{T}$ is an immersion. Fix
a target graph $D\in\mathscr{D}$ and let $C\in\mathsf{T}^{-1}(D)$. If
$\mathsf{T}$ is strongly $r$-local, then let $C^{\prime}\subseteq
C\in\mathscr{C}$ be obtained by keeping the vertices of $C$ that remain in
$\mathsf{T}(C)$, as well as their $r$-neighborhoods. By strong $r$-locality,
$C^{\prime}\in\mathsf{T}^{-1}(D)$. Since $\mathscr{C}$ has bounded degree,
there is some $k$ such that $|C^{\prime}|\leq k|D|$.

Let $\mathscr{C}_{n}$ denote the number of unlabeled graphs of size $n$ in
$\mathscr{C}$, and similarly $\mathscr{D}_{n}$. Suppose
$\mathscr{C}_{n}=O(c^{n})$. Then if the transduction uses $\ell$ colors, we
have $\mathscr{D}_{n}\leq 2^{\ell kn}O(c^{kn})$ since every graph in
$\mathscr{D}_{n}$ is the $\mathsf{T}$-image of a graph in $\mathscr{C}_{kn}$,
so $\mathscr{D}$ is unlabeled-small.

######  Corollary 68.

The class of subcubic graphs is not the $\sqsubseteq_{\rm FO}$-minimum class
of unbounded twin-width.

######  Proof 20.7.

Let $\mathscr{C}$ be a hereditary unlabeled-small class of graphs of unbounded
twin-width and bounded degree (so $\mathscr{C}$ is monadically dependent), as
constructed in [BGTT22], so $\mathscr{C}$ is not delineated. Since the class
of subcubic graphs is not unlabeled-small [Noy15, Formula 6.6], Lemma 67 shows
it cannot be transduced from $\mathscr{C}$.

We remark that the class $\mathscr{C}$ is only shown to be small rather than
unlabeled-small in [BGTT22], using [BGK+22, Lemma 41] that the class of
induced subgraphs of the Cayley graph of a finitely-generated group is small.
However, the same proof shows such a class is unlabeled-small; the only change
needed is that Cayley’s formula for the number of labeled rooted forests on
$n$ vertices should be replaced by an exponential upper bound on the number of
unlabeled rooted forests on $n$ vertices, which follows from such a bound on
unlabeled rooted trees [Drm15, Theorem 4.4.6].

######  Problem 69.

Is (unlabeled-)smallness preserved by transductions?

However, we have the following positive results concerning maximum classes.

######  Theorem 70 (follows from [BBGT23, Theorem 1.5]).

There exists a constant $c$ such that every class with bounded twin-width is a
transduction of the class of all graphs with twin-width at most $c$. In other
words, the bounded twin-width property has a maximum.

The following is also a direct consequence of results in [BBGT23].

######  Theorem 71.

The property of being monadically stable and having bounded twin-width has a
maximum, which can be chosen to be the class of all graphs with twin-width at
most $c$ and girth at least $6$ (for some constant $c$).

######  Proof 20.8.

It has been proved in [GPT22] that every monadically stable class of graphs
with bounded twin-width is a transduction of a weakly sparse class with
bounded twin-width. For $k,t\in\mathbb{N}$, let $\mathscr{C}_{k,t}$ be the
class of all $K_{t,t}$-free graphs with twin-width at most $k$. According to
[BBGT23, Theorem 1.4], there exists a constant $c$ and a function $f$ such
that, for every graph in $G\in\mathscr{C}_{k,t}$, the $f(k,t)$-subdivision of
$G$ has twin-width at most $c$ (and girth at least $6$). It follows that
$\mathscr{C}_{k,t}$ is an ${\rm FO}$-transduction of the class $\mathscr{B}$
of all graphs with girth at least $6$ and twin-width at most $c$.
Consequently, $\mathscr{B}$ is a maximum for the property of being monadically
stable and having bounded twin-width.

####  20.4 Not a lattice

We now show the transduction quasi-order is not a lattice, by showing the
classes of planar graphs and of half-graphs have no greatest lower bound, i.e.
there is no maximal class for the downset below both classes. This also shows
that the join of infinitely many classes is not generally defined, as we could
then define the meet of two classes as the join of all classes below both. We
will make use of Lemma 38 showing that the class of planar graphs transduces
every class of bounded pathwidth. We first show that the pathwidth hierarchy
is strict in the transduction quasi-order, and thus has no maximum class.

######  Theorem 72.

For $n\geq 1$ we have $\mathscr{T}_{n+2}\subseteq_{\rm
FO}\mathscr{P\\!W\\!}_{n+1}$ but $\mathscr{T}_{n+2}\not\sqsubseteq_{\rm
FO}\mathscr{P\\!W\\!}_{n}$. Consequently,
$\mathscr{P\\!W\\!}_{n+1}\not\sqsubseteq_{\rm FO}\mathscr{P\\!W\\!}_{n}$.

######  Proof 20.9.

For convenience, we define
$\mathscr{T}_{1}=\mathscr{P\\!W\\!}_{0}=\mathscr{E}$, which is consistent with
our definitions. We now prove $\mathscr{T}_{n+1}\not\sqsubseteq_{\rm
FO}\mathscr{P\\!W\\!}_{n-1}$ by induction on $n$. For $n=1$, this follows from
Proposition 39 (or from the known fact $\mathscr{T}_{2}\sqsupset\mathscr{E}$).
Now assume that we have proved the statement for $n\geq 1$ and assume towards
a contradiction that $\mathscr{T}_{n+2}\sqsubseteq_{\rm
FO}\mathscr{P\\!W\\!}_{n}$. The class $\mathscr{P\\!W\\!}_{n}$ is the monotone
closure of the class $\mathcal{I}_{n+1}$ of interval graphs with clique number
at most $n+1$. As the class $\mathcal{I}_{n+1}$ has bounded star chromatic
number, it follows from Corollary 20 that
$\mathscr{P\\!W\\!}_{n}\sqsubseteq_{\rm FO}\mathcal{I}_{n+1}$. Let
$\mathsf{T}$ be the composition of the respective transductions, so that
$\mathscr{T}_{n+2}\subseteq\mathsf{T}(\mathcal{I}_{n+1})$. As
$\mathscr{T}_{n+2}$ is additive, it follows from Corollary 16 that there is a
copy operation $\mathsf{C}$ and an immersive transduction $\mathsf{T}_{0}$
such that $\mathsf{T}_{0}\circ\mathsf{C}$ subsumes $\mathsf{T}$. As
$\\{G+K_{1}:G\in\mathscr{T}_{n+1}\\}\subseteq\mathscr{T}_{n+2}$ if follows
from Lemma 14 that there exists an integer $r$ such that
$\mathscr{T}_{n+1}\sqsubseteq^{\circ}_{\rm
FO}\mathcal{B}_{r}^{\mathsf{C}(\mathcal{I}_{n+1})}\subseteq\mathsf{C}(\mathcal{B}_{r}^{\mathcal{I}_{n+1}})$.
According to Lemma 15, as $\mathscr{T}_{n+1}$ is additive, there exists an
immersive transduction $\mathsf{T}_{1}$ with
$\mathscr{T}_{n+1}\subseteq\mathsf{T}_{1}\circ\mathsf{C}(\mathcal{B}_{r}^{\mathcal{I}_{n+1}})$.

Let $G\in\mathcal{B}_{r}^{\mathcal{I}_{n+1}}$ and let $P$ be a shortest path
connecting the minimal and maximal vertices in an interval representation of
$G$. Then $P$ has length at most $2r$, $P$ dominates $G$, and
$G-P\in\mathcal{I}_{n}$. By encoding the adjacencies in $G$ to the vertices of
$P$ by a monadic expansion, we get that that there exists a transduction
$\mathsf{T}_{2}$ (independent of our choice of $G$) such that $G$ is a
$\mathsf{T}_{2}$-transduction of $H$, where $H$ is obtained from $G$ by
deleting all the edges incident to a vertex in $P$. In particular,
$\mathcal{B}_{r}^{\mathcal{I}_{n+1}}\subseteq\mathsf{T}_{2}(\mathcal{I}_{n})$
thus
$\mathscr{T}_{n+1}\subseteq\mathsf{T}_{1}\circ\mathsf{C}\circ\mathsf{T}_{2}(\mathcal{I}_{n})$,
which contradicts our induction hypothesis.

######  Theorem 73.

The class $\mathscr{H}$ of half-graphs and the class
${\mathscr{P}}\\!\\!\textit{\calligra lanar}\,$ of planar graphs have no
greatest lower bound in $\sqsubseteq_{\rm FO}$ (or in $\sqsubseteq_{\rm
FO}^{\circ}$).

######  Proof 20.10.

Consider one of the quasi-orders $\sqsubseteq_{\rm FO}$, $\sqsubseteq_{\rm
FO}^{\circ}$, which we will denote by $(\mathfrak{X},\sqsubseteq)$. Assume
$\mathscr{C}$ is the greatest lower bound of $\mathscr{H}$ and
${\mathscr{P}}\\!\\!\textit{\calligra lanar}\,$ in
$(\mathfrak{X},\sqsubseteq)$. According to Theorem 5, the class
${\mathscr{P}}\\!\\!\textit{\calligra lanar}\,$, being nowhere dense, is
monadically stable. Thus, as $\mathscr{C}$ is (by assumption) a transduction
of ${\mathscr{P}}\\!\\!\textit{\calligra lanar}\,$, it is also monadically
stable. Hence, according to [NOdMRS20], there exists an integer $k$ such that
$\mathscr{C}\sqsubseteq_{\rm FO}^{\circ}\mathscr{P\\!W\\!}_{k}$ (hence
$\mathscr{C}\sqsubseteq\mathscr{P\\!W\\!}_{k}$). According to Theorem 72,
$\mathscr{P\\!W\\!}_{k+1}\not\sqsubseteq_{\rm FO}\mathscr{P\\!W\\!}_{k}$
(hence $\mathscr{P\\!W\\!}_{k+1}\not\sqsubseteq\mathscr{P\\!W\\!}_{k}$). Thus,
$\mathscr{C}\sqsubset\mathscr{P\\!W\\!}_{k+1}$. However,
$\mathscr{P\\!W\\!}_{k+1}$ is addable (hence additive),
$\mathscr{P\\!W\\!}_{k+1}\sqsubseteq_{\rm FO}^{\circ}\mathscr{H}$ and,
according to Lemma 38,
$\mathscr{P\\!W\\!}_{k+1}\sqsubseteq^{\circ}{\mathscr{P}}\\!\\!\textit{\calligra
lanar}\,$. In particular, $\mathscr{P\\!W\\!}_{k+1}\in\mathfrak{X}$,
$\mathscr{P\\!W\\!}_{k+1}\sqsubseteq\mathscr{H}$, and
$\mathscr{P\\!W\\!}_{k+1}\sqsubseteq{\mathscr{P}}\\!\\!\textit{\calligra
lanar}\,$, what contradicts the assumption that $\mathscr{C}$ is the greatest
lower bound of $\mathscr{H}$ and ${\mathscr{P}}\\!\\!\textit{\calligra
lanar}\,$ in $(\mathfrak{X},\sqsubseteq)$.

On the other hand, it is easy to see that the least upper bound of two classes
is always defined.

######  Proposition 74.

Let $\mathscr{C}_{1}$ and $\mathscr{C}_{2}$ be graph classes. Then
$\mathscr{C}_{1}\cup\mathscr{C}_{2}$ is the least upper bound of
$\mathscr{C}_{1}$ and $\mathscr{C}_{2}$ in $\sqsubseteq_{\rm FO}$ (and in
$\sqsubseteq_{\rm FO}^{\circ}$).

######  Proof 20.11.

We only do the proof for $\sqsubseteq_{\rm FO}$, since that for
$\sqsubseteq_{\rm FO}^{\circ}$ is essentially identical. It is immediate that
$\mathscr{C}_{1}\cup\mathscr{C}_{2}$ transduces each of$\mathscr{C}_{1}$ and
$\mathscr{C}_{2}$. So suppose $\mathscr{D}$ transduces $\mathscr{C}_{1}$ and
$\mathscr{C}_{2}$ via transductions $\mathsf{T}_{1}$ and $\mathsf{T}_{2}$. We
wish to encode these both in a single transduction (and for the proof to carry
over to $\sqsubseteq_{\rm FO}^{\circ}$, we should not achieve this via
copying). We do this by introducing a new color $U(x)$. We first perform the
copy operation the max of the number of times it was performed in
$\mathsf{T}_{1}$ and $\mathsf{T}_{2}$. Then, if any point is colored by $U$,
we perform the interpretation from $\mathsf{T}_{1}$, and otherwise perform the
interpretation from $\mathsf{T}_{2}$.

###  21 Dense analogues and open problems

In this section, we discuss the notion of _dense analogue_ of a class
property, as introduced in [GPT22]. In the following, we consider only
infinite hereditary classes. Let $\Sigma$ be the class property of being
weakly sparse (that is the property of a class that there is some integer $s$
such that no graph in the class includes $K_{s,s}$ as a subgraph). Unlike the
model-theoretic dividing lines of stability and independence for hereditary
classes, the notion of weakly sparse is not preserved by transductions, but
finds its motivation in the study of sparse classes. Recall that a class
property $\Pi$ is a _transduction downset_ if it is preserved by
transductions. In other words, a transduction downset consists of a downset
for the transduction order $(\mathfrak{C},\sqsubseteq_{\rm FO})$. The
_transduction closure_ $\Pi^{\downarrow}$ of a class property $\Pi$ is the
property to be a transduction of a class in $\Pi$, that is the smallest
transduction downset (for inclusion) that includes $\Pi$. (This is the same as
the class property structurally $\Pi$.) A _transduction ideal_ is a
transduction downset $\Pi$ such that every two elements of $\Pi$ have an upper
bound in $\Pi$, i.e. if the union of any two classes in $\Pi$ is in $\Pi$ (by
Proposition 74). A class property $\Pi_{s}$ is a _sparse transduction downset_
if it contains only weakly sparse classes and is preserved by transductions to
weakly sparse classes. In other words, a sparse transduction downset is the
trace on $\Sigma$ of a transduction downset. A sparse transduction downset
$\Pi_{s}$ is a _sparse transduction ideal_ if the union of any two classes in
$\Pi_{s}$ is in $\Pi_{s}$.

The _dense analogue_ $\Pi$ of a sparse transduction downset $\Pi_{s}$ is the
largest transduction downset $\Pi$ (for inclusion) with
$\Pi\cap\Sigma=\Pi_{s}$. This definition is valid as
$\Pi_{s}^{\downarrow}\cap\Sigma=\Pi_{s}$ for every sparse transduction
downset, and the union of all transduction downsets $\Pi$ with
$\Pi\cap\Sigma=\Pi_{s}$ is a transduction downset with the same property.

######  Proposition 75.

The dense analogue of a sparse transduction ideal is a transduction ideal.

######  Proof 21.1.

Let $\Pi$ be the dense analogue of a sparse transduction ideal $\Pi_{s}$.
Assume $\mathscr{C}_{1},\mathscr{C}_{2}\in\Pi$, and let $\mathscr{D}$ be a
weakly sparse transduction of
$\mathscr{C}_{1}\operatorname{\uplus}\mathscr{C}_{2}$. Then, there is a
partition $\mathscr{D}_{1}\operatorname{\uplus}\mathscr{D}_{2}$ of
$\mathscr{D}$ with $\mathscr{D}_{1}\sqsubseteq\mathscr{C}_{1}$ and
$\mathscr{D}_{2}\sqsubseteq\mathscr{C}_{2}$. As $\mathscr{D}$ is weakly
sparse, so are $\mathscr{D}_{1}$ and $\mathscr{D}_{2}$. Thus, both
$\mathscr{D}_{1}$ and $\mathscr{D}_{2}$ belong to $\Pi_{s}$. As $\Pi_{s}$ is a
sparse transduction ideal, $\mathscr{D}\in\Pi$. It follows that every weakly
sparse transduction of $\mathscr{C}_{1}\operatorname{\uplus}\mathscr{C}_{2}$
belongs to $\Pi_{s}$, thus
$\mathscr{C}_{1}\operatorname{\uplus}\mathscr{C}_{2}\in\Pi$. Therefore, $\Pi$
is a transduction ideal.

######  Proposition 76.

Let $\Pi$ be a transduction downset. Then, $\Pi$ is the dense analogue of
$\Pi\cap\Sigma$ if and only if the complement $\Pi^{*}$ of $\Pi$ is such that

$\mathscr{C}\in\Pi^{*}\quad\Longrightarrow\quad(\exists\mathscr{D}\in\Sigma\cap\Pi^{*})\
\mathscr{D}\sqsubseteq_{\rm FO}\mathscr{C}\qquad\text{(\/property $\Pi^{*}$ is
grounded in $\Sigma$)}.$

######  Proof 21.2.

Assume $\Pi$ is the dense analogue of $\Pi\cap\Sigma$ and let $\Pi^{*}$ be the
complement of $\Pi$. As $\Pi$ is the dense analogue of $\Pi\cap\Sigma$, for
every class $\mathscr{C}\notin\Pi$ there exists a weakly sparse class
$\mathscr{D}\notin\Pi$ with $\mathscr{D}\sqsubseteq_{\rm FO}\mathscr{C}$.

Conversely, let $\Pi_{s}=\Pi\cap\Sigma$. For every $\mathscr{C}\notin\Pi$, we
have $\mathscr{C}\in\Pi^{*}$. Thus, there exists $\mathscr{D}\sqsubseteq_{\rm
FO}\mathscr{C}$ with $\mathscr{D}\in\Sigma\cap\Pi^{*}$. Hence, $\mathscr{D}$
is weakly sparse and $\mathscr{D}\notin\Pi$. It follows that $\Pi$ is the
dense analogue of $\Pi_{s}$.

Monadic dependence is the dense analogue of nowhere dense. If a class is
nowhere dense, then it is monadically dependent [AA14]. Conversely, assume
that $\mathscr{C}$ is a hereditary weakly sparse monadically dependent class.
Assume for contradiction that $\mathscr{C}$ is not nowhere dense. Then,
according to [Dvo18, Theorem 6], there is some integer $k$ such that
$\mathscr{C}$ contains a $\leq k$-subdivision of every complete graph. It
follows that the class of all graphs can be obtained as a transduction of
$\mathscr{C}$, contradicting the hypothesis that $\mathscr{C}$ is monadically
dependent.

Note that this shows that the dense analogue of $\Pi$ can be strictly larger
than $\Pi^{\downarrow}$, since nowhere dense classes are monadically stable
and thus their transduction closure is contained within monadic stability.

Bounded shrubdepth is the dense analogue of bounded treedepth. Indeed, every
weakly sparse class with bounded shrubdepth has bounded treedepth [NOdM12,
Proposition 6.4], while the class of paths (which has unbounded treedepth) can
be transduced from any class with unbounded shrubdepth [POdMS22, Theorem 1.1].

It would be tempting to think that the prominent role played by weakly sparse
classes in our understanding of the transduction quasi-order is due to the
fact that the complexity of a set of classes is determined by its relation to
$\Sigma$. A strong formalization of this is given by the following order-
theoretic notion: a subset $\Upsilon$ of classes is sup-dense in the
transduction quasi-order $\sqsubseteq_{\rm FO}$ if, for every two classes
$\mathscr{C}$ and $\mathscr{D}$ we have

$\mathscr{C}\equiv_{\rm
FO}\mathscr{D}\qquad\iff\qquad\forall\mathscr{F}\in\Upsilon\quad(\mathscr{F}\sqsubseteq_{\rm
FO}\mathscr{C})\iff(\mathscr{F}\sqsubseteq_{\rm FO}\mathscr{D}).$

######  Proposition 77.

The set $\Sigma$ is not sup-dense in the FO-transduction quasi-order.

######  Proof 21.3.

Let $\mathscr{C}$ be the class of all planar graphs, and let $\mathscr{D}$ be
the union of $\mathscr{C}$ and of the class $\mathscr{H}$ of all half-graphs.
As every transduction of $\mathscr{C}$ is monadically stable and $\mathscr{D}$
is not (as it includes $\mathscr{H}$), we have that
$\mathscr{D}\sqsubseteq_{\rm FO}\mathscr{C}$ but $\mathscr{D}\not\equiv_{\rm
FO}\mathscr{C}$. However, according to [NOdMRS20], every weakly sparse
transduction of half-graphs has bounded pathwidth, and thus by Lemma 38 is a
transduction of $\mathscr{C}$. Thus $\Sigma$ is not sup-dense in the
transduction quasi-order.

While the classes $\mathscr{C}$ and $\mathscr{D}$ above had the same weakly
sparse classes $\sqsubseteq_{\rm FO}$-below them, they had different weakly
sparse classes $\sqsubseteq_{\rm FO}$-above them, since the only weakly sparse
classes $\sqsubseteq_{\rm FO}$-above $\mathscr{D}$ are somewhere dense. We now
show that even requiring that $\mathscr{C}$ and $\mathscr{D}$ have the same
relation to every weakly sparse class does not force them to be $\equiv_{\rm
FO}$-equivalent.

######  Proposition 78.

There are hereditary graph classes $\mathscr{C}\not\equiv_{\rm FO}\mathscr{D}$
such that for every weakly sparse class $\mathscr{F}$, we have
$\mathscr{F}\sqsubseteq_{\rm FO}\mathscr{C}\iff\mathscr{F}\sqsubseteq_{\rm
FO}\mathscr{D}$ and $\mathscr{F}\sqsupseteq_{\rm
FO}\mathscr{C}\iff\mathscr{F}\sqsupseteq_{\rm FO}\mathscr{D}$.

######  Proof 21.4.

Let $\mathscr{C}_{0}$ be a maximum monadically stable class of bounded twin-
width as given by Theorem 71, let $\mathscr{H}$ be the class of half-graphs,
let $\mathscr{T\\!\\!P}$ be the class of trivially perfect graphs, let
$\mathscr{C}=\mathscr{C}_{0}\cup\mathscr{H}$, and let
$\mathscr{D}=\mathscr{C}_{0}\cup\mathscr{T\\!\\!P}$. Then,
$\mathscr{D}\sqsubseteq_{\rm FO}\mathscr{C}$ but $\mathscr{D}\not\equiv_{\rm
FO}\mathscr{C}$. By [GW00b], every weakly sparse transduction of
$\mathscr{T\\!\\!P}$ or $\mathscr{H}$ has bounded treewidth, and thus is
contained in $\mathscr{C}_{0}$. On the other hand, the only weakly sparse
classes above either $\mathscr{C}$ or $\mathscr{D}$ are somewhere dense.

We now turn to various conjectures concerning dense analogues, and prove some
equivalences between them, for which the following proposition will be
helpful.

######  Proposition 79.

Let $\Pi_{s}$ be a sparse transduction downset. Assume that $\Pi_{s}$ has the
following characterization, where $\mathscr{F}\in\Sigma$ is a non-empty weakly
sparse class of graphs:

$\mathscr{C}\in\Pi_{s}\iff\mathscr{C}\in\Sigma\text{ and }\exists
F\in\mathscr{F}\text{ s.t. }\mathscr{C}\text{ excludes $F$ as a topological
minor.}$ (4)

Then, a weakly sparse class $\mathscr{C}$ belongs to $\Pi_{s}$ if and only if
it has no transduction to a class $\mathscr{D}$ containing, for each
$F\in\mathscr{F}$, some subdivision of $F$.

######  Proof 21.5.

Let $\mathscr{C}$ be a weakly sparse class. We prove by contraposition that if
$\mathscr{C}$ belongs to $\Pi_{s}$, then $\mathscr{C}$ has no transduction to
a class $\mathscr{D}$ containing, for each $F\in\mathscr{F}$, some subdivision
of $F$. Assume that $\mathscr{C}$ has a transduction to a class $\mathscr{D}$
containing, for each $F\in\mathscr{F}$, some subdivision of $F$. By
considering a subclass, we can assume that $\mathscr{D}$ contains no other
graphs than these subdivisions. Then, $\mathscr{D}$ is weakly sparse (as
$\mathscr{F}$ is weakly sparse) and, according to (4),
$\mathscr{D}\notin\Pi_{s}$. As $\Pi_{s}$ is a downset,
$\mathscr{C}\notin\Pi_{s}$.

Conversely, assume that $\mathscr{C}$ has no transduction to a class
containing, for each $F\in\mathscr{F}$, some subdivision of $F$. In
particular, the hereditary closure $\mathsf{H}(\mathscr{C})$ of $\mathscr{C}$
does not contain any subdivision of some $F\in\mathscr{F}$. In other words, no
graph in $\mathscr{C}$ contains a subdivision of $F$ as an induced subgraph.
As $\mathscr{C}$ is weakly sparse, it follows from [Dvo18] that $\mathscr{C}$
has bounded expansion. In particular, $\mathscr{C}$ has bounded star chromatic
number. According to Corollary 20 the monotone closure $\mathscr{C}^{\prime}$
of $\mathscr{C}$ is a transduction of $\mathscr{C}$. Considering this time the
monotone closure transduction of $\mathscr{C}$, we get that there is a graph
$F^{\prime}\in\mathscr{F}$ such that no graph in $\mathscr{C}^{\prime}$
contains a subdivision of $\mathscr{F}^{\prime}$ as a subgraph. By (4), it
follows that $\mathscr{C}^{\prime}\in\Pi_{s}$. As
$\mathscr{C}\subseteq\mathscr{C}^{\prime}$, we get $\mathscr{C}\in\Pi_{s}$ as
well.

Let us give a pair of examples of applications of Proposition 79.

Every weakly sparse class with unbounded treewidth has a transduction
containing a subdivision of each wall.

######  Proof 21.6.

Let $\Pi_{s}$ be the property of having bounded treewidth. It is well known
that a weakly sparse class has bounded treewidth if and only if it excludes
some wall as a topological minor. Hence, according to Proposition 79, a class
has unbounded twin-width if and only if it has a transduction to a class
containing a subdivision of each wall.

Every weakly sparse class with unbounded pathwidth has a transduction
containing a subdivision of each cubic tree.

######  Proof 21.7.

Let $\Pi_{s}$ be the property of having bounded pathwidth. It is well known
that a weakly sparse class has bounded pathwidth if and only if it excludes
some cubic tree as a topological minor. Hence, according to Proposition 79, a
class has unbounded pathwidth if and only if it has a transduction to a class
containing a subdivision of each cubic tree.

It was conjectured in [GPT22] that cliquewidth is the dense analog of
treewidth and linear cliquewidth is the dense analog of pathwidth. Every
weakly sparse transduction of a class with bounded cliquewidth (resp. linear
cliquewidth) has bounded treewidth (resp. bounded pathwidth). Hence, according
to the characterization given in Sections 21 and 21, these conjectures can be
restated as follows.

######  Conjecture 80.

Bounded linear cliquewidth is the dense analogue of bounded pathwidth.

######  Conjecture 81.

Bounded cliquewidth is the dense analogue of bounded treewidth

A particular case concerns sparse transduction downset $\Pi_{s}$ that do not
include bounded pathwidth. Indeed, if some class $\mathscr{C}$ with bounded
pathwidth does not belong to $\Pi_{s}$, this means that the class of half-
graphs does not belong to the dense analogue of $\Pi_{s}$. In such a case, the
dense analogue of $\Pi_{s}$ is stable and the conjecture restates as:

######  Conjecture 82.

Let $\Pi_{s}$ be a sparse transduction downset that does not include all
classes with bounded pathwidth. Then, the largest transduction downset whose
trace on $\Sigma$ is $\Pi_{s}$ is the smallest transduction downset including
$\Pi_{s}$.

An example where this conjecture holds is the property of having bounded
degree:

######  Proposition 83.

Let $\Pi_{s}$ be the property of nearly having bounded degree. Then, $\Pi_{s}$
is a sparse transduction downset and the largest transduction downset $\Pi$
whose trace on $\Sigma$ is $\Pi_{s}$ is the smallest transduction downset
including $\Pi_{s}$.

Furthermore, $\Pi$ consists of the mutually algebraic (equiv. monadically
NFCP) classes.

######  Proof 21.8.

First note that, according to Proposition 40, $\Pi_{s}$ is equivalent to the
property of being a weakly sparse perturbation of a class with bounded degree
and is a sparse transduction downset.

By Theorem 63 every mutually algebraic class of graphs is transduction-
equivalent to a class of bounded degree graphs. Hence, as the property of
being mutually algebraic is a transduction downset, it is the smallest
transduction downset including $\Pi_{s}$.

On the other hand, if $\mathscr{C}$ is a class that is not mutually algebraic,
it transduces star forests by Theorem 63, hence it does not belong to $\Pi$.
Thus, the property of being mutually algebraic is also the largest
transduction downset whose trace on $\Sigma$ is $\Pi_{s}$.

A related problem is the relation between sparse and stable properties.

######  Conjecture 84.

Let $\Pi_{s}$ be a sparse transduction downset of bounded expansion classes
with dense analogue $\Pi$. Then, the smallest transduction downset
$\Pi_{s}^{\downarrow}$ including $\Pi_{s}$ is the set of all (monadically)
stable classes in $\Pi$.

This conjecture is deeply related to the studies in [NOdMRS20, NOdMP+21,
GPT22]. However, it is plausible that one cannot relax the condition that the
classes in $\Pi_{s}$ have bounded expansion, because of the following
equivalence.

######  Proposition 85.

The following statements are equivalent:

  1. 1.

For every sparse transduction downset $\Pi_{s}$ with dense analogue $\Pi$, the
transduction downset $\Pi_{s}^{\downarrow}$ is the set of all stable classes
in $\Pi$;

  2. 2.

All monadically stable classes are sparsifiable (i.e. transduction-equivalent
to some weakly sparse class).

######  Proof 21.9.

(1)$\Rightarrow$(2): Let $\mathscr{C}$ be a monadically stable class, let
$\mathscr{C}^{\downarrow}$ be the set of all transductions of $\mathscr{C}$
and let $\Pi_{s}=\mathscr{C}^{\downarrow}\cap\Sigma$. Obviously,
$\mathscr{C}^{\downarrow}$ is included in the dense analogue of $\Pi_{s}$.
Thus, (1) implies that $\mathscr{C}$ is a transduction of a class
$\mathscr{D}\in\Pi_{s}$, which is itself a transduction of $\mathscr{C}$.
Hence, $\mathscr{C}$ is sparsifiable.

(2)$\Rightarrow$(1): Let $\Pi_{s}$ be a monotone sparse transduction downset
with dense analogue $\Pi$ and let $\mathscr{C}$ be a (monadically) stable
class in $\Pi$. By (2) $\mathscr{C}$ is transduction-equivalent to a weakly
sparse class $\mathscr{D}$. As $\Pi\cap\Sigma=\Pi_{s}$, we have
$\mathscr{D}\in\Pi_{s}$. Hence, $\mathscr{C}\in\Pi_{s}^{\downarrow}$.

For the case where $\Pi_{s}$ is the property of having bounded expansion,
Conjecture 84 restates as follows:

######  Conjecture 86.

If a monadically stable class does not have structurally bounded expansion,
then it has a transduction to a class that is nowhere dense but not bounded
expansion.

######  Proposition 87.

Conjectures 84 and 86 are equivalent.

######  Proof 21.10.

The only direction to prove is that Conjecture 86 implies Conjecture 84.
Assume Conjecture 86 holds and let $\Pi_{s}$ be a sparse transduction downset
of bounded expansion classes with dense analogue $\Pi$. Let $\mathscr{C}$ be a
monadically stable class. If $\mathscr{C}$ does not have structurally bounded
expansion, then there exists a nowhere dense class
$\mathscr{D}\sqsubseteq\mathscr{C}$ that does not have bounded expansion.
Thus, $\mathscr{D}\notin\Pi_{s}$ and $\mathscr{C}\notin\Pi$. Otherwise,
$\mathscr{C}$ is transduction-equivalent to a class $\mathscr{D}$ with bounded
expansion. Then,

$\mathscr{C}\in\Pi\iff\mathscr{D}\in\Pi\iff\mathscr{D}\in\Pi_{s}\iff\mathscr{C}\in\Pi_{s}^{\downarrow}.$

One main difficulty in proving all these conjectures is the non-monotonicity
of the involved classes. The following, if true, would provide a great tool.
Recall that a graph $G$ is _$k$ -degenerate_ if every induced subgraph of $G$
has a minimum degree at most $k$. A class of graphs $\mathscr{C}$ is
_degenerate_ if there exists $k\in\mathbb{N}$ such that all the graphs in
$\mathscr{C}$ are $k$-degenerate.

######  Conjecture 88.

Every weakly sparse non-degenerate class has a transduction to a monotone non-
degenerate class.

######  Conjecture 89.

For every weakly sparse class of graphs $\mathscr{C}$,

  * •

either $\mathscr{C}$ has a transduction to its monotone closure,

  * •

or $\mathscr{C}$ has a transduction to a monotone nowhere dense class with
unbounded fractional chromatic number.

Though Conjecture 89 seems to be stronger than Conjecture 88, this is not the
case.

######  Proposition 90.

Conjectures 88 and 89 are equivalent.

######  Proof 21.11.

On the one hand, Conjecture 89 obviously implies Conjecture 88. On the other
hand, assume Conjecture 88 holds and let $\mathscr{C}$ be a weakly sparse
class of graphs. If $\mathscr{C}$ has bounded expansion or is not monadically
dependent, then $\mathscr{C}$ has a transduction to its monotone closure.
Otherwise, $\mathscr{C}$ is nowhere dense but not bounded expansion. If
$\mathscr{C}$ is degenerate, then it follows from [Dvo18] that $\mathscr{C}$
contains an shallow induced subdivision of graphs with arbitrarily large
minimum degree, thus transduces onto a non-degenerate monotone (monadically
dependent) class. On the other hand, if $\mathscr{C}$ is non-degenerate, we
have the same property according to Conjecture 88. Thus, we can reduce to the
case where $\mathscr{C}$ is a non-degenerate monotone monadically dependent
class. In particular, $\mathscr{C}$ is nowhere dense. Then it follows from
[DOdMW20] that $\mathscr{C}$ contains $1$-subdivisions of graphs with
unbounded fractional chromatic number.

### References

  * [AA14] H. Adler and I. Adler.  Interpreting nowhere dense graph classes as a classical notion of model theory.  European Journal of Combinatorics, 36:322–330, 2014.
  * [AMR92] N. Alon, C. McDiarmid, and B. Reed.  Star arboricity.  Combinatorica, 12:375–380, 1992.
  * [BBGT23] E. Bonnet, R. Bourneuf, C. Geniet, and S. Thomassé.  Factoring pattern-free permutations into separable ones.  arXiv preprint, 2023.
  * [BC10] A. Blumensath and B. Courcelle.  On the monadic second-order transduction hierarchy.  Logical Methods in Computer Science, 6(2), 2010.  doi:10.2168/LMCS-6(2:2)2010.
  * [BCK+22] E. Bonnet, D. Chakraborty, E.J. Kim, N. Köhler, R. Lopes, and S. Thomassé.  Twin-width VIII: delineation and win-wins.  arXiv preprint arXiv:2204.00722, 2022.
  * [BGK+22] E. Bonnet, C. Geniet, E.J. Kim, S. Thomassé, and R. Watrigant.  Twin-width II: small classes.  Combinatorial Theory, 2(2):#10, 2022.  doi:10.5070/C62257876.
  * [BGTT22] E. Bonnet, C. Geniet, R. Tessera, and S. Thomassé.  Twin-width VII: groups.  arXiv preprint arXiv:2204.12330, 2022.
  * [BKTW20] E. Bonnet, E.J. Kim, S. Thomassé, and R. Watrigant.  Twin-width I: tractable FO model checking.  In 61st Annual Symposium on Foundations of Computer Science (FOCS 2020), pages 601–612. IEEE, 2020.
  * [BL22a] S. Braunfeld and M.C. Laskowski.  Existential characterizations of monadic NIP.  arXiv preprint arXiv:2209.05120, 2022.
  * [BL22b] S. Braunfeld and M.C. Laskowski.  Worst-case expansions of complete theories.  Model Theory, 1(1):15–30, 2022.
  * [BNOdM+21] E. Bonnet, J. Nešetřil, P. Ossona de Mendez, S. Siebertz, and S. Thomassé.  Twin-width and permutations.  2021\.
  * [BS85] J. T. Baldwin and S. Shelah.  Second-order quantifiers and the complexity of theories.  Notre Dame Journal of Formal Logic, 26(3):229–303, 1985.
  * [CE12] B. Courcelle and J. Engelfriet.  Graph structure and monadic second-order logic: a language-theoretic approach, volume 138.  Cambridge University Press, 2012.
  * [CO00] B. Courcelle and S. Olariu.  Upper bounds to the clique width of graphs.  Discrete Applied Mathematics, 101(1-3):77–114, 2000.
  * [Col07] T. Colcombet.  A combinatorial theorem for trees.  In International Colloquium on Automata, Languages, and Programming, pages 901–912. Springer, 2007.
  * [Cou90] B. Courcelle.  The monadic second-order logic of graphs. I. Recognizable sets of finite graphs.  Information and computation, 85(1):12–75, 1990.
  * [Cou92] B. Courcelle.  The monadic second-order logic of graphs VII: Graphs as relational structures.  Theoretical Computer Science, 101(1):3–33, 1992.
  * [Die12] R. Diestel.  Graph theory, volume 173 of.  Graduate texts in mathematics, page 7, 2012.
  * [DO95] G. Ding and B. Oporowski.  Some results on tree decomposition of graphs.  Journal of Graph Theory, 20(4):481–499, 1995.  doi:10.1002/jgt.3190200412.
  * [DOdMW20] Z. Dvořák, P. Ossona de Mendez, and H. Wu.  $1$-subdivisions, fractional chromatic number and Hall ratio.  Combinatorica, 40(6):759–774, 2020.  doi:10.1007/s00493-020-4223-9.
  * [Drm15] M. Drmota.  Trees.  In Handbook of Enumerative Combinatorics, pages 281–334. Chapman and Hall/CRC, 2015.
  * [Dvo18] Z. Dvořák.  Induced subdivisions and bounded expansion.  European Journal of Combinatorics, 69:143 – 148, 2018.  doi:10.1016/j.ejc.2017.10.004.
  * [EK63] P. Erdős and P. J. Kelly.  The minimal regular graph containing a given graph.  Amer. Math. Monthly, 70:1074–1075, 1963.
  * [FPST18] G. Fabiański, M. Pilipczuk, S. Siebertz, and S. Toruńczyk.  Progressive algorithms for domination and independence.  arXiv preprint arXiv:1811.06799, 2018.
  * [FV59] S. Feferman and R. Vaught.  The first order properties of products of algebraic systems.  Fundamenta Mathematicae, 47(1):57–103, 1959.
  * [GHN+19] R. Ganian, P. Hliněný, J. Nešetřil, J. Obdržálek, and P. Ossona de Mendez.  Shrub-depth: Capturing height of dense graphs.  Logical Methods in Computer Science, 15, 2019.
  * [GHO+20] J. Gajarský, P. Hliněný, J. Obdržálek, D. Lokshtanov, and M.S. Ramanujan.  A new perspective on FO model checking of dense graph classes.  ACM Transactions on Computational Logic (TOCL), 21(4):1–23, 2020\.
  * [GKN+20] J. Gajarský, S. Kreutzer, J. Nešetřil, P. Ossona de Mendez, M. Pilipczuk, S. Siebertz, and S. Toruńczyk.  First-order interpretations of bounded expansion classes.  ACM Transactions on Computational Logic, 21(4):Article 29, 2020\.  doi:10.1145/3382093.
  * [GKS17] M. Grohe, S. Kreutzer, and S. Siebertz.  Deciding first-order properties of nowhere dense graphs.  Journal of the ACM, 64(3):17:1–17:32, 2017.
  * [GPT22] J. Gajarskỳ, M. Pilipczuk, and S. Toruńczyk.  Stable graphs of bounded twin-width.  In Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science, pages 1–12, 2022.
  * [Gro03] Martin Grohe.  Local tree-width, excluded minors, and approximation algorithms.  Combinatorica, 23(4):613–632, 2003.
  * [GW00a] F. Gurski and E. Wanke.  The Tree-Width of Clique-Width Bounded Graphs without $K_{n,n}$, volume 1928 of Lecture Notes in Computer Science, pages 196–205.  Springer Berlin Heidelberg, 2000.
  * [GW00b] F. Gurski and E. Wanke.  The tree-width of clique-width bounded graphs without $k_{n,n}$.  In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 196–205. Springer, 2000.
  * [Hod93] W. Hodges.  Model theory, volume 42.  Cambridge University Press, 1993.
  * [Las13] M. C. Laskowski.  Mutually algebraic structures and expansions by predicates.  The Journal of Symbolic Logic, 78(1):185–194, 2013.
  * [Lib04] Leonid Libkin.  Elements of Finite Model Theory.  Springer, 2004.
  * [Loz08] V. V. Lozin.  From tree-width to clique-width: Excluding a unit interval graph.  In Seok-Hee Hong, Hiroshi Nagamochi, and Takuro Fukunaga, editors, Algorithms and Computation, pages 871–882, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg.
  * [LT22] M. C. Laskowski and C. A. Terry.  Jumps in speeds of hereditary properties in finite relational languages.  Journal of Combinatorial Theory, Series B, 154:93–135, 2022.
  * [Mak04] J. A. Makowsky.  Algorithmic uses of the Feferman–Vaught theorem.  Annals of Pure and Applied Logic, 126(1-3):159–213, 2004.
  * [NOdM03] J. Nešetřil and P. Ossona de Mendez.  Colorings and homomorphisms of minor closed classes.  In B. Aronov, S. Basu, J. Pach, and M. Sharir, editors, The Goodman-Pollack Festschrift, volume 25 of Algorithms and Combinatorics, pages 651–664. Discrete & Computational Geometry, 2003\.
  * [NOdM05] J. Nešetřil and P. Ossona de Mendez.  The grad of a graph and classes with bounded expansion.  In A. Raspaud and O. Delmas, editors, 7th International Colloquium on Graph Theory, volume 22 of Electronic Notes in Discrete Mathematics, pages 101–106. Elsevier, 2005.  doi:10.1016/j.endm.2005.06.018.
  * [NOdM06] J. Nešetřil and P. Ossona de Mendez.  Linear time low tree-width partitions and algorithmic consequences.  In STOC’06. Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pages 391–400. ACM Press, 2006.  doi:10.1145/1132516.1132575.
  * [NOdM08a] J. Nešetřil and P. Ossona de Mendez.  Grad and classes with bounded expansion I. Decompositions.  European Journal of Combinatorics, 29(3):760–776, 2008.  doi:10.1016/j.ejc.2006.07.013.
  * [NOdM08b] J. Nešetřil and P. Ossona de Mendez.  Grad and classes with bounded expansion I. decompositions.  European Journal of Combinatorics, 29(3):760–776, 2008.
  * [NOdM10a] J. Nešetřil and P. Ossona de Mendez.  From sparse graphs to nowhere dense structures: Decompositions, independence, dualities and limits.  In European Congress of Mathematics, pages 135–165. European Mathematical Society, 2010.  doi:10.4171/077-1/7.
  * [NOdM10b] J. Nešetřil and P. Ossona de Mendez.  Sparse combinatorial structures: Classification and applications.  In R. Bhatia and A. Pal, editors, Proceedings of the International Congress of Mathematicians 2010 (ICM 2010), volume IV, pages 2502–2529, Hyderabad, India, 2010. World Scientific.  URL: http://eproceedings.worldscinet.com/9789814324359/9789814324359_0156.html.
  * [NOdM12] J. Nešetřil and P. Ossona de Mendez.  Sparsity (Graphs, Structures, and Algorithms), volume 28 of Algorithms and Combinatorics.  Springer, 2012.  465 pages.
  * [NOdM17] J. Nešetřil and P. Ossona de Mendez.  Cluster analysis of local convergent sequences of structures.  Random Structures & Algorithms, 51(4):674–728, 2017.
  * [NOdMP+21] J. Nešetřil, P. Ossona de Mendez, M. Pilipczuk, R. Rabinovich, and S. Siebertz.  Rankwidth meets stability.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2014–2033, 2021.  doi:10.1137/1.9781611976465.120.
  * [NOdMRS20] J. Nešetřil, P. Ossona de Mendez, R. Rabinovich, and S. Siebertz.  Linear rankwidth meets stability.  In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, pages 1180–1199, 2020.
  * [Noy15] M. Noy.  Graphs.  In Handbook of Enumerative Combinatorics, pages 397–436. Chapman and Hall/CRC, 2015.
  * [NT00] J. Nešetřil and C. Tardif.  Duality theorems for finite structures (characterising gaps and good characterisations).  Journal of Combinatorial Theory, Series B, 80(1):80–97, 2000.
  * [Pal18] D. Palacín.  An introduction to stability theory.  In Lectures in model theory. 2018.
  * [POdMS22] M. Pilipczuk, P. Ossona de Mendez, and S. Siebertz.  Transducing paths in graph classes with unbounded shrubdepth.  European Journal of Combinatorics, page 103660, 2022.  doi:10.1016/j.ejc.2022.103660.
  * [PT99] A. Proskurowski and J. A. Telle.  Classes of graphs with restricted interval models.  Discrete Mathematics & Theoretical Computer Science, 3, 1999.
  * [PZ78] K.-P. Podewski and M. Ziegler.  Stable graphs.  Fund. Math., 100:101–107, 1978.
  * [RS86] N. Robertson and P. D. Seymour.  Graph minors. V. Excluding a planar graph.  Journal of Combinatorial Theory, Series B, 41(1):92–114, 1986.
  * [She90] S. Shelah.  Classification theory: and the number of non-isomorphic models, volume 92.  Elsevier, 1990.
  * [Sim15] P. Simon.  A guide to NIP theories.  Cambridge University Press, 2015.