# Shallow vertex minors, stability, and dependence

Hector Buffière, Eun Jung Kim, Patrice Ossona de Mendez

► To cite this version:

Hector Buffière, Eun Jung Kim, Patrice Ossona de Mendez. Shallow vertex minors, stability, and dependence. Innovations in Graph Theory, 2024, 1, pp.87 - 112. 10.5802/igt.5. hal-04807086

HAL Id: hal-04807086

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

Submitted on 27 Nov 2024

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 Attribution 4.0 International License
SHALLOW VERTEX MINORS, STABILITY,
AND DEPENDENCE

by Hector BUFFIÈRE,

Eun Jung KIM & Patrice OSSONA DE MENDEZ (*)

ABSTRACT. — *Stability* and *dependence* are model-theoretic notions that have recently proved highly effective in the study of structural and algorithmic properties of hereditary graph classes, and are considered key notions for generalizing to hereditary graph classes the theory of sparsity developed for monotone graph classes (where an essential notion is that of *nowhere dense* class). The theory of sparsity was initially built on the notion of *shallow minors* and on the idea of excluding different sets of minors, depending on the depth at which these minors can appear.

In this paper, we follow a similar path, where *shallow vertex minors* replace shallow minors. In this setting, we provide a neat characterization of stable / dependent hereditary classes of graphs: A hereditary class of graphs $\mathcal{C}$ is *dependent* if and only if it does not contain all permutation graphs and, for each integer $r$, it excludes some split interval graph as a depth-$r$ vertex minor; it is *stable* if and only if, for each integer $r$, it excludes some half-graph as a depth-$r$ vertex minor.

A key ingredient in proving these results is the preservation of stability and dependence of a class when taking bounded depth shallow vertex minors. We extend this preservation result to binary structures and get, as a direct consequence, that bounded depth shallow vertex minors of graphs with bounded twin-width have bounded twin-width.

# 1. Introduction

Graph minors are central to structural graph theory and have been extensively studied by Robertson and Seymour in their *Graph minor project*.

**Keywords:** graph, local complementation, shallow vertex minor, dependence, NIP, stability, twin-width, binary relational structure.

2020 Mathematics Subject Classification: 05C75, 03C13.

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

<footnote>(*) This paper is part of projects that have received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreements No 810115 – DYNASNET).</footnote>
The shallow version of graph minors then allowed to extend some of the
properties of proper minor closed classes of graphs to classes with bounded
expansion and nowhere dense classes, and constitutes the foundation of the
theory of sparsity initiated by Jaroslav Nešetřil and the third author [13].

Vertex minors have been introduced by Oum [16] in his foundational
paper on rank-width. Recall that a graph $H$ is a *vertex-minor* of a graph $G$ if it can be reached from $G$ by the successive application of local com-
plementations and vertex deletions. It appears that vertex minors are a
natural dense analog to graph minors as witnessed, for instance, by the
grid theorem for vertex minors [11].

Shallow vertex minors have been introduced in [15], where it is proved
that shallow vertex minors of graphs in a class with bounded expansion
can be obtained through first-order transductions. This notion is defined
inductively from the one of depth-1 vertex minor. A graph $H$ is a *depth-1
vertex-minor* of a graph $G$ if it can be reached from $G$ by local complemen-
tation of the vertices of an independent set and vertex deletions. In this
paper, we give further evidence that shallow vertex minors are relevant to
the structural study of hereditary graph classes.

It is known that a class is *nowhere dense* if it excludes, for each integer
$r$, some graph (equivalently, some clique) as a depth-$r$ shallow minor and
that, for a monotone class of graphs, being nowhere dense is equivalent to
the model theoretical notions of stability and dependence [1]. Note that
classes excluding a vertex minor are not, in general, dependent. Indeed, as
noticed in [15], if a class is closed under vertex minors, then it is dependent
if and only if it has bounded cliquewidth.

Study of hereditary classes of graphs from the perspective of model the-
ory recently gained a lot of attention, and led to numerous fundamental
results both in structural and algorithmic graph theory. Particularly, stabil-
ity and dependence appeared to play a special role (like in classical model
theory). For instance, it has been proved that first-order model checking is
fixed-parameter tractable on hereditary stable classes of graphs [7], while
it is conjectured that this problem is fixed-parameter tractable on those
hereditary classes of graphs that are dependent. On the dependent but un-
stable regime, it is known that first-order model checking is fixed-parameter
tractable on classes with bounded twin-width [3].

The case of hereditary classes of ordered graphs (that is, of graphs with
a fixed linear order on the vertex set) has been settled.
THEOREM 1.1 ([2]). — For a hereditary class of ordered graphs $\mathcal{C}$, the following are equivalent (assuming FPT $\neq$ AW[*]):

(1) First-order model checking is fixed-parameter tractable on $\mathcal{C}$;

(2) $\mathcal{C}$ has bounded twin-width;

(3) $\mathcal{C}$ is dependent;

(4) $\mathcal{C}$ contains neither the class of all ordered permutation graphs, nor any of 24 special classes encoding ordered matchings.

In the presence of a linear order on the vertex set, a matching can be viewed as a family of intervals and thus naturally defines an interval graph with two sorts of intervals, disjoint “short” intervals for the vertices, and “long” intervals for the matching. In Theorem 1.1, the 24 classes are constructed from perfect matchings between two subsets A and B of vertices with $max A < min B$. This constraint translates to the property that the interval graph associated to the ordered matching is split (See Figure 1.1): its vertex set is the union of an independent set (the vertices) and a clique (the matching). From this point of view, condition ((4)) of Theorem 1.1 excludes the ordered analog of permutation graphs and split interval graphs.

<figure><img src="image_3.png" /><figcaption>Figure 1.1. The split interval graph associated to the matching $M = \{(6, 2), (5, 4), (4, 1), (3, 6), (2, 3), (1, 5)\}$.</figcaption></figure>

In this paper, we provide a full characterization of those hereditary classes of graphs that are stable or dependent classes in terms of excluded shallow vertex minors.

THEOREM 1.2. — Let $\mathcal{C}$ be a hereditary class of graphs. Then, $\mathcal{C}$ is dependent if and only if the class $\mathcal{C}$ does not contain all permutation graphs and, for every integer $r$, the class $\mathcal{C}$ excludes some split interval graph as a depth-$r$ shallow vertex minor.

This characterization (proved in Section 6 as Theorem 6.1) is based on the following graphs:

* a *permutation graph* is a graph with vertex set $[n]$ associated to a permutation $\sigma \in \mathcal{S}_n$, where *ij* is an edge if $(i, j)$ is an inversion of $\sigma$ (i.e. if $(i < j) \leftrightarrow (\sigma(i) > \sigma(j))$);
<figure><img src="image_4.png" /></figure>

* a split interval graph is a graph that is both split (meaning that is vertex set can be partitioned into an independent set and a clique) and an interval graph (i.e. an intersection graph of intervals of the line). See [10] for more on split interval graphs.

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

It is known [14] that stable hereditary classes of graphs are exactly dependent hereditary classes of graphs that do not contain the class of all half-graphs. This is a key ingredient in proving the next characterization.

**THEOREM 1.3.** — Let $\mathcal{C}$ be a hereditary class of graphs. Then, $\mathcal{C}$ is stable if and only if, for every integer $r$, the class $\mathcal{C}$ excludes some half-graph as a depth-$r$ shallow vertex minor.

This characterization (proved in Section 6 as Theorem 6.3) is based on the following graphs:

* the half-graph of order $n$ has vertices $a_1, \dots, a_n, b_1, \dots, b_n$ and edges $a_ib_j$ where $i \le j$;

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

The paper is organized as follows: In Section 2 we give some preliminaries on flips, local complementation, and shallow vertex minors. In Section 3 we analyze in what sense flip and local complementation commute. After recalling the properties of dependence and stability in Section 4, we prove that these properties are preserved by taking shallow vertex minors, and deduce in Section 6 our characterization theorems. In Section 7, we discuss generalization of the results of Section 4 to binary relational structures.
## 2. Flips, local complementations, and shallow vertex minors

### 2.1. Flips

In this paper, it will be convenient to consider that the adjacency relation $E_G$ of a graph $G$ has value in $\mathbb{F}_2$, with $E_G(u, v) = 1$ if $u$ and $v$ are adjacent. This will allow us to use the standard arithmetic operations of $\mathbb{F}_2$.

A k-flip on a set $V$ is a pair $F = (\iota, \tau)$, where $\iota: V \to [k]$ and $\tau: [k] \times [k] \to \mathbb{F}_2$ is a symmetric function (i.e. $\tau(i, j) = \tau(j, i)$ for all $i, j \in [k]$). Given a flip $F$ on $V(G)$, the graph $G \oplus F$ has the same vertex set as $G$, and its adjacency relation is defined by

$$ (2.1) \qquad E_{G \oplus F}(x, y) = E_G(x, y) + \tau(\iota(x), \iota(y)). $$

Each flip $F$ on $V(G)$ induces a partition of $V(G)$ into $k$ (possibly empty) parts $\iota^{-1}(1), \dots, \iota^{-1}(k)$, also called $F$-classes. More generally, for a subset $X$ of $V(G)$, the flip $F$ induces a partition of $X$ into parts $\iota^{-1}(1) \cap X, \dots, \iota^{-1}(k) \cap X$, the $F$-classes of $X$.

If $G$ is a graph and $F = (\iota, \tau)$ is a k-flip on a set $X \supseteq V(G)$, then $F$ naturally defines a k-flip on $V(G)$ by considering the restriction of $\iota$ to $V(G)$. By abuse of notation, we still denote $G \oplus F$ the graph obtained by applying the restricted k-flip.

A subset $X$ of vertices of $G$ is $F$-homogeneous if the adjacency of any two distinct vertices $u, v \in X$ depends only on $\iota(u)$ and $\iota(v)$. The trace of a set $Y$ on a set $X$ is the intersection $X \cap Y$. A flip $F'$ on $V(G)$ is $X$-compatible with $F$ if the (non-empty) traces on $X$ of the parts of $F'$ are the same as the (non-empty) traces on $X$ of the parts of $F$. It is immediate that $X$ is $F$-homogeneous if and only if there exists a flip $F'$ on $V(G)$ that is $X$-compatible with $F$ and such that $X$ is an independent set of $G \oplus F \oplus F'$.

### 2.2. Local complementations

Let $G$ be a graph and let $v$ be a vertex of $G$, the graph obtained from $G$ by local complementation of $v$ is the graph $G * v$ with same vertex set as $G$, with adjacency relation defined by

$$ (2.2) \qquad E_{G * v}(x, y) = E_G(x, y) + E_G(x, v) \cdot E_G(v, y). $$

If $u$ and $v$ are adjacent, pivoting the edge $uv$ is the operation obtained by successive local complementation of $u, v$, and $u: G \wedge uv = G * u * v * u$
($=G*v*u*v$). This operation flips the edges between the private neighbors of $u$, the private neighbors of $v$, and the common neighbors of $u$ and $v$, and then exchanges $u$ and $v$. Thus, if $x, y$ are distinct vertices different from $u$ and $v$, it is easily checked that

$$ (2.3) \quad E_{G \land uv}(x, y) = E_G(x, y) + E_G(x, u) \cdot E_G(y, v) + E_G(x, v) \cdot E_G(y, u). $$

If $I = \{v_1, \dots, v_k\}$ is an independent set, then $G * v_1 * \dots * v_k = G * v_{\sigma(1)} * \dots * v_{\sigma(n)}$ for every permutation $\sigma$ of $[k]$. This justifies the notation $G * I$ for the graph obtained from $G$ by successive local complementation of all the vertices in the independent set $I$. Note that we will consider the notation $G * X$ faulty if $X$ is not independent in $G$. It immediately follows from (2.2) that if $I$ is an independent set of a graph $G$, then the adjacency relation of $G * I$ is

$$ (2.4) \quad E_{G*I}(x, y) = E_G(x, y) + \sum_{v \in I} E_G(x, v) \cdot E_G(v, y). $$

A depth 1 vertex minor of a graph $G$ is an induced subgraph of $G*I$, for some independent set $I$ of $G$. We denote by $\text{svm}_1(G)$ the set of all the depth 1 vertex minors of $G$ and, more generally, by $\text{svm}_1(\mathscr{C})$ the set of all the depth 1 vertex minors of graphs in $\mathscr{C}$. We further define inductively depth $c$ vertex minors (for positive integers $c > 1$) as depth 1 vertex minors of depth $(c-1)$ vertex minors. Also, it will be convenient to consider that depth 0 vertex minors are simply induced subgraphs. We consequently extend the notations $\text{svm}_1(G)$ and $\text{svm}_1(\mathscr{C})$ to depth $c$ vertex minors, as $\text{svm}_c(G)$ and $\text{svm}_c(\mathscr{C})$.

For a graph $G$ and a vertex $v$ (resp. a subset $D$ of vertices of $G$), we denote by $G - v$ (resp. $G - D$) the induced subgraph of $G$ obtained by deleting $v$ (resp. $D$). Thus, a depth-1 vertex minor of $G$ has the form $G * I - D$, for some (possibly empty) independent set $I$ and some (possibly empty) subset $D$ of vertices. It is immediate that if $u$ and $v$ are (distinct) vertices of $G$, then $(G - u) * v = (G * v) - u$. Thus, for $c \ge 1$, depth-$c$ shallow vertex minors of $G$ are graphs of the form $G * I_1 * \dots * I_c - D$, where $I_i$ is an independent set of $G * I_1 * \dots * I_{i-1}$ and $D$ is a subset of vertices.

### 3. Commuting flips and vertex minors

Flips and local complementations do not commute in general. However, we shall see that the composition of a flip by a shallow vertex minor operation can be rewritten as the composition of a shallow vertex minor operation and a flip (and vice versa).
We start our study by a special case, considering the graph $G \oplus F * I$, where $I$ is an independent set of both $G$ and $G \oplus F$. The general case, proved in Lemma 3.6 for convenience, is not needed for the main results of this paper.

LEMMA 3.1. — Let $I$ be an independent set of a graph $G$ and let $F = (\iota, \tau)$ be a $k$-flip on $V(G)$. If $I$ is independent in $G \oplus F$, then there exists a $k2^k$-flip $F'$ on $V(G)$ such that

$$G * I \oplus F' = G \oplus F * I.$$

Proof. — We have

$$E_{G*I}(u, v) = E_G(u, v) + \sum_{z \in I} E_G(u, z) \cdot E_G(z, v).$$

As $I$ is an independent set in $G \oplus F$,

$$ \begin{aligned} E_{G \oplus F*I}(u, v) &= E_{G \oplus F}(u, v) + \sum_{z \in I} (E_{G \oplus F}(u, z) \cdot E_{G \oplus F}(z, v)) \\ &= E_G(u, v) + \tau(\iota(u), \iota(v)) \\ &\quad + \sum_{z \in I} ((E_G(u, z) + \tau(\iota(u), \iota(z))) \cdot (E_G(v, z) + \tau(\iota(v), \iota(z)))) \end{aligned} $$

For $i, j \in [k]$ and $u \in V(G)$ we define

$$\zeta(i, j) = \sum_{z \in I} \tau(i, \iota(z)) \cdot \tau(j, \iota(z))$$

$$\zeta(u, i) = \sum_{z \in I} E_G(u, z) \cdot \tau(i, \iota(z)).$$

Then,

$$E_{G \oplus F*I}(u, v) = E_{G*I}(u, v) + \tau(\iota(u), \iota(v)) \\ + \zeta(\iota(u), \iota(v)) + \zeta(u, \iota(v)) + \zeta(v, \iota(u)).$$

Define $\tau' : ([k] \times \{0, 1\}^k) \times ([k] \times \{0, 1\}^k) \to \mathbb{F}_2$ and $\iota' : V(G) \to [k] \times \{0, 1\}^{[k]}$ (where $\{0, 1\}^{[k]}$ is interpreted as the set of all functions from $[k]$ to $\{0, 1\}$) by

$$\tau'((i, \alpha), (j, \beta)) = \tau(i, j) + \zeta(i, j) + \alpha(j) + \beta(i)$$

$$\iota'(v) = (\iota(v), \zeta(v, \cdot)).$$

Then $(\tau', \iota')$ defines a $k2^k$-flip $F'$ on $V(G)$ such that $E_{G \oplus F*I}(u, v) = E_{G*I}(u, v) + \tau'(\iota'(u), \iota'(v))$. $\square$
In our study, it will be important to keep some subset of vertices independent while performing a flip. The next lemma shows how to handle such a condition.

**LEMMA 3.2.** — Let $I$ be an independent set of a graph $G$ and let $F = (\iota, \tau)$ be a $k$-flip on $V(G)$. Then, there exists a $2k$-flip $F'$ on $V(G)$ such that $G \oplus F'$ is obtained from $G \oplus F$ by removing all the edges between vertices of $I$.

*Proof.* — Define $\iota': V(G) \to [k] \times \{0, 1\}$ by $\iota'(v) = (\iota(v), 1)$ if $v \in I$ and $\iota'(v) = (\iota(v), 0)$, otherwise. Define $\tau'$ by $\tau'((i, a), (j, b)) = \tau(i, j)$ if $(a, b) \neq (1, 1)$ and $\tau'((i, a), (j, b)) = 0$, otherwise. Let $F' = (\tau', \iota')$. Then, if $u$ and $v$ do not both belong to $I$, we have $E_{G \oplus F'}(u, v) = E_{G \oplus F}(u, v)$. However, if both $u$ and $v$ belong to $I$, we have $E_{G \oplus F'}(u, v) = E_G(u, v) = 0$. $\square$

The next lemma expresses that distances cannot be arbitrarily shrunk in a shallow vertex minors.

**LEMMA 3.3.** — Let $H \in \text{svm}_1(G)$ and let $x, y \in V(H)$. Then, $\text{dist}_H(x, y) \ge \frac{1}{2} \text{dist}_G(x, y)$.

*Proof.* — Let $H = G * I - D$. Assume $\text{dist}_H(x, y) = 1$. Then, either $\text{dist}_G(x, y) = 1$ or some edge between $x$ and $y$ has been created by the local complementation of the vertices in $I$. In this later case, $x$ and $y$ have a common neighbor in $I$ hence $\text{dist}_G(x, y) = 2$. Generally, considering a shortest path between $x$ and $y$ in $H$, we deduce $\text{dist}_H(x, y) \ge \frac{1}{2} \text{dist}_G(x, y)$. $\square$

The next lemma, which is a direct consequence of Lemmas 3.1, 3.2 and 3.3, will be the key to the preservation theorems proved in Section 5.

**LEMMA 3.4.** — Let $F$ be a $k$-flip on $V(G)$ and let $I$ be an independent set of $G$. Then, there exists a $2k2^{2k}$-flip $F'$ on $V(G)$ such that, for every two vertices $x, y$ in $V(G)$ we have

$$ (3.1) \qquad \text{dist}_{G*I \oplus F'}(x, y) \ge \frac{1}{2} \text{dist}_{G \oplus F}(x, y). $$

*Proof.* — According to Lemma 3.2 there exists a $2k$-flip $\hat{F}$ such that $\text{dist}_{G \oplus \hat{F}} \ge \text{dist}_{G \oplus F}$ and $I$ is independent in $G \oplus \hat{F}$. By Lemma 3.1 there exists a $(2k)2^{2k}$-flip $F'$ such that $G * I \oplus F' = G \oplus \hat{F} * I$. According to Lemma 3.3, for every $x, y \in V(G)$, we have

$$ \text{dist}_{G*I \oplus F'}(x, y) = \text{dist}_{G \oplus \hat{F}*I}(x, y) \ge \frac{1}{2} \text{dist}_{G \oplus \hat{F}}(x, y) \ge \frac{1}{2} \text{dist}_{G \oplus F}(x, y). \quad \square $$

<figure><img src="image_7.png" /></figure>
We end this section with an extension of Lemma 3.1, which will not be needed in the remaining of the paper (and thus can be safely skipped). Nevertheless, it seemed to us that this result, which clarifies the relationships between flip and shallow vertex minors, has an independent interest that justifies its inclusion here.

For a class $\mathscr{C}$ and an integer $k$, we denote by $\text{Flip}_k(\mathscr{C})$ the class of all the graphs $G \oplus F$, where $F$ is a $k$-flip.

**PROPOSITION 3.5.** — For every integer $k$, there exist integers $k'$, $c$ such that

$$ \text{svm}_1(\text{Flip}_k(\mathscr{C})) \subseteq \text{Flip}_{k'}(\text{svm}_c(\mathscr{C})) \\ \text{and } \text{Flip}_k(\text{svm}_1(\mathscr{C})) \subseteq \text{svm}_c(\text{Flip}_{k'}(\mathscr{C})). $$

The proof of this proposition will follow from the next technical lemma.

**LEMMA 3.6.** — There exists a function $F(k)$ (basically, a tower of height $k$) such that for every graph $G$, every independent set $I$ of $G$, and every $k$-flip $F = (\iota, \tau)$ on $V(G)$ there exists a partition $J_1, \dots, J_p$ of $I$ into at most $2k$ parts and an $F(k)$-flip $F'$ on $V(G)$ such that

$$ G * I \oplus F' = G \oplus F * J_1 * \cdots * J_p. $$

*Proof.* — First, note that $I$ is $F$-homogeneous in $G \oplus F$ as it is independent in $G$. We prove the lemma by induction on the number $k$ of $F$-classes of $I$. We allow $I$ to be empty, so that the base case, $k = 0$, obviously holds.

Assume that the lemma when the number of $F$-classes of $I$ is at most $k \ge 0$, and let $I$ be an independent set with $(k+1)$ $F$-classes, denoted $I_1, \dots, I_{k+1}$.

* Assume $I_1$ is independent in $G \oplus F$.

▷ Claim 1. — There exists a $k2^k$-flip $F'$ that is $I$-compatible with $F$, such that $G * I_1 \oplus F' = G \oplus F * I_1$ and $I \setminus I_1$ is $F'$-homogeneous in $G * I_1$.

*Proof of the claim.* As $I_1$ is an $F$-class of $I$, we have $I_1 \subseteq \iota^{-1}(i_0) \cap I$ for some $i_0 \in [k]$. As $I$ is $F$-homogeneous, there exists a symmetric function $f: [k] \times [k] \to \mathbb{F}_2$ such that, for $x, y \in I$, we have $E_G(x, y) = f(\iota(x), \iota(y))$. Thus, if $v \in I_1$ and $i \in [k]$, we have

$$ \begin{align*} \varsigma(v, i) &= \sum_{z \in I_1} E_G(v, z) \cdot \tau(i, \iota(z)) \\ &= \sum_{z \in I_1} f(\iota(v), i_0) \cdot \tau(i, i_0) \\ &= |I_1| \cdot f(\iota(v), i_0) \cdot \tau(i, i_0), \end{align*} $$
where $|I_1|$ is meant as the cardinal of $I_1$ counted in $\mathbb{F}_2$, that is the parity of $|I_1|$. It follows that $\varsigma(v, \cdot)$ is a function of $\iota(v)$, thus $F$ and $F'$ are $I$-compatible.

Let $u, v$ be distinct vertices in $I \setminus I_1$. As $I$ is $F$-homogeneous in $G$ we have

$$ 
\begin{aligned}
E_{G*I_1}(u, v) &= E_G(u, v) + \sum_{z \in I_1} E_G(u, z) \cdot E_G(z, v) \\
&= f(\iota(u), \iota(v)) + |I_1| \cdot f(\iota(u), i_0) \cdot f(\iota(v), i_0).
\end{aligned}
$$

Thus, $I \setminus I_1$ is $F'$-homogeneous in $G * I_1$. $\triangleleft$

As $F'$ is $I$-compatible with $F$, $I_2, \dots, I_{k+1}$ are the $k$ $F'$-classes of $I \setminus I_1$ in $G * I_1$. By induction, there exist $J_1, \dots, J_p$ and a flip $F''$ such that

$$ (G * I_1) * (I \setminus I_1) \oplus F'' = (G * I_1) \oplus F' * J_1 * \dots * J_p. $$

Hence,

$$ 
\begin{aligned}
G * I \oplus F'' &= (G * I_1) * (I \setminus I_1) \oplus F'' \\
&= (G * I_1) \oplus F' * J_1 * \dots * J_p \\
&= G \oplus F * I_1 * J_1 * \dots * J_p,
\end{aligned}
$$

which has the desired form, as $\{I_1, J_1, \dots, J_p\}$ is a partition of $I$ with $p+1 \le 2(k+1)$ parts.

* Otherwise, $I_1$ is not independent in $G \oplus F$.

Then, $I_1$ is a clique of size at least two of $G \oplus F$. We split $I_1$ into a singleton $\{a_1\}$ and $I_1 \setminus \{a_1\}$. According to the above, there exists a $k2^k$-flip $F'$ that is $I$-compatible with $F$ such that

$$ G * a_1 \oplus F' = G \oplus F * a_1 $$

and $I \setminus \{a_1\}$ is $F'$-homogeneous in $G * a_1$. As $F'$ is $I$-compatible with $F$, $I_1 \setminus \{a_1\}$, $I_2, \dots, I_{k+1}$ are the $F'$-classes of $I \setminus I_1$. As $I_1$ is a clique in $G \oplus F$, $I_1 \setminus \{a_1\}$ is independent in $G \oplus F * a_1 = G * a_1 \oplus F'$. Hence, according to Claim 1, there exists a $(k2^k)2^{k2^k}$-flip $F''$ that is $I \setminus \{a_1\}$-compatible with $F'$ such that

$$ (G * a_1) * (I_1 \setminus \{a_1\}) \oplus F'' = (G * a_1) \oplus F' * (I_1 \setminus \{a_1\}). $$

Moreover, as $F''$ is $I \setminus \{a_1\}$-compatible with $F'$, $I_2, \dots, I_p$ are the $k$ $F''$-classes of $I \setminus I_1$ in $G * I_1$.

By induction, there exist $J_1, \dots, J_p$ and a flip $F'''$ such that

$$ (G * I_1) * (I \setminus I_1) \oplus F''' = (G * I_1) \oplus F'' * J_1 * \dots * J_p. $$
Hence,

$$
\begin{align*}
G * I \oplus F''' &= (G * I_1) * (I \setminus I_1) \oplus F''' \\
&= (G * I_1) \oplus F'' * J_1 * \cdots * J_p \\
&= (G * a_1) * (I_1 \setminus \{a_1\}) \oplus F'' * I_1 * J_1 * \cdots * J_p \\
&= (G * a_1) \oplus F' * (I_1 \setminus \{a_1\}) * J_1 * \cdots * J_p \\
&= G \oplus F * a_1 * (I_1 \setminus \{a_1\}) * J_1 * \cdots * J_p,
\end{align*}
$$

which has the desired form, as {{a_1}, (I_1 \setminus {a_1}), J_1, \dots, J_p} is a
partition of I with p + 2 \\ \le 2(k + 1) parts.

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

*Proof of Proposition 3.5.* — Proposition 3.5 immediately follows from
the next two claims.

▷ Claim 2. — Let $F = (\iota, \tau)$ be a $k$-flip of $G$ and let $I$ be an independent set of $G \oplus F$. Then, there exists a partition $I_1, \dots, I_p$ of $I$ into at most $2k$ parts and an $F(k)$-flip $F'$ on $V(G)$ such that

$$
G * I_1 * \cdots * I_p \oplus F' = G \oplus F * I.
$$

*Proof of the claim.* Applying Lemma 3.6 to $G \oplus F$, we obtain a partition $I_1, \dots, I_p$ of $I$ into at most $2k$ parts and an $F(k)$-flip $F'$ on $V(G)$ such that

$$
(G \oplus F) * I \oplus F' = (G \oplus F) \oplus F * I_1 * \cdots * I_p.
$$

As flips are involutive, we deduce $G * I_1 * \cdots * I_p \oplus F' = G \oplus F * I$. $\triangleleft$

▷ Claim 3. — Let $F = (\iota, \tau)$ be a $k$-flip of $G$ and let $I$ be an independent set of $G$. Then, there exists a partition $I_1, \dots, I_p$ of $I$ into at most $2k$ parts and an $F(k)$-flip $F'$ on $V(G)$ such that

$$
G \oplus F' * I_p * \cdots * I_1 = G * I \oplus F.
$$

*Proof of the claim.* Note that *I* is an independent set of *G* * *I* as well.
Applying Lemma 3.6 to *G* * *I*, we obtain a partition *I*₁, ..., *I*ₚ of *I* into at
most 2k parts and an *F*(k)-flip *F*′ on *V*(*G*) such that

$$
(G * I) * I \oplus F' = (G * I) \oplus F * I_1 * \cdots * I_p.
$$

As local complementations are involutive, we deduce $G \oplus F' * I_p * \cdots * I_1 = G * I \oplus F$. $\triangleleft$

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

<figure><img src="image_10.png" /></figure>
4. Dependence and Stability

The notions of dependence (or NIP) and stability are central to the classification theory in Model Theory. Let $\mathscr{C}$ be a class of graphs and let $\varphi(\bar{x}; \bar{y})$ be a first-order partitioned formula, that is a first-order formula whose free variables are partitioned into two tuples (here $\bar{x}$ and $\bar{y}$).

The formula $\varphi$ is unstable on $\mathscr{C}$ if, for every integer $n$ there exists a graph $G \in \mathscr{C}$ and tuples $\bar{a}_1, \dots, \bar{a}_n, \bar{b}_1, \dots, \bar{b}_n$ of vertices of $G$ such that $G \models \varphi(\bar{a}_i, \bar{b}_j)$ if and only if $i \le j$. A class $\mathscr{C}$ is stable if no formula is unstable on $\mathscr{C}$.

The formula $\varphi$ is *independent* on $\mathscr{C}$ if, for every integer $n$ there exists a graph $G \in \mathscr{C}$ and tuples $\bar{a}_1, \dots, \bar{a}_n, \bar{b}_0, \dots, \bar{b}_{[n]}$ of vertices of $G$ such that $G \models \varphi(\bar{a}_i, \bar{b}_J)$ if and only if $i \in J$. A class $\mathscr{C}$ is *dependent* (or NIP) if no formula is independent on $\mathscr{C}$.

We illustrate this notion by an example:

*Example 4.1.* — The class of split interval graphs is independent.

*Proof.* — Consider the following formulas.

$$ \nu(x) := \exists y (\neg(x = y) \land \forall z (E(x, z) \leftrightarrow E(y, z))) $$

$$ \eta(x) := \neg\nu(x) \land \forall y (\nu(y) \rightarrow \neg E(x, y)) $$

$$ \mu_{\nu}(x, y) := E(x, y) \land \forall z ((\nu(z) \land E(z, y)) \rightarrow (\forall t E(x, t) \rightarrow E(z, t))) $$

$$ \mu_{\eta}(x, y) := E(x, y) \land \forall z ((\eta(z) \land E(z, y)) \rightarrow (\forall t E(x, t) \rightarrow E(z, t))) $$

$$ \varphi(x, y) := \exists z (\mu_{\nu}(x, z) \land \mu_{\eta}(y, z)) $$

These formulas will be used on the following construction of a split interval graph $G$ (See Figure 4.1). Let $n > 1$ be an integer. We consider $2n + 2^n$ non-intersecting intervals $a_1, a'_1, \dots, a_n, a'_n, b_{[n]}, \dots, b_{\{1\}}, b_0$ in this order (the subsets of $[n]$ being ordered in reverse lexicographic order). We add an interval from $a_1$ to $a'_n$ then, for each $i \in [n]$ and each $J \subseteq [n]$ containing $i$, we add an interval from $a_i$ to $b_J$. The formula $\nu(x)$ expresses that $x$ has a false twin. Hence, $\nu(G) = \{a_1, \dots, a_n, a'_1, \dots, a'_n\}$. The formula $\eta$ allows defining the remaining of the stable part of $G$: $\eta(G) = \{b_0, \dots, b_{\{1, \dots, n\}}\}$. The formula $\mu_{\nu}(x, y)$ expresses that $x$ is the leftmost interval in $\nu(G)$ that is adjacent to $y$, while $\mu_{\eta}(x, y)$ expresses that $x$ is the rightmost interval in $\eta(G)$ that is adjacent to $y$. Finally, we easily check that $G \models \phi(a_i, b_J)$ if and only if $i \in J$. Hence, $\phi$ is independent on the class of split interval graphs. $\square$

We can also consider monadic expansions of graphs, that is, relational structures with a single binary relation and finitely many unary predicates,
<figure><img src="image_11.png" /><figcaption>Figure 4.1. Encoding a power graph in a split interval graph. We have $\varphi(a_i, b_J) \leftrightarrow i \in J$.</figcaption></figure>

which can be seen as vertex-colored graphs. A class $\mathcal{C}'$ is a monadic expansion of a class of graphs $\mathcal{C}$ if the class $\mathcal{C}$ is obtained from $\mathcal{C}'$ by “forgetting” the unary predicates. A class $\mathcal{C}$ is monadically stable (resp. monadically dependent) if every monadic expansion of $\mathcal{C}$ is stable (resp. dependent). For hereditary classes of graphs, the monadic and non-monadic version collapse:

**THEOREM 4.2 ([5]).** — Let $\mathcal{C}$ be a hereditary class of graphs. Then $\mathcal{C}$ is dependent if and only if it is monadically dependent, and it is stable if and only if it is monadically stable.

As a direct consequence, we have

**COROLLARY 4.3.** — Let $\mathcal{C}$ be a class of graphs. Then $\mathcal{C}$ is monadically dependent if and only if the hereditary closure of $\mathcal{C}$ is dependent, and it is monadically stable if and only if the hereditary closure of $\mathcal{C}$ is stable.

Recently, several characterization theorems have been given for stable and dependent hereditary classes. We shall make use of two types of characterizations.

The first type of characterizations is based on the possibility to push vertices far away by means of a flip.

**THEOREM 4.4 ([8]).** — A class $\mathcal{C}$ is monadically stable if and only if for every radius $r$, there exists an integer $k$ and an unbounded non-decreasing function $U: \mathbb{N} \to \mathbb{N}$ such that for every $G \in \mathcal{C}$ and every $A \subseteq V(G)$ there exists a $k$-flip $F$ and a subset $S \subseteq A$ with $|S| \ge U(|A|)$ and any two vertices in $S$ are pairwise at distance at least $r$ in $G \oplus F$.

**THEOREM 4.5 ([9, Theorem 1.3]).** — A class $\mathcal{C}$ is monadically dependent if and only if for every radius $r$, there exists an integer $k$ and an unbounded non-decreasing function $U: \mathbb{N} \to \mathbb{N}$ such that for every $G \in \mathcal{C}$ and every $A \subseteq V(G)$ there exists a $k$-flip $F$ and subsets $A_1, A_2 \subseteq A$ with $|A_1|, |A_2| \ge U(|A|)$ and any vertex in $A_1$ is at distance at least $r$ in $G \oplus F$ to vertices in $A_2$.
The second type of characterization is structural.

**THEOREM 4.6** ([9, Theorem 1.6]). — Let $\mathcal{C}$ be a graph class. Then $\mathcal{C}$ is monadically dependent if and only if for every $r \ge 1$ there exists $n \in \mathbb{N}$ such that $\mathcal{C}$ excludes as induced subgraphs

• all flipped star $r$-crossings of order $n$, and

• all flipped clique $r$-crossings of order $n$, and

• all flipped half-graph $r$-crossings of order $n$, and

• the comparability grid of order $n$.

We take time to define the families of graphs used in Theorem 4.6. Let $r$ be a positive integer.

• A star $r$-crossings of order $n$ (Figure 4.2b) is the $r$-subdivision of $K_{n,n}$. It consists of principle vertices $a_1, \dots, a_n$ and $b_1, \dots, b_n$ and internally vertex-disjoint paths $P_{i,j}$ ($i, j \in [n]$) with vertices $p_{i,j,k}$ (with $0 \le k \le r+1$ monotone on the path), where $p_{i,j,0} = a_i$ and $p_{i,j,r+1} = b_j$.

• A clique $r$-crossings of order $n$ (Figure 4.2c) is the graph obtained from a star $r$-crossings of order $n$ by making the neighborhood of each principal vertex complete.

• A half-graph $r$-crossings of order $n$ (Figure 4.2d) is the graph obtained from a star $r$-crossings of order $n$ by making adjacent the vertices $a_i$ and $p_{i',j,1}$ whenever $i' \ge i$ and the vertices $b_j$ and $p_{i,j',r}$ whenever $j' \ge j$.

A flipped star $r$-crossings (resp. clique $r$-crossing, half-graph $r$-crossings) of order $n$ is the graph obtained from a star $r$-crossings (resp. a clique $r$-crossing, a half-graph $r$-crossings) of order $n$ by applying a flip based on the partitions with parts $\{p_{i,j,k}: i, j \in [n]\}$, for $0 \le k \le r+1$, which we call the flip-parts.

• Finally, the comparability grid of order $n$ (Figure 4.2a) has vertex set $\{a_{i,j}: i, j \in [n]\}$, with $a_{i,j}$ adjacent to $a_{i',j'}$ whenever $i = i'$, $j = j'$, or $(i < j) \leftrightarrow (i' < j')$.
<figure><img src="image_12.png" /><figcaption>Figure 4.2. The forbidden induced configurations. Figures 4.2b–4.2d: the flipped versions are obtained by applying an $r+2$-flip whose parts are materialized as horizontal lines of vertices.</figcaption></figure>

The next easy lemma will be useful.

**LEMMA 4.7.** — Let $G$ be a graph, let $F = (\iota, \tau)$ be a $k$-flip on $V(G)$, and let $I$ be an independent set of $G$ containing exactly one element of each $F$-class.

Then, there exist $z_1, \dots, z_p$ in $I$ with $p \le 3k/2$ (where each element of $I$ is used at most twice), such that

$$ (4.1) \qquad G \oplus F * z_1 * \cdots * z_p - N_G[I] = G - N_G[I], $$

where $N_G[I]$ denotes the closed neighborhood of $I$ in $G$.

*Proof.* — Let $X = \{i \in [k] : \exists j \in [k], \tau(i, j) = 1\}$. We prove a strengthening of the lemma statement by induction on $|X|$, where we require that $\iota(z_i) \in X$ for all $i \in [p]$.

The base case is $X = \emptyset$, in which case $G \oplus F = G$, so we can let $p = 0$.

Assume we have proved the induction hypothesis for $|X| \le \ell$ (where $\ell \ge 0$) and let $|X| = \ell + 1$.
Assume there exists $a \in X$ with $\tau(a, a) = 1$, and let $z$ be the element in $I$ with $\iota(z) = a$. Then, for $u, v \notin N_G[z]$,

$$ 
\begin{align*}
E_{G \oplus F \ast z}(u, v) &= E_G(u, v) + \tau(\iota(u), \iota(v)) \\
&\quad + ((E_G(u, z) + \tau(\iota(u), a)) \cdot ((E_G(v, z) + \tau(\iota(v), a)) \\
&= E_G(u, v) + \tau(\iota(u), \iota(v)) + \tau(\iota(u), a) \cdot \tau(\iota(v), a) \\
&= E_{G \oplus F'}(u, v),
\end{align*}
$$

where $F' = (\iota, \tau')$ and $\tau'(i, j) = \tau(i, j) + \tau(i, a) \cdot \tau(j, a)$. In particular, $\tau'(a, i) = 0$ for all $i \in [k]$. Thus, the result follows from the induction hypothesis.

Otherwise, let $a \in X$. As $\tau(a, a) = 0$, there exists $b \neq a$ in $X$ with $\tau(a, b) = 1$. Note that $\tau(b, b) = 0$. Let $z$ (resp. $z'$) be the element of $I$ with $\iota(z) = a$ (resp. $\iota(z') = b$). Then, $zz'$ is an edge of $G \oplus F$, and we have, for $u, v \notin N_G[z, z']$,

$$ 
\begin{align*}
E_{G \oplus F \ast z \ast z' \ast z}(u, v) \\
&= E_{G \oplus F \wedge z z'}(u, v) \\
&= E_G(u, v) + \tau(\iota(u), \iota(v)) \\
&\quad + (E_G(u, z) + \tau(\iota(u), \iota(z))) \cdot (E_G(v, z') + \tau(\iota(v), \iota(z')) \\
&\quad + (E_G(u, z') + \tau(\iota(u), \iota(z')) \cdot (E_G(v, z) + \tau(\iota(v), \iota(z))) \\
&= E_G(u, v) + \tau(\iota(u), \iota(v)) \\
&\quad + \tau(\iota(u), a) \cdot \tau(\iota(v), b) + \tau(\iota(u), b) \cdot \tau(\iota(v), a) \\
&= E_{G \oplus F'}(u, v),
\end{align*}
$$

where $F' = (\iota, \tau')$ and $\tau'(i, j) = \tau(i, j) + \tau(i, a) \cdot \tau(j, b) + \tau(i, b) \cdot \tau(j, a)$. In particular, $\tau'(a, i) = 0$ and $\tau'(b, i) = 0$ for all $i \in [k]$. Thus, the statement follows from the induction hypothesis. $\square$

The next lemma shows how to reduce subdivisions.

**LEMMA 4.8.** — Let $G$ be a subdivision of a graph $H$, where every edge is subdivided at most $r$ times. Then, $H$ is a depth-$\lceil \log_2(r+1) \rceil$ vertex minor of $G$.

*Proof.* — Let $S = V(G) \setminus V(H)$ be the set of all the subdivision vertices of $G$, and let $I \subseteq S$ be an independent set of maximal possible cardinal. Note that if an edge $uv$ of $H$ is subdivided $k \le r$ times in $G$, then $I$ contains $\lceil k/2 \rceil$ of these subdivision vertices, and thus $G \ast I - I$ is a subdivision of $H$, where each edge is subdivided at most $\lceil r/2 \rceil$ times. By induction, $H$ is
a depth-$c$ vertex minor of $G * I - I$, where $2^{c-1} + 1 \le \lfloor r/2 \rfloor + 1 \le 2^c$, i.e. if $2^c + 1 \le r + 1 \le 2^{c+1}$. Hence, $H$ is a depth-$\lceil \log_2(r+1) \rceil$ vertex minor of $G$. $\square$

It will be helpful to consider the following graphs instead of split interval graphs: the *matchmaking graph* associated to a matching $M \subset [n] \times [n]$ is the graph with vertex set $\{a_i : i \in [n]\} \cup \{b_j : j \in [n]\} \cup M$, where $(k, \ell) \in M$ is adjacent to $a_i$ if $i \le k$ and to $b_j$ if $j \le \ell$ (See Figure 4.3).

<figure><img src="image_13.png" /><figcaption>Figure 4.3. matchmaking graph associated to the (ordered) matching $M = \{(1,5), (2,3), (3,6), (4,1), (5,4), (6,2)\}$.</figcaption></figure>

**LEMMA 4.9.** — Every split interval graph is a depth-1 vertex minor of a matchmaking graph.

*Proof.* — Let $H$ be a split interval graph. We construct a supergraph $G$ of $H$ with additional properties. We first let $G = H$. As $G$ is a split interval graph, its vertex set is the disjoint union of a clique $K$ and an independent set $I$. It is known [10, Proposition 1] that $G$ has an interval representation where every interval in $I$ is a singleton. Hence, the interval representation defines a linear order $<$ on $I$. As $K$ is a clique, $\bigcap K$ is not empty. Adding, if necessary, a vertex to $I$, we can assume that there exists $a_1 \in I \bigcap \bigcap K$. Moreover, by slightly extending some intervals and adding some vertices in $I$, we can assume that all the intervals have distinct leftmost incidence in $I$ and distinct rightmost incidence in $I$. By adding new intervals and vertices in $I$ if necessary, we can further ensure that every vertex $v \in I$ is the leftmost or the rightmost incidence in $I$ of exactly one interval in $K$ (and that all the intervals in $K$ are incident to $a_1$). Then, the elements of $I$ can be labeled $a_m < \dots < a_1 < b_1 < \dots < b_m$, and the elements in $K$ can be labeled as a set $M$ of pairs $(i,j)$, where the pair associated to $v \in L$ is
(i, j) if $a_i$ is the leftmost incidence of $v$ in $I$, $b_j$ the rightmost incidence of $v$ in $I$. Note that $M$ is a perfect matching of $\{a_1, \dots, a_m\}$ and $\{b_1, \dots, b_m\}$ by construction.

The graph $G'$ obtained by flipping $K$ (i.e. turning $K$ into an independent set) is a matchmaking graph $H'$. Now, $H$ is an induced subgraph of $G' = H' * a_1$, hence a depth-1 vertex minor of a matchmaking graph. $\square$

With Lemma 4.7 in hand, we reduce the different cases of Theorem 4.6 in terms of shallow vertex minors.

**LEMMA 4.10.** — Let $\mathcal{C}$ be a class of graphs and let $r$ be a positive integer. Assume that for arbitrarily large integer $n$ the class $\mathcal{C}$ includes a flipped star $r$-crossings or a flipped clique $r$-crossings of order $n$. Then, $\text{svm}_c(\mathcal{C})$ is the class of all graphs, where $c = 3r/2 + 4 + \lfloor \log_2(2r+1) \rfloor$.

*Proof.* — Consider a flipped star $r$-crossings or a flipped clique $r$-crossings $G$ of order $n$. Let $I = \{p_{1,1,2k} : 0 \le 2k \le r+1\} \cup \{p_{2,2,2k+1} : 0 \le 2k+1 \le r+1\}$. Then, $I$ is an independent set and, according to Lemma 4.7, a star $r$-crossings or a clique $r$-crossings of order $n-2$ is a depth-$\left(\left\lfloor \frac{3(r+2)}{2} \right\rfloor\right)/2$ vertex minor of $G$. If the obtained graph is a clique $r$-crossings of order $n-2$, then it can be turned into a star $r$-crossings of order $n-2$ by local complementation of the (independent) set of all its principal vertices. Thus, we get a star $r$-crossings of order $n-2$ as a depth-$\left(\left\lfloor \frac{3r+2}{4} \right\rfloor\right)$ vertex minor of $G$. This graph contains the $(2r+1)$-subdivision of all the $(2r+1)$-subdivisions of the graphs with order at most $\sqrt{n-2}$. The result follows. $\square$

**LEMMA 4.11.** — Let $\mathcal{C}$ be a class of graphs and let $r$ be a positive integer. Assume that for arbitrarily large integer $n$ the class $\mathcal{C}$ includes a flipped half-graph $r$-crossings. Then, $\text{svm}_c(\mathcal{C})$ includes all matchmaking graphs, where $c = 3r/2 + 4 + \lfloor \log_2 r \rfloor$.

*Proof.* — Consider a flipped half-graph $r$-crossings $G$ of order $2n+3$. Let $I = \{p_{1,1,2k} : 2 \le 2k \le r\} \cup \{p_{2,2,2k+1} : 0 \le 2k+1 \le r+1\} \cup \{a_3\}$. Then, $I$ is an independent set and, according to Lemma 4.7, a half-graph $r$-crossings of order $2n$ is a depth-$\left(\left\lfloor \frac{3(r+2)}{2} \right\rfloor\right)$ vertex minor of $G$. If $r=1$, then we get all matchmaking graphs of order $2n$ as induced subgraphs of the so-obtained graph. If $r \ge 2$, we get, as a depth-$\lfloor \log_2 r \rfloor$ vertex minor of the so-obtained graph a graph formed by two half graphs and an arbitrary perfect matching between their upper parts. By local complementation of one of these upper part (and as the order $2n$ is even) we get all matchmaking graphs of order $2n$. $\square$
As a consequence of Theorem 4.6, the above lemmas, and the fact that every permutation graph is an induced subgraph of a comparability grid (See, for instance, [11]), we get

COROLLARY 4.12. — Let $\mathcal{C}$ be a hereditary class of graphs. If $\mathcal{C}$ is independent, then either $\mathcal{C}$ includes all permutation graphs or there exists a non-negative integer $r$ such that $\text{svm}_r(\mathcal{C})$ includes all split interval graphs.

## 5. Preservation of dependence and stability by shallow vertex minors

This section gathers the preservation theorems proved in this paper, which will be central to the characterization theorems proved in the next section.

LEMMA 5.1. — Let $\mathcal{C}$ be a hereditary class of graphs. Then $\mathcal{C}$ is stable if and only if $\text{svm}_1(\mathcal{C})$ is stable.

*Proof*. — If $\text{svm}_1(\mathcal{C})$ is stable, then $\mathcal{C}$ is stable as $\mathcal{C} \subseteq \text{svm}_c(\mathcal{C})$.

Assume $\mathcal{C}$ is stable. Let $r$ be a positive integer, let $G \in \mathcal{C}$, let $I$ be an independent set of $G$ and let $A \subseteq V(G)$. According to Theorem 4.4, there exists a $k_{2r}$-flip $F_{2r}$ and a subset $S$ of $A$ with size at least $U_{2r}(|A|)$, such that the vertices of $S$ are $2r$-independent in $G \oplus F_{2r}$. According to Lemma 3.4, there exists a $2k_{2r}2^{2k_{2r}}$-flip $F'$ such that $\text{dist}_{G*I \oplus F'} \ge \frac{1}{2} \text{dist}_{G \oplus F_{2r}}$. The integer $k'_r = 2k_{2r}2^{2k_{2r}}$, the flip $F'_r = F'$, and the function $U'_r = U_{2r}$ witness that, according to Theorem 4.4, the class $\{G * I : G \in \mathcal{C}, I \text{ independent in } G\}$ is monadically stable. It follows that the hereditary closure $\text{svm}_1(\mathcal{C})$ of this class is stable. $\square$

Similarly, we get.

LEMMA 5.2. — Let $\mathcal{C}$ be a hereditary class of graphs. Then, $\mathcal{C}$ is dependent if and only if $\text{svm}_1(\mathcal{C})$ is dependent.

*Proof*. — If $\text{svm}_1(\mathcal{C})$ is dependent, then $\mathcal{C}$ is dependent as $\mathcal{C} \subseteq \text{svm}_c(\mathcal{C})$.

Assume $\mathcal{C}$ is dependent. Let $r$ be a positive integer, let $G \in \mathcal{C}$, let $I$ be an independent set of $G$ and let $A \subseteq V(G)$. According to Theorem 4.5, there exists a $k_{2r}$-flip $F_{2r}$ and subset $A_1, A_2$ of $A$ with size at least $U_{2r}(|A|)$, such that $\text{dist}_{G \oplus F_{2r}}(A_1, A_2) > r$. According to Lemma 3.4, there exists a $2k_{2r}2^{2k_{2r}}$-flip $F'$ such that $\text{dist}_{G*I \oplus F'} \ge \frac{1}{2} \text{dist}_{G \oplus F}$. The integer $k'_r = 4k_{2r}$, the flip $F'_r = F'$, and the function $U'_r = U_{2r}$ witness that, according to Theorem 4.5, the class $\{G * I : G \in \mathcal{C}, I \text{ independent in } G\}$ is monadically dependent. It follows that the hereditary closure $\text{svm}_1(\mathcal{C})$ of this class is dependent. $\square$
# 6. The characterization theorems

**THEOREM 6.1 (Restatement of Theorem 1.2).** — Let $\mathcal{C}$ be a hereditary class of graphs. Then, $\mathcal{C}$ is dependent if and only if the class $\mathcal{C}$ does not contain all permutation graphs and, for every integer $r$, the class $\mathcal{C}$ excludes some split interval graph as a depth-$r$ shallow vertex minor.

*Proof.* — Assume $\mathcal{C}$ is independent. Then, according to Corollary 4.12, either $\mathcal{C}$ contains all permutation graphs or there exists a non-negative integer $r$ such that $\text{svm}_r(\mathcal{C})$ includes all split interval graphs.

Conversely, assume that either $\mathcal{C}$ contains all permutation graphs or there exists a non-negative integer $r$ such that $\text{svm}_r(\mathcal{C})$ includes all split interval graphs. In the first case, $\mathcal{C}$ is independent, as it is well known that the class of all permutation graphs is independent(1)

In the latter case, it follows from the fact that the class of split interval graphs is independent (See Example 4.1) that $\text{svm}_r(\mathcal{C})$ is independent. Then, according to Lemma 5.2, the class $\mathcal{C}$ is independent. □

The characterization of stability will make use of the following result.

**THEOREM 6.2 ([14, Theorem 5.2]).** — For a monadically dependent graph class $\mathcal{C}$, the following conditions are equivalent:

(1) $\mathcal{C}$ has a stable edge relation;

(2) $\mathcal{C}$ is stable;

(3) $\mathcal{C}$ is monadically stable

**THEOREM 6.3 (Restatement of Theorem 1.3).** — Let $\mathcal{C}$ be a hereditary class of graphs. Then, $\mathcal{C}$ is stable if and only if, for every integer $r$, the class $\mathcal{C}$ excludes some half-graph as a depth-$r$ shallow vertex minor.

*Proof.* — Assume that for some integer $r$, the class $\text{svm}_r(\mathcal{C})$ contains all the half-graphs. Then, $\text{svm}_r(\mathcal{C})$ is unstable and, according to Lemma 5.1, so is $\mathcal{C}$.

Conversely, assume that $\mathcal{C}$ is unstable. Assume that $\mathcal{C}$ is also independent. Then, either $\mathcal{C}$ includes all permutation graphs (including all half-graphs, as they are permutation graphs), or there exists a non-negative $r$ such that $\text{svm}_r(\mathcal{C})$ includes all split interval graphs. As every half-graph

<footnote>(1) One way to see this is to check that the class of all permutations encoded as two linear orders (which is known to be independent [4]) is a transduction of the class of all permutation graphs. To see this, we associate to $\sigma \in \mathfrak{S}_n$ the permutation $\hat{\sigma} \in \mathfrak{S}_{2n}$ defined by $\hat{\sigma}(2i + 1) = \sigma(i)$ and $\hat{\sigma}(2i) = n + i$. Let $A = \{2i: i \in [n]\}$ and $B = \{2i + 1: i \in [n]\}$, then $\sigma$ is isomorphic to the permutation on $A$ defined by the total orders $(x <_1 y) := (\forall z \in B(z) \to (E(x, z) \to E(y, z)))$ and $(x <_2 y) := (x <_1 y) \leftrightarrow E(x, y)$.</footnote>
can be obtained as a depth-1 vertex minor of a split interval graph, we conclude that $\text{svm}_{r+1}(\mathcal{C})$ includes all half-graphs.

Otherwise, $\mathcal{C}$ is dependent and unstable. Then, according to Theorem 6.2, the graphs in $\mathcal{C}$ contain arbitrarily large semi-induced half-graphs. By a standard Ramsey argument, we deduce that we can find in $\mathcal{C}$ arbitrarily large flipped half graphs, where the partition used for the flip is the bipartition of the half-graph. Let $a_1, \dots, a_n, b_1, \dots, b_n$ be the vertices of the flipped half-graph. By considering the independent set $\{a_n, b_1\}$ and Lemma 4.7, we deduce that $\text{svm}_2(\mathcal{C})$ contains all half-graphs. $\square$

## 7. Extension to binary structures

In this section, we discuss the generalization of Theorems 1.2 and 1.3 to binary structures. As an application, we show that this generalization allows a short proof that the boundedness of twin-width is preserved by shallow vertex minors.

A relational signature $\sigma$ is a set of relation symbols with arity. A binary relational structure is a relational structure whose signature contains relations with arity at most 2.

Let $\sigma$ be a relational signature and let $\bar{\sigma} = \sigma \cup \{\sim\}$, where $\sim$ is a binary relation symbol. The $k$-copy operation $C_k$ maps a $\sigma$-structure $\mathbf{M}$ into the $\bar{\sigma}$-structure $C_k(\mathbf{M})$ consisting of $k$ copies of $\mathbf{M}$ where the copies of each element of $\mathbf{M}$ are made adjacent by $\sim$. The copies of a same element are called clones. Note that for $k=1$, $C_1$ maps each structure $\mathbf{M}$ to itself.

For a set $\mathcal{U}$ of unary relations, the coloring operation $\Gamma_{\mathcal{U}}$ maps a structure $\mathbf{M}$ to the set $\Gamma_{\mathcal{U}}(\mathbf{M})$ of all its $\mathcal{U}$-expansions.

Let $\sigma^+, \sigma'$ be relational structures, where $\sigma^+ \setminus \bar{\sigma} = \mathcal{U}$. A simple interpretation $\mathcal{I}$ of $\sigma'$-structures in $\sigma^+$-structures is defined by a formula $\nu(x)$ and, for each $R \in \sigma'$ with arity $r$, a formula $\rho_R(\bar{x})$ with $|\bar{x}| = r$ (in the first-order language of $\sigma^+$-structures). If $\mathbf{M}^+$ is a $\sigma^+$-structure, then $\mathbf{N} = \mathcal{I}(\mathbf{M}^+)$ is the $\sigma'$-structure with domain $N = \nu(\mathbf{M}^+)$ where, for each $R \in \sigma'$ with arity $r$, we have $R(\mathbf{N}) = \rho_R(\mathbf{M}) \cap \nu(\mathbf{M})^r$. For a set $\Gamma$ of $\sigma^+$-structures we let $\mathcal{I}(\Gamma) = \bigcup_{\mathbf{M}^+ \in \Gamma} \mathcal{I}(\mathbf{M}^+)$.

A transduction $\mathcal{T}$ is the composition $\mathcal{I} \circ \Gamma_{\mathcal{U}} \circ C_k$ of a copy operation $C_k$, a coloring operation $\Gamma_{\mathcal{U}}$, and a simple interpretation $\mathcal{I}$. In other words, for every $\sigma$-structure $\mathbf{M}$ we have $\mathcal{T}(\mathbf{M}) = \{\mathcal{I}(\mathbf{M}^+) : \mathbf{M}^+ \in \Gamma_{\mathcal{U}}(C_k(\mathbf{M}))\}$.

Let $\sigma = \{R_1, \dots, R_k\}$ be a binary relational signature. We consider two transductions. First, $\mathcal{X} = \mathcal{I}_X \circ \Gamma_{\mathcal{U}} \circ C_k$ from $\sigma$-structures to $\mathcal{U}$-colored digraphs, where $\mathcal{U} = \{P_1, \dots, P_k\}$ and $\mathcal{I}_X$ is the simple interpretation defined
by the formulas

$$
\begin{align*}
\nu(x) &:= \top \\
\rho_{P_i}(x) &:= P_i(x) \\
\rho_E(x, y) &:= \left( \bigvee_{i \in [k]} (P_i(x) \wedge P_i(y) \wedge R_i(x, y)) \right) \\
&\qquad \vee \left( \bigvee_{i \neq j \in [k]} (P_i(x) \wedge P_j(y) \wedge (x \sim y)) \right)
\end{align*}
$$

Second, $\mathbf{K}$ is the simple interpretation of $\sigma$-structures in $\mathcal{U}$-colored di-
graphs defined by the formulas (where $1 < i \le k$)

$$
\begin{align*}
\nu(x) &:= P_1(x), \\
R_1(x, y) &:= E(x, y), \\
R_i(x, y) &:= \exists x', y' (P_i(x') \wedge P_i(y') \wedge E(x, x') \wedge E(y, y') \wedge E(x', y')).
\end{align*}
$$

Particularly, let $f_X(\mathbf{M}) \in \mathbf{X}(\mathbf{M})$ be the graph obtained from the $\mathcal{U}$-
expansion such that $P_i$ marks the $i$th clones. It is clear that for every
$\sigma$-structure $\mathbf{M}$, we have $\mathbf{M} = \mathbf{K}(f_x(\mathbf{M}))$. (Hence, $\mathbf{M} \in \mathbf{K} \circ \mathbf{X}(\mathbf{M})$.) In partic-
ular, a class $\mathcal{C}$ of $\sigma$-structures is monadically dependent (resp. monadically
stable) if and only if $f_X(\mathcal{C})$ is monadically dependent (resp. monadically
stable).

Note that if $R_i$ is symmetric, so is the adjacency relation between the
vertices in the unary relation $P_i$. In such a case, we can consider that
subdigraphs induced by vertices in $P_i$ are actually graphs. Let $\sigma$ be a fi-
nite binary structure and let $M$ be a $\sigma$-structure such that $R_1, \dots, R_a$ are
symmetric. For $i \in [a]$, we define $\mathbf{M} *^{R_i} v$ as the $\sigma$-structure obtained by
$R_i$-complementing the $R_i$-neighborhood of $v$. A depth-1 vertex minor of $\mathbf{M}$
has the form

$$
\mathbf{M} *^{R_1} I_1 * \cdots *^{R_a} I_a - D,
$$

where $I_i$ is an $R_i$-independent subset of $M$ and $D \subseteq M$. We denote by
$\text{svm}_1(\mathbf{M})$ the set of all the depth-1 vertex minors of $\mathbf{M}$ and, for a class $\mathcal{C}$
of $\sigma$-structures, we define $\text{svm}_1(\mathcal{C}) = \bigcup_{\mathbf{M} \in \mathcal{C}} \text{svm}_1(\mathbf{M})$.

Fact 1. — For every class $\mathcal{C}$ of $\sigma$-structures, we have

$$
f_X(\mathrm{svm}_1(\mathcal{C})) \subseteq \mathrm{svm}_1(f_X(\mathcal{C})).
$$

As a consequence, we have

COROLLARY 7.1. — Let $\mathcal{C}$ be a hereditary class of binary structures.
Then,
(1) $\mathcal{C}$ is stable if and only if $\mathrm{svm}_1(\mathcal{C})$ is stable;

(2) $\mathcal{C}$ is dependent if and only if $\mathrm{svm}_1(\mathcal{C})$ is dependent.

As an application of this corollary, we have

**THEOREM 7.2.** — Let $\mathcal{C}$ be a class of graphs. Then, $\mathcal{C}$ has bounded twin-width if and only if $\mathrm{svm}_1(\mathcal{C})$ has bounded twin-width.

*Proof.* — As $\mathcal{C} \subseteq \mathrm{svm}_1(\mathcal{C})$, the class $\mathcal{C}$ has bounded twin-width if $\mathrm{svm}_1(\mathcal{C})$ has bounded twin-width.

Conversely, assume that $\mathcal{C}$ has bounded twin-width. According to [2], the class $\mathcal{C}$ has an expansion to a dependent class $\mathcal{C}^<$ of ordered graph. This expansion is a binary structure with (binary) signature $\{E, <\}$. According to Corollary 7.1, $\mathrm{svm}_1(\mathcal{C}^<)$ is dependent. Here, we have a single symmetric relation, which is $E$. As the linear order is not modified by local complementations on $E$-neighborhood, the class $\mathrm{svm}_1(\mathcal{C}^<)$ is a class $\mathcal{D}^<$ of ordered graphs, which is a dependent expansion of $\mathrm{svm}_1(\mathcal{C})$. According to [2], it follows that $\mathrm{svm}_1(\mathcal{C})$ has bounded twin-width. □

## 8. Discussion

It has been proved [12] that a class $\mathcal{C}$ has bounded shrubdepth if and only if $\mathcal{C}$ excludes some path as a vertex minor. It is natural to ask whether this result could be strengthened by restricting to shallow vertex minors.

*Problem 1.* — Is it true that for every class $\mathcal{C}$ with unbounded shrubdepth there exists an integer $r$ such that $\mathrm{svm}_r(\mathcal{C})$ contains all paths or all half-graphs?

Remark that this problem can be restated as follows: Is it true that for every stable class $\mathcal{C}$ with unbounded shrubdepth there exists an integer $r$ such that $\mathrm{svm}_r(\mathcal{C})$ contains all paths?

It is known [15] that a class $\mathcal{C}$ has structurally bounded expansion if and only if there exists a class $\mathcal{D}$ of bipartite graphs with bounded expansion such that $\mathcal{C} \subseteq \mathrm{svm}_1(\mathcal{D})$. An obvious question is whether such a kind of characterizations would extend to stable hereditary classes of graphs.

*Problem 2.* — Is it true that a hereditary class $\mathcal{C}$ is stable if and only if there exist an integer $c$ and a nowhere dense class $\mathcal{D}$, such that $\mathcal{C} \subseteq \mathrm{svm}_c(\mathcal{D})$?
One direction follows from Theorem 1.3: If there exist an integer $c$ and a nowhere dense class $\mathcal{D}$ such that $\mathcal{C} \subseteq \text{svm}_c(\mathcal{D})$, then $\mathcal{C}$ is stable. On the other hand, it might well follow from [6] that if $\mathcal{C}$ is stable then there exists a stable almost nowhere dense class $\mathcal{D}$ of bipartite graphs with $\mathcal{C} \subseteq \text{svm}_1(\mathcal{D})$.

## Acknowledgments

While writing this article, we have been informed that the methods used by Dreier, Mählmann, and Toruńczyk might allow to directly prove the preservation of monadic dependence and monadic stability under any transduction based on first-order logic with modulo counting. However, we decided to keep the proofs of the preservation of shallow vertex minors as an illustrative application of the commuting properties of flip and local complementation.

The authors would like to thank the referee for their careful reading.

## BIBLIOGRAPHY

[1] H. ADLER & I. ADLER, Interpreting nowhere dense graph classes as a classical notion of model theory, *Eur. J. Comb.* **36** (2014), p. 322–330, https://dx.doi.org/10.1016/j.ejc.2013.06.048.

[2] E. BONNET, U. GIOANTI, P. OSSONA DE MENDEZ, P. SIMON, S. THOMASSÉ & S. TORUŃCZYK, Twin-width IV: ordered graphs and matrices, in *STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing*, ACM, 2022, p. 924–937, https://dx.doi.org/10.1145/3519935.3520037.

[3] E. BONNET, E. J. KIM, S. THOMASSÉ & R. WATRIGANT, Twin-width I: tractable FO model checking, in *61st Annual Symposium on Foundations of Computer Science (FOCS 2020)*, IEEE, 2020, p. 601–612.

[4] E. BONNET, J. NEŠETŘIL, P. OSSONA DE MENDEZ, S. SIEBERTZ & S. THOMASSÉ, Twin-width and permutations, *Logical Methods in Computer Science* **20** (2024), no. 3, article no. 4 (25 pages), https://dx.doi.org/10.46298/lmcs-20(3:4)2024.

[5] S. BRAUNFELD & M. C. LASKOWSKI, Existential characterizations of monadic NIP, 2022, https://arxiv.org/abs/2209.05120.

[6] S. BRAUNFELD, J. NEŠETŘIL, P. OSSONA DE MENDEZ & S. SIEBERTZ, Decomposition horizons: from graph sparsity to model-theoretic dividing lines, *Eur. J. Comb.* (2024), Eurocomb 2023 special issue; submitted.

[7] J. DREIER, I. ELEFTHERIADIS, N. MÄHLMANN, R. MCCARTY, M. PILIPCZUK & S. TORUŃCZYK, First-Order Model Checking on Monadically Stable Graph Classes, accepted at FOCS 2024, 2023, https://arxiv.org/abs/2311.18740.

[8] J. DREIER, N. MÄHLMANN, S. SIEBERTZ & S. TORUŃCZYK, Indiscernibles and Flatness in Monadically Stable and Monadically NIP Classes, in *50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)*, Schloss-Dagstuhl-Leibniz Zentrum für Informatik, 2023.

[9] J. DREIER, N. MÄHLMANN & S. TORUŃCZYK, Flip-Breakability: A Combinatorial Dichotomy for Monadically Dependent Graph Classes, in *Proceedings of the 56th Annual ACM Symposium on Theory of Computing*, ACM, 2024, p. 1550–1560.
[10] S. FOLDES & P. L. HAMMER, Split graphs having Dilworth number two, *Can. J. Math.* **29** (1977), no. 3, p. 666–672.

[11] J. GEELEN, O. KWON, R. MCCARTY & P. WOLLAN, The Grid Theorem for vertex-minors, *J. Comb. Theory, Ser. B* **158** (2023), p. 93–116, https://dx.doi.org/10.1016/j.jctb.2020.08.004, Robin Thomas 1962-2020.

[12] O. KWON, R. MCCARTY, S. OUM & P. WOLLAN, Obstructions for bounded shrub-depth and rank-depth, *J. Comb. Theory, Ser. B* **149** (2021), p. 76–91, https://dx.doi.org/10.1016/j.jctb.2021.01.005.

[13] J. NEŠETŘIL & P. OSSONA DE MENDEZ, *Sparsity (Graphs, Structures, and Algorithms)*, Algorithms and Combinatorics, vol. 28, Springer, 2012, 465 pages.

[14] J. NEŠETŘIL, P. OSSONA DE MENDEZ, M. PILIPCZUK, R. RABINOVICH & S. SIEBERTZ, Rankwidth meets stability, in *Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)*, ACM, 2021, p. 2014–2033, https://dx.doi.org/10.1137/1.9781611976465.120.

[15] J. NEŠETŘIL, P. OSSONA DE MENDEZ & S. SIEBERTZ, Modulo-Counting First-Order Logic on Bounded Expansion Classes, *Discrete Math.* **347** (2024), no. 8, p. 113700, https://dx.doi.org/10.1016/j.disc.2023.113700.

[16] S. OUM, Rank-width and vertex-minors, *J. Comb. Theory, Ser. B* **95** (2005), no. 1, p. 79–100, https://dx.doi.org/10.1016/j.jctb.2005.03.003.

Manuscript received 13th June 2024,
accepted 14th November 2024.

Hector BUFFIÈRE
École Normale Supérieure
Paris
France
hector.buffiere@ens.fr

Eun Jung KIM
KAIST, Daejeon
South Korea
and CNRS
Paris
France
eunjungkim78@gmail.com

Patrice OSSONA DE MENDEZ
Centre d'Analyse et de Mathématiques Sociales
(CNRS, UMR 8557)
Paris
France
and Computer Science Institute of Charles
University
Praha
Czech Republic
pom@ehess.fr
<figure><img src="image_14.png" /></figure>

This article is licensed under the
**CREATIVE COMMONS ATTRIBUTION 4.0**
**INTERNATIONAL LICENSE.**
http://creativecommons.org/licenses/by/4.0/

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

*Innovations in Graph Theory* is a member of the
Mersenne Center for Open Publishing
ISSN: 3050-743X