# Flip-Breakability: A Combinatorial Dichotomy
for Monadically Dependent Graph Classes††thanks:  N.M. was supported by the
German Research Foundation (DFG) with grant agreement No. 444419611. S.T. was
supported by the project BOBR that is funded from the European Research
Council (ERC) under the European Union’s Horizon 2020 research and innovation
programme with grant agreement No. 948057. The BOBR project also supported a
stay of N.M. at the University of Warsaw, where part of this work was done.

Jan Dreier
TU Wien
<EMAIL_ADDRESS>Nikolas Mählmann
University of Bremen
<EMAIL_ADDRESS>Szymon Toruńczyk
University of Warsaw
<EMAIL_ADDRESS>
###### Abstract

A conjecture in algorithmic model theory predicts that the model-checking
problem for first-order logic is fixed-parameter tractable on a hereditary
graph class if and only if the class is _monadically dependent_. Originating
in model theory, this notion is defined in terms of logic, and encompasses
nowhere dense classes, monadically stable classes, and classes of bounded
twin-width. Working towards this conjecture, we provide the first two
combinatorial characterizations of monadically dependent graph classes. This
yields the following dichotomy.

On the structure side, we characterize monadic dependence by a Ramsey-
theoretic property called _flip-breakability_. This notion generalizes the
notions of uniform quasi-wideness, flip-flatness, and bounded grid rank, which
characterize nowhere denseness, monadic stability, and bounded twin-width,
respectively, and played a key role in their respective model checking
algorithms. Natural restrictions of flip-breakability additionally
characterize bounded treewidth and cliquewidth and bounded treedepth and
shrubdepth.

On the non-structure side, we characterize monadic dependence by explicitly
listing few families of _forbidden induced subgraphs_. This result is
analogous to the characterization of nowhere denseness via forbidden
subdivided cliques, and allows us to resolve one half of the motivating
conjecture: First-order model checking is AW[$*$]-hard on every hereditary
graph class that is monadically independent. The result moreover implies that
hereditary graph classes which are small, have almost bounded twin-width, or
have almost bounded flip-width, are monadically dependent.

Lastly, we lift our result to also obtain a combinatorial dichotomy in the
more general setting of monadically dependent classes of binary structures.

section [5pt] 0pt 0pt *[.5pc]. []

###### Acknowledgements.

N.M. thanks Michał Pilipczuk for hosting a stay at the University of Warsaw,
where part of this work was done.

###### Contents

  1. 1 Introduction
  2. 2 Technical Overview
  3. 3 Conclusions and Future Work
  4. 4 Preliminaries
  5. I Structure
    1. 5 Grids and Insulators
    2. 6 Prepatterns
    3. 7 The Insulation Property
    4. 8 Flip-Breakability
    5. 9 Sample Sets
    6. 10 Extending Insulators
  6. II Non-Structure
    1. 11 Transformers
    2. 12 Converters and Crossings
    3. 13 Wrapping Up
  7. III Lower Bounds
    1. 14 Hardness of Model Checking
    2. 15 Almost Bounded Twin-Width
    3. 16 Almost Bounded Flip-Width
    4. 17 Small Classes
  8. IV Restrictions and Extensions
    1. 18 Variants of Flip-Breakability
    2. 19 Binary Structures

###  1 Introduction

Algorithmic model theory studies the interplay between the computational
complexity of computational problems defined using logic, and the structural
properties of the considered instances. In this context, _algorithmic meta-
theorems_ [41, 37] are results that establish the tractability of entire
families of computational problems, which are defined in terms of logic, while
imposing structural restrictions on the input instances. The archetypical
example is Courcelle’s theorem, which states that every problem that can be
expressed in monadic second order logic (MSO), can be solved in linear time,
whenever the considered input graphs have bounded treewidth [13, 3]. This
implies that the model checking problem for MSO is _fixed-parameter tractable_
(fpt) on every class $\mathcal{C}$ of bounded treewidth. That is, there is an
algorithm which determines whether a given input graph $G\in\mathcal{C}$
satisfies a given MSO formula $\varphi$ in time $f(|\varphi|)\cdot|V(G)|^{c}$
for some function $f\colon\mathrm{\mathbb{N}}\to\mathrm{\mathbb{N}}$ and some
constant $c$ (in this case $c=1$). More generally, the model checking problem
for MSO is fpt on all classes of bounded cliquewidth [14].

In this paper, we focus on the model-checking problem for _first-order logic_
(FO), which allows to relax the structure of the input graphs greatly, at the
cost of restricting the logic. Graph classes for which this problem is fpt
include classes of bounded degree [53], the class of planar graphs [29],
classes which exclude a minor [28], classes of bounded expansion [25], and
more generally, nowhere dense classes [38], all of which are _sparse_ graph
classes (specifically, every $n$-vertex graph in such a class has
$O(n^{1+\varepsilon})$ edges, for every fixed $\varepsilon>0$). The problem is
moreover fpt on proper hereditary classes of permutation graphs, some classes
of bounded twin-width [9], structurally nowhere dense classes [21],
monadically stable classes [20], and others [5]. The central question in the
area, first phrased in [37, Sec. 8.2], is the following.

> What are the structural properties that exactly characterize the
> hereditary111A graph class is _hereditary_ if it is closed under vertex
> removal. graph classes with fpt first-order model checking?

_Sparsity theory_ [44], initiated by Nešetřil and Ossona de Mendez, has
provided solid structural foundations, and a very general notion of structural
tameness for sparse graph classes. More recently, _twin-width theory_ [9]
provides another notion of graph classes which are structurally tame, and not
necessarily sparse. While _twin-width theory_ and _sparsity theory_ bear
striking similarities, they are fundamentally incomparable in scope. The
community eagerly anticipates a theory that unifies both frameworks, and
answers the central question. _Stability theory_ – an area in model theory
developed initially by Shelah – provides very general notions of _logical_
tameness of classes of graphs (or other structures), called (monadic)
_stability_ and _dependence_ 222In the literature, _dependence_ is also
referred to as _NIP_ , which stands for _negation of the independence
property_., which subsume the notions studied in sparsity theory and in twin-
width theory, but are not easily amenable to combinatorial or algorithmic
treatment. Let us briefly review _sparsity theory_ , _twin-width theory_ , and
_stability theory_ , which we build upon. Figure 1 shows the relationships
between the properties of graph classes discussed in this paper.

Figure 1: Hierarchy of selected properties of graph classes. Classes in green
boxes are known do admit fpt model checking algorithms (with additional
assumptions required in the case of bounded twin-width). _Monadically
dependent_ classes are known to generalize all these notions. It is
conjectured that a hereditary class is monadically dependent if and only if
its model checking problem is tractable.

###### Sparsity.

The central notion of sparsity theory [44] is that of a _nowhere dense_ graph
class. This is a very general notion of structural tameness of sparse graph
classes, and encompasses all classes with bounded degree, bounded treewidth,
the class of planar graphs, and classes that exclude some graph as a minor.
After a long sequence of prior work [53, 28, 29, 17, 25], the celebrated
result of Grohe, Kreutzer and Siebertz [38] established that the model
checking problem is fpt on every nowhere dense graph class. For classes that
are _monotone_ (closed under removal of vertices and edges) this is optimal
[25, 41], yielding the following milestone result.

> A monotone graph class admits fpt model checking if and only if it is
> _nowhere dense_ (assuming $\textnormal{FPT}\neq\textnormal{AW}[*]$) [38].

Here, $\textnormal{FPT}\neq\textnormal{AW}[*]$ is a standard complexity
assumption in parameterized complexity, equivalent to the statement that model
checking is not fpt on the class of all graphs. The major shortcoming of this
result is that it only captures monotone classes, and thus _sparse_ graph
classes, while there are dense graph classes which are not monotone, and have
fpt model checking. A trivial example is the class of cliques. More generally,
all classes of bounded cliquewidth have fpt model checking. For many years,
not many examples of graph classes for which the model checking problem is fpt
– beyond nowhere dense classes and classes of bounded cliquewidth – were
known.

A recent line of research extends sparsity theory beyond the sparse setting
using _transductions_. We say a graph class $\mathcal{C}$ _transduces_ a graph
class $\mathcal{D}$ if there exists a first-order formula $\varphi(x,y)$ such
that every graph in $\mathcal{D}$ can be obtained by the following four steps:
(1) taking a graph $G\in\mathcal{C}$, (2) coloring the vertices of $G$, (3)
replacing the edge set of $G$ with $\\{uv\mid u,v\in V(G),u\neq
v,G\models\varphi(u,v)\lor\varphi(v,u)\\}$, and (4) taking an induced
subgraph. Step 3 can construct, for example, the _edge-complement_ of $G$ with
$\varphi(x,y)=\neg E(x,y)$ or the _square_ of $G$ with $\varphi(x,y)=\exists
z~{}E(x,z)\land E(z,y)$. Note that the formula $\varphi$ has access to the
colors of $G$ from step 2. Therefore, for example, the class of all graphs is
transduced by the class of $1$-subdivided cliques (by coloring the subdivision
vertices that should be turned into edges), but is _not_ transduced by the
class of cliques. It was recently shown that model checking is fpt on
_transductions of nowhere dense classes_ [21], extending the work of Grohe,
Kreutzer, and Siebertz [38] beyond the sparse setting. This result has been
generalized very recently in [20], as described below.

Figure 2: A half-graph of order 4.

###### Monadic Stability.

Stability, and its variants, are logical tameness conditions arising in
Shelah’s classification program [54]. A graph class is _monadically_ 333
_Monadically_ refers to the coloring step of a transduction, which is an
expansion of the graph with unary/monadic predicates. In classical model
theory monadically stable (monadically dependent) classes are equivalently
defined as those classes that remain stable (dependent) under unary
expansions. _stable_ if it does not transduce the class of all _half-graphs_
(see Figure 2). Monadically stable classes include all structurally nowhere
dense classes [2, 49]. In [20] it is shown that FO model checking is fpt on
all monadically stable classes, and moreover obtains matching hardness bounds
via a new characterization of such classes in terms of forbidden induced
subgraphs. A class is _orderless_ if it avoids some half-graph as a semi-
induced444Semi-induced half-graphs look similar to Figure 2, but the
connections within the top row and within the bottom row may be arbitrary.
subgraph. This establishes monadically stable classes as the _limit of
tractability_ among orderless classes.

> An orderless, hereditary graph class admits fpt model checking if and only
> if it is _monadically stable_ (assuming
> $\textnormal{FPT}\neq\textnormal{AW}[*]$) [20].

###### Twin-Width.

Twin-width [9] is a recently introduced notion which has its roots in
enumerative combinatorics and the Stanley-Wilf conjecture/Marcus-Tardos
theorem. Graph classes with bounded twin-width include the class of planar
graphs, all classes of bounded cliquewidth, the class of unit interval graphs,
and every proper hereditary class of permutation graphs. It was shown that
model checking is fpt on graph classes of bounded twin-width, assuming an
appropriate decomposition of the graph (in form of a so-called _contraction
sequence_) is given as part of the input [9]. On _ordered graphs_ (that is,
graphs equipped with a total order on the vertex set, which can be accessed by
the formulas) a recent breakthrough result has lifted this additional proviso,
and also characterized classes of bounded twin-width as the _limit of
tractability_ [7].

> A hereditary class of ordered graphs admits fpt model checking if and only
> if it has bounded _twin-width_ (assuming
> $\textnormal{FPT}\neq\textnormal{AW}[*]$) [7].

###### Monadic Dependence.

As discussed above, an exact characterization of classes with fpt model-
checking has been established in three settings: for monotone graph classes,
for the more general hereditary orderless graph classes, and for hereditary
classes of ordered graphs, in terms of the notions of nowhere denseness,
monadic stability, and bounded twin-width, respectively. Those notions turn
out to be three facets of a single notion, again originating in stability
theory. A graph class $\mathcal{C}$ is _monadically independent_ if it
transduces the class of all graphs [4]. Otherwise $\mathcal{C}$ is
_monadically dependent_. In all three settings where we have a complete
characterization of fpt model checking, monadic dependence precisely captures
the limit of tractability.

  * •

On monotone classes, nowhere denseness is equivalent to monadic dependence
[49, 2].

  * •

On orderless classes, monadic stability is equivalent to monadic dependence
[45].

  * •

On classes of ordered graphs, bounded twin-width is equivalent to monadic
dependence [7].

This suggests that the known tractability limits [38, 7, 21, 20] are fragments
of a larger picture, where monadically dependent classes unify sparsity
theory, twin-width theory, and stability theory into a single theory of
tractability.

######  Conjecture 1.1 (e.g., [1, 7, 21]).

Let $\mathcal{C}$ be a hereditary class of graphs. Then the model checking
problem for first-order logic is fpt on $\mathcal{C}$ if and only if
$\mathcal{C}$ is monadically dependent.555The conjecture stated in [1]
mentions dependence instead of monadic dependence, but for hereditary classes,
those notions are equivalent [12]. Furthermore, the conjecture in [1] states
only one implication, but the other one was also posed at the same workshop as
an open problem.

Originally stated in 2016 [1], the above conjecture is now the central open
problem in the area. Both directions have been open.

#### Contribution

To approach Conjecture 1.1, a combinatorial characterization of monadic
dependence is sought. Based on the development in the sparse, orderless, and
ordered cases discussed above, it appears that what is needed are
_combinatorial dichotomy results_ , stating that all monadically dependent
graph classes exhibit structure which can be used to design efficient
algorithms, while all other graph classes exhibit a sufficient lack of
structure, which can be used to prove hardness results. The three known
restricted classifications of classes with fpt model checking were enabled in
part (see discussion below) thanks to such combinatorial dichotomies for
nowhere dense, monadically stable, and bounded twin-width graph classes.
However, for monadically dependent classes not a single combinatorial
characterization has been known. Previous characterizations of monadic
dependence (for example, via indiscernible sequences or existentially defined
canonical configurations [11, 12]) all have a logical, rather than
combinatorial, aspect. This limits their algorithmic usefulness.

In this paper, we provide the first two _purely combinatorial_
characterizations of monadically dependent classes, which together constitute
a combinatorial dichotomy theorem for these classes.

  * •

On the one hand, we show that monadically dependent graph classes have a
Ramsey-like property called _flip-breakability_ , which guarantees that any
large set of vertices $W$ contains two still-large subsets $A,B$ that in a
certain sense are strongly separated.

  * •

On the other hand, we show that graph classes that are monadically independent
contain certain highly regular patterns as induced subgraphs, which are
essentially two highly interconnected sets.

As argued below, _flip-breakability_ might be a crucial step towards
establishing fixed-parameter tractability of the model checking problem for
monadically dependent classes, and settling the tractability side of 1.1.
Moreover, we use the patterns of the second characterization to prove the
hardness side of 1.1: we show that first-order model checking is AW[$*$]-hard
on every hereditary graph class that is monadically independent (Theorem 1.7).
We now present our two combinatorial characterizations of monadically
dependent classes in more detail.

##### Flip-Breakability

_Flips_ are a central emerging mechanism in the study of well-behaved graph
classes (e.g., [33, 5, 32, 55]). A _$k$ -flip_ of a graph $G$ is a graph $H$
obtained from $G$ by partitioning the vertex set into $k$ parts and, for every
pair $X,Y$ of parts, either leaving the adjacency between $X$ and $Y$ intact,
or complementing it (see also Section 4).

We use flips to measure the interaction between vertex sets $A,B$ at a fixed
distance $r$ in a graph $G$. Intuitively, if for some small value $k$ there is
a $k$-flip $H$ of $G$ in which the distance $\textnormal{dist}_{H}(A,B)$ is
larger than $r$, then this witnesses that the sets $A$ and $B$ are “well-
separated” at distance $r$.

Figure 3:  The sets $A$ and $B$ are far away after a $5$-flip shown on the
right side. We flip between the blue squares and the blue circles, and between
the orange squares and the orange circles.

Consider for example the graph $G$ on the left side of Figure 3, consisting of
stacked half-graphs. Applying a flip between the blue squares and the blue
circles (as depicted to the right of Fig. 3), and between the orange squares
and the orange circles, we obtain a $5$-flip of $G$ in which the sets $A$ and
$B$ have distance at least $6$.

Roughly, our first main result expresses that for graphs from a monadically
dependent class, in every sufficiently large vertex set $W$, we can find two
still-large subsets $A$ and $B$ whose distance in some $O(1)$-flip is larger
than a given constant $r$. This is formally expressed as follows.

######  Definition 1.2 (Flip-Breakability).

A class of graphs $\mathcal{C}$ is flip-breakable if for every radius
$r\in\mathrm{\mathbb{N}}$ there exists a function
$N_{r}:\mathrm{\mathbb{N}}\to\mathrm{\mathbb{N}}$ and a constant
$k_{r}\in\mathrm{\mathbb{N}}$ such that for all $m\in\mathrm{\mathbb{N}}$,
$G\in\mathcal{C}$ and $W\subseteq V(G)$ with $|W|\geqslant N_{r}(m)$ there
exist subsets $A,B\subseteq W$ with $|A|,|B|\geqslant m$ and a $k_{r}$-flip
$H$ of $G$ such that:

$\textnormal{dist}_{H}(A,B)>r.$

######  Theorem 1.3.

A class of graphs is monadically dependent if and only if it is flip-
breakable.

Our proof is algorithmic: For a fixed monadically dependent class
$\mathcal{C}$ and radius $r$, the subsets $A$ and $B$ and the witnessing flip
$H$ can be computed in time $O_{\mathcal{C},r}(|V(G)|^{2})$ (Theorem 13.2).

As we discuss in Section 2, our results are based on a new notion called the
_insulation property_ (Definitions 5.2 and 7.2), which trivially implies flip-
breakability, but imposes an even more regular structure on monadically
dependent graph classes.

##### Relation of Flip-Breakability to Other Work

The model checking algorithms for nowhere dense classes [38] and monadically
stable classes [21, 20] are respectively based on winning strategies for
_pursuit-evasion games_ called the _splitter game_ [38] and the _flipper game_
[32]. These winning strategies were obtained from a characterization of
nowhere dense classes in terms of _uniform quasi-wideness_ [16, 43] and a
characterization of monadically stable classes in terms of _flip-flatness_
[22]. Both are Ramsey-like properties which are very similar to flip-
breakability. The definitions of these three notions match the same template:

> A class of graphs $\mathcal{C}$ is … if for every radius
> $r\in\mathrm{\mathbb{N}}$ there exists a function
> $N_{r}:\mathrm{\mathbb{N}}\to\mathrm{\mathbb{N}}$ and a constant
> $k_{r}\in\mathrm{\mathbb{N}}$ such that for all $m\in\mathrm{\mathbb{N}}$,
> $G\in\mathcal{C}$ and $W\subseteq V(G)$ with $|W|\geqslant N_{r}(m)$ there
> exist …

In all three cases we continue the definition by stating the existence of a
large number of vertices that are in a certain sense “well-separated”.
However, the sentence is completed in an increasingly more general way for the
three notions. The crucial differences are highlighted in bold.

  * •

uniform quasi-wide [16, 43]: …a set $\boldsymbol{S}\subseteq V(G)$ of at most
$\boldsymbol{k_{r}}$ vertices and $A\subseteq W\setminus S$ with $|A|\geqslant
m$, such that in $G\setminus S$, all vertices from $A$ have pairwise distance
greater than $\boldsymbol{r}$.

  * •

flip-flat [22]: …a $\boldsymbol{k_{r}}$-flip $\boldsymbol{H}$ of $G$ and
$A\subseteq W$ with $|A|\geqslant m$, such that in $H$, all vertices from $A$
have pairwise distance greater than $\boldsymbol{r}$.

  * •

flip-breakable: …a $\boldsymbol{k_{r}}$-flip $\boldsymbol{H}$ of $G$ and
$A,B\subseteq W$ with $|A|,|B|\geqslant m$, such that in $H$, all vertices in
$\boldsymbol{A}$ have distance greater than $\boldsymbol{r}$ from all vertices
in $\boldsymbol{B}$.

In the context of ordered graphs, the model checking algorithm for classes of
bounded twin-width crucially relied on a characterization of these classes in
terms of _bounded grid rank_ [7, Sec. 3.4]. Rephrasing this characterization
in the language of this paper, it reads as follows.

> A class of ordered graphs $\mathcal{C}$ has _bounded grid rank_ if there
> exists $k\in\mathrm{\mathbb{N}}$ such that for all $G\in\mathcal{C}$ and
> ordered sequences of vertices $a_{1}<\dots<a_{k}\in V(G)$,
> $b_{1}<\dots<b_{k}\in V(G)$, there exists a $k$-flip $H$ of $G$ and indices
> $i,j\in[k-1]$ defining ranges $A=\\{a\in V(G)\mid a_{i}\leqslant a\leqslant
> a_{i+1}\\}$, $B=\\{b\in V(G)\mid b_{j}\leqslant b\leqslant b_{j+1}\\}$, such
> that there are no edges incident to both $A$ and $B$ in $H$.

Flip-breakability combines the distance-$r$-based aspects of uniform quasi-
wideness and flip-flatness with the “no edges incident to both $A$ and $B$”
criterion of grid rank. Using our _insulation property_ , one can easily
reprove the characterization of nowhere dense classes in terms of uniform
quasi-wideness [43], of monadically stable classes in terms of flip-flatness
[22], and of classes of ordered graphs with bounded twin-width in terms of
grid rank [7].

Given that flip-breakability characterizes monadically dependent graph classes
and naturally generalizes the previous notions, we believe that it will also
play a crucial role in a future model checking algorithm for monadically
dependent classes: Mirroring the situation for nowhere dense and monadically
stable classes, flip-breakability might lead to a characterization of
monadically dependent classes in terms of a _pursuit-evasion game_. Just like
the previous two algorithms [38, 21, 20], winning strategies for this game
might then be useful for model checking, and settling the backward direction
of 1.1. (Note however that in each of these cases, the games where only one of
the main ingredients of the model checking algorithm).

###### Binary Structures.

Our results apply in the more general setting of binary structures, rather
than graphs, that is, of structures equipped with one or more binary relation.
In particular, we prove that monadically dependent classes of binary
structures can be equivalently characterized in terms of flip-breakability,
defined suitably for binary structures. As an application, we derive a key
result of [7]: that monadically dependent classes of ordered graphs have
bounded grid rank (see definition above).

######  Theorem 1.4 ([7]).

Let $\mathcal{C}$ be a monadically dependent class of ordered graphs. Then
$\mathcal{C}$ has bounded grid rank.

###### Variants of Flip-Breakability.

The previously highlighted similarities between flip-breakability, flip-
flatness, and uniform quasi-wideness suggest the following natural variations
of flip-breakability. We allow to modify the graph using either _(1) flips or
vertex deletions_ and demand that the resulting subset is either _(2) flat or
broken_ , that is, either pairwise separated or separated into two large sets.
We further additionally parameterize the type of separation to be either _(3)
distance-$r$ or distance-$\infty$_. While _distance- $r$_ separation
corresponds to the usual kind given in Definition 1.2, _distance- $\infty$_
separation demands sets to be in different connected components of the graph.
This is formalized by the following definition.

######  Definition 1.5.

A class of graphs $\mathcal{C}$ is _distance- $\infty$ flip-breakable_, if
there exists a function $N:\mathrm{\mathbb{N}}\to\mathrm{\mathbb{N}}$ and a
constant $k\in\mathrm{\mathbb{N}}$ such that for all
$m\in\mathrm{\mathbb{N}}$, $G\in\mathcal{C}$ and $W\subseteq V(G)$ with
$|W|\geqslant N(m)$ there exist subsets $A,B\subseteq W$ with
$|A|,|B|\geqslant m$ and a $k$-flip $H$ of $G$ such that in $H$, no two
vertices $a\in A$ and $b\in B$ are in the same connected component.

Using this terminology, uniform quasi-wideness, for example, becomes
_distance- $r$ deletion-flatness_. For formal definitions of these variants,
we refer to Section 18. As summarized in the following Table 1, each of the
eight possible combinations of (1), (2) and (3) characterizes a well-studied
property of graph classes.

|  |  flatness |  breakability
---|---|---|---
dist-$r$ | flip- |  monadic stability [22] |  monadic dependence (Thm. 13.1)
deletion- |  nowhere denseness [16, 43] |  nowhere denseness (Thm. 18.2)
dist-$\infty$ | flip- |  bd. shrubdepth (Thm. 18.17) |  bd. cliquewidth (Thm. 18.4)
deletion- |  bd. treedepth (Thm. 18.28) |  bd. treewidth (Thm. 18.12)
Table 1: Variants of flip-breakability.

Notably, the right column of Table 1 corresponds to conjectured tractability
limits of the model checking problem, where the distance-$r$ and
distance-$\infty$ variants correspond to, respectively, first-order and
monadic second-order logic, and the flip and deletion variants correspond to
hereditary and monotone classes. Furthermore, it is interesting to see that
the seemingly more general deletion-breakability collapses to deletion-
flatness, as both properties characterize nowhere denseness.

##### Forbidden Induced Subgraphs

Imposing bounds on the size of certain patterns is a common and powerful
mechanism for defining well-behaved graph classes. For example, by definition,
a class $\mathcal{C}$ is _nowhere dense_ if and only if for every
$r\in\mathrm{\mathbb{N}}$, $\mathcal{C}$ avoids some $r$-subdivided clique as
a subgraph. In similar spirit, it is shown [20] that an orderless class
$\mathcal{C}$ is _monadically stable_ if and only if for every
$r\in\mathrm{\mathbb{N}}$, the class $\mathcal{C}$ avoids all $r$-flips of the
$r$-subdivided clique, and its line graph, as an induced subgraph. A similar
characterization for monadically dependent classes has so far been elusive. In
this paper, we show that a class $\mathcal{C}$ is _monadically dependent_ if
and only if for every $r\in\mathrm{\mathbb{N}}$, the class $\mathcal{C}$
avoids certain variations of the $r$-subdivision of some complete bipartite
graph, as an induced subgraph. Let us start by defining these patterns.

For $r\geqslant 1$, the _star $r$-crossing_ of order $n$ is the
$r$-subdivision of $K_{n,n}$. More precisely, it consists of _roots_
$a_{1},\dots,a_{n}$ and $b_{1},\dots,b_{n}$ together with $r$-vertex paths
$\\{\pi_{i,j}\mid i,j\in[n]\\}$ that are pairwise vertex-disjoint (see Figure
4). We denote the two endpoints of a path $\pi_{i,j}$ by
$\mathrm{start}(\pi_{i,j})$ and $\mathrm{end}(\pi_{i,j})$. We require that
roots appear on no path, that each root $a_{i}$ is adjacent to
$\\{\mathrm{start}(\pi_{i,j})\mid j\in[n]\\}$, and that each root $b_{j}$ is
adjacent to $\\{\mathrm{end}(\pi_{i,j})\mid i\in[n]\\}$. The _clique
$r$-crossing_ of order $n$ is the graph obtained from the star $r$-crossing of
order $n$ by turning the neighborhood of each root into a clique. Moreover, we
define the _half-graph $r$-crossing_ of order $n$ similarly to the star
$r$-crossing of order $n$, where each root $a_{i}$ is instead adjacent to
$\\{\mathrm{start}(\pi_{i^{\prime},j})\mid i^{\prime},j\in[n],i\leqslant
i^{\prime}\\}$, and each root $b_{j}$ is instead adjacent to
$\\{\mathrm{end}(\pi_{i,j^{\prime}})\mid i,j^{\prime}\in[n],j\leqslant
j^{\prime}\\}$. Each of the three $r$-crossings contains no edges other than
the ones described. At last, the _comparability grid_ of order $n$ consists of
vertices $\\{a_{i,j}\mid i,j\in[n]\\}$ and edges between vertices $a_{i,j}$
and $a_{i^{\prime},j^{\prime}}$ if and only if either $i=i^{\prime}$, or
$j=j^{\prime}$, or $i<i^{\prime}\Leftrightarrow j<j^{\prime}$.

Figure 4:  (_i_) star 4-crossing of order 4. (_ii_) clique 4-crossing of order
4. (_iii_) half-graph 4-crossing of order 4. (_iv_) comparability grid of
order 4. In (_i_), (_ii_), (_iii_), the roots are adjacent to all vertices in
their respective colorful strip.

It is easy to see that these patterns are logically complicated: For every
fixed $r$, the four graph classes containing these four types of patterns are
monadically independent.

We also need to consider certain flips of the above patterns. To this end, we
partition the vertices of star, clique, and half-graph $r$-crossings into
_layers_ : The 0th layer consists of the vertices $\\{a_{1},\dots,a_{n}\\}$.
The $l$th layer, for $l\in[r]$, consists of the $l$th vertices of the paths
$\\{\pi_{i,j}\mid i,j\in[n]\\}$ (that is, the 1st and $r$th layer,
respectively, are $\\{\mathrm{start}(\pi_{i,j})\mid i,j\in[n]\\}$ and
$\\{\mathrm{end}(\pi_{i,j})\mid i,j\in[n]\\}$). Finally, the $(r+1)$th layer
consists of the vertices $\\{b_{1},\dots,b_{n}\\}$. A _flipped_
star/clique/half-graph $r$-crossing is a graph obtained from a
star/clique/half-graph $r$-crossing by performing a flip where the parts of
the specifying partition are the layers of the $r$-crossing. Note that while
there is only one star/clique/half-graph $r$-crossing of order $n$, there are
multiple flipped star/clique/half-graph $r$-crossings of order $n$. Their
number is however bounded by $2^{(r+2)^{2}}$: an upper bound for the number of
possible flips specified by a single partition of size $(r+2)$.

######  Theorem 1.6.

Let $\mathcal{C}$ be a graph class. Then $\mathcal{C}$ is monadically
dependent if and only if for every $r\geqslant 1$ there exists
$k\in\mathrm{\mathbb{N}}$ such that $\mathcal{C}$ excludes as induced
subgraphs

  * •

all flipped star $r$-crossings of order $k$, and

  * •

all flipped clique $r$-crossings of order $k$, and

  * •

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

  * •

the comparability grid of order $k$.

This characterization by forbidden induced subgraphs opens the door for
various algorithmic, logical, and combinatorial hardness results. On the
algorithmic side, we prove the hardness part of 1.1.

######  Theorem 1.7.

The first-order model checking problem is $\mathrm{AW}[*]$-hard on every
hereditary, monadically independent graph class.

The result builds on the following logical hardness result, which is of
independent interest.

######  Theorem 1.8.

Every hereditary, monadically independent graph class efficiently interprets
the class of all graphs.

Recall that monadically independent classes were defined as those which
transduce the class of all graphs. For hereditary classes, the above result
strengthens this definition: _interpretations_ are a more restrictive version
of transductions, that do not include a nondeterministic coloring step.
Moreover, _efficient_ interpretations come with a polynomial time algorithm
which, given an arbitrary input graph $G$, outputs a graph in $\mathcal{C}$ in
which $G$ is encoded. This allows to reduce the model checking problem for all
graphs to the model checking problem on the class $\mathcal{C}$, thus proving
Theorem 1.7.

On the combinatorial side, we show that no hereditary, monadically independent
graph class is _small_ , has _almost bounded twin-width_ , or has _almost
bounded flip-width_. Let us quickly explain the three notions.

A graph class $\mathcal{C}$ is _small_ if it contains at most $n!c^{n}$
distinct labeled $n$-vertex graphs, for some constant $c$. This notion has
been studied in enumerative combinatorics [42, 46]. It is known that all
classes of bounded twin-width are small [10]. The converse implication was
conjectured, and was subsequently refuted [6]. In the context of ordered
graphs, it was shown that all small classes of ordered graphs have bounded
twin-width [7]. We prove the following.

######  Theorem 1.9.

Every hereditary, small graph class is monadically dependent.

Say that a class $\mathcal{C}$ of graphs has _almost bounded twin-width_ if
for every $\varepsilon>0$ the twin-width of every $n$-vertex graph
$G\in\mathcal{C}$ is bounded by
$O_{\varepsilon,\mathcal{C}}(n^{\varepsilon})$. We prove the following.

######  Theorem 1.10.

Every hereditary, almost bounded twin-width graph class is monadically
dependent.

In [55], a family of graph-width parameters called _flip-width of radius_ $r$,
for $r\geqslant 1$, is introduced, together with the ensuing notion of classes
of _almost bounded flip-width_. Classes of almost bounded flip-width include
all nowhere dense classes, all classes of bounded twin-width, and more
generally, and all classes of almost bounded twin-width. It is conjectured
that for hereditary graph classes, almost bounded flip-width coincides with
monadic dependence:

######  Conjecture 1.11 ([55]).

A hereditary graph class $\mathcal{C}$ has almost bounded flip-width if and
only if it is monadically dependent.

We prove one implication of this conjecture.

######  Theorem 1.12.

Every hereditary, almost bounded flip-width graph class is monadically
dependent.

##### Relation of the Patterns to Other Work

Our forbidden patterns characterization Theorem 1.6 generalizes similar
previous characterizations. Recall that monadic dependence is captured by
monadic stability, for hereditary orderless graph classes, and by bounded
twin-width, for hereditary classes of ordered graphs. The results [20, 7]
characterizing monadic dependence in those two settings can be restated as
follows.

  * •

For orderless graph classes, a class $\mathcal{C}$ is monadically dependent if
and only if for every $r\in\mathrm{\mathbb{N}}$ there exists
$k\in\mathrm{\mathbb{N}}$ such that no graph in $\mathcal{C}$ contains a
flipped star $r$-crossing or clique $r$-crossing of order $k$ as an induced
subgraph [20].

  * •

For classes of ordered graphs, a class $\mathcal{C}$ is monadically dependent
if and only if there exists $k\in\mathrm{\mathbb{N}}$ and a specific, finite
family of ordered graphs with $2k$ vertices (similar to a matching on $2k$
vertices ordered suitably) which are avoided by $\mathcal{C}$ as semi-induced
ordered subgraphs [7] (see Theorem 19.16 for a formulation).

Our approach towards proving the forbidden patterns characterization and model
checking hardness originates in [20] and [7]. As a result, we reprove some of
their results. A subset of the patterns identified in this paper are
sufficient to characterize monadic dependence in the setting of orderless
graph classes. As orderless classes cannot contain large half-graph crossings
or comparability grids, Theorem 1.6 implies the result of [20] characterizing
monadically stable classes in terms of forbidden induced subgraphs. It is
worth noting that in [20], for hereditary, orderless, monadically independent
graph classes, hardness is shown even for _existential_ model checking.
Adapting our results to the setting of binary structures, we show how to
derive the characterization from [7] of monadically dependent classes of
ordered graphs in terms of forbidden patterns.

A recent paper by Braunfeld and Laskowski shows that a hereditary class of
relational structures is monadically dependent if and only if it is dependent
[12]. Dependence is a generalization of monadic dependence studied in model
theory. For the special case of graph classes, our Theorem 1.8 reproves that
result. Similarly to our paper, the proof of Braunfeld and Laskowski exhibits
certain large configurations (called pre-coding configurations) in classes
that are monadically independent. As pre-coding configurations are defined in
terms of formulas with tuples of free variables, these results are not a
purely combinatorial characterization of monadically dependent graph classes.
In particular, they seem insufficient for obtaining algorithmic hardness
results. However, we believe that one could also prove Theorem 1.9, stating
that small, hereditary classes are dependent, using the results of [12].

In [27], Eppstein and McCarty prove that many different types of geometric
graphs have unbounded flip-width, and in fact [27, App. A], form monadically
independent graph classes. These include interval graphs, permutation graphs,
circle graphs, and others. It is shown that these classes contain large
_interchanges_ , which are similar to $1$-subdivided cliques, and to our
patterns. Containing interchanges of arbitrarily large order is a sufficient,
but not necessary condition to monadic independence.

###  2 Technical Overview

All our proofs are fully constructive and only use elementary tools such as
Ramsey’s theorem.

###### Insulators.

In order to prove flip-breakability for a graph $G$ and a large set
$W\subseteq V(G)$, we try to enclose a sizeable subset $W_{\star}\subseteq W$
in a structure $\mathcal{A}$ that “insulates” the elements of $W_{\star}$ from
each other, and from external vertices that are not enclosed in $\mathcal{A}$.
We call this structure $\mathcal{A}$ an _insulator_ (Definition 5.2). It is a
grid-like partition of a subset of $V(G)$. An example is shown on the left
side of Figure 5 (in general, each cell may contain more than one vertex).

Roughly speaking, there is a coloring of the vertex set, using a bounded
number of colors, such that the adjacency between a pair of vertices in non-
adjacent rows of the grid is determined only by their colors. For a pair of
vertices in adjacent rows, the adjacency is determined by their colors and the
order of their columns. Finally, the adjacencies between vertices in the
exterior of the grid and the vertices inside the grid (without the first and
last column, and last row) are determined by their colors. Exceptionally, the
connections within the top row and between adjacent cells of the grid may be
arbitrary.

The large subset $W_{\star}\subseteq W$ is distributed in the bottom row of
the insulator, in a way such that every vertex of $W_{\star}$ is contained in
a different column. Assume the insulator has height at least $r$. We can
choose two large subsets $A$ and $B$ of $W_{\star}$, such that for any two
vertices $v\in A$ and $w\in B$, it takes at least $r$ steps along edges which
are not controlled by the insulator to get from $v$ to $w$.

Figure 5:  Left: An insulator surrounding the set $W_{\star}$. The shown
stacked half-graph layout is easily described by a bounded number of colors
and the column order. A bounded number of flips are sufficient to ensure the
highlighted subsets $A\subseteq W_{\star}$ and $B\subseteq W_{\star}$ have
distance larger than $4$. The shades of red and blue highlight upper bounds on
the distance of other vertices to $A$ and $B$. In particular, all unshaded
vertices have distance larger than two to these sets.

Given $r\in\mathrm{\mathbb{N}}$, we strive for insulators of height $r$, where
the number of colors is bounded by some constant, depending on $r$. Thus, if
we embed large sets $A,B$ in such an insulator and coarsen the columns as
shown on the right side of Figure 5, we can ensure with a bounded number of
flips (depending on the number of colors) that edges only go between adjacent
cells, and thus $A$ and $B$ have distance at least $r$. Hence, we can use the
insulators to obtain flip-breakability.

###### Constructing Insulators or Prepatterns.

One can trivially construct an insulator of height one that embeds a set $W$:
Build a single row by placing every vertex of $W$ into a distinct cell. The
central step of our construction, presented in Part I, takes a large insulator
of height $r$, and adds another row on top to obtain a still-large insulator
of height $r+1$. To this end, we build upon and significantly extend
techniques developed in the context of flip-flatness [22], based on
_indiscernible sequences_ , a fundamental tool in model theory.

Given a large insulator of height $r$ in any graph $G$, the key step in our
construction shows that there is either _enough disorder_ to connect the
topmost row of the grid into a preliminary pattern, called _prepattern_
(Definition 6.3), resembling a crossing (Figure 6, left), or _enough order_ to
add an additional row $r+1$ on top (Figure 6, right). While both cases reduce
the number of columns in the insulator, there still remains a large number of
them.

Figure 6:  In every graph, we can either increase the height of an insulator
of find a large prepattern.

We define _prepattern-free_ classes (Definition 6.4) by excluding certain
prepatterns. In such classes, we therefore always find _enough order_ to
construct _large insulators_ row-by-row (Proposition 7.10). We say that such
classes have the _insulation property_ (Definition 7.2). By the arguments
outlined in Figure 5, such classes are easily shown to be _flip-breakable_
(Proposition 8.1). Lastly, using the locality property of first-order logic,
it is easy to show that _flip-breakable_ classes are monadically dependent
(Proposition 8.8). Thus, any graph class satisfies the following chain of
implications.

$\textnormal{prepattern-
free}~{}\overset{\textnormal{Prop.\,\ref{prop:prepatternImpliesInsulation}}}{\
{=\joinrel=\joinrel=\joinrel\Longrightarrow}\ }~{}\textnormal{insulation
property}~{}\overset{\textnormal{Prop.\,\ref{prop:ge-implies-fb}}}{\
{=\joinrel=\joinrel=\joinrel\Longrightarrow}\ }~{}\textnormal{flip-
breakable}~{}\overset{\textnormal{Prop.\,\ref{prop:fb-implies-mnip}}}{\
{=\joinrel=\joinrel=\joinrel\Longrightarrow}\ }~{}\textnormal{mon.\
dependent}$

###### Cleaning Up Prepatterns.

Afterwards, in Part II, we clean up the prepatterns. This involves heavy use
of Ramsey’s theorem to regularize the patterns until we either obtain a
flipped star/clique/half-graph crossing, or a comparability grid. From such
patterns one can trivially transduce all graphs. This is summarized by the
following chain of implications.

$\neg\textnormal{prepattern-
free}~{}\overset{\,\textnormal{Def.}}{\Leftarrow\joinrel=\joinrel\Rightarrow}~{}\textnormal{large
prepatterns}~{}\overset{\textnormal{Prop.\,\ref{prop:patterns-main}}}{\
{=\joinrel=\joinrel=\joinrel\Longrightarrow}\ }~{}\textnormal{large
patterns}~{}\overset{\textnormal{Prop.\,\ref{lem:transduceAll}}}{\
{=\joinrel=\joinrel=\joinrel\Longrightarrow}\ }~{}\textnormal{mon.\
independent}$

Hence, by contrapositive, monadic dependence implies prepattern-freeness.
Together with the previous chain of implications, we obtain the desired
equivalences.

$\textnormal{insulation property}~{}\Longleftrightarrow~{}\textnormal{flip-
breakable}~{}\Longleftrightarrow~{}\textnormal{no large
patterns}~{}\Longleftrightarrow~{}\textnormal{mon.\ dependent}$

###### Hardness.

Consider a hereditary class $\mathcal{C}$ that is monadically independent. As
discussed, $\mathcal{C}$ contains large patterns witnessing this. To obtain
hardness of model checking, we reduce from the model checking problem in
general graphs. This requires an encoding of an arbitrary graph into a large
pattern, using a first-order formula. We know that when adding colors, such an
encoding is possible: classes that are monadically independent transduce the
class of all graphs. However, for our reduction we require encodings that do
not use colors: we want to show that every hereditary class that is
monadically independent _interprets_ the class of all graphs. Here, an
_interpretation_ is a transduction that does not use colors and where instead
of taking arbitrary induced subgraphs, the vertex set of the interpreted graph
must be definable in the original graph by a formula $\delta(x)$. Heavily
relying on the fact that in hereditary classes we can take induced subgraphs
_before_ applying the interpretation, it is not too hard to show that for each
$r\geqslant 1$, the hereditary closures of the class of all comparability
grids and the classes of all _non-flipped_ star/clique/half-graph
$r$-crossings interpret the class of all graphs. The main challenge is to
“reverse” the flips using first-order formulas in the case of _flipped_
$r$-crossings. This is achieved by using sets of twins to mark layers of the
$r$-crossing.

###  3 Conclusions and Future Work

In this paper, we obtain the first combinatorial characterizations of
monadically dependent graph classes, which open the way to generalizing the
results of sparsity theory to the setting of hereditary graph classes. Our
main results, Theorem 1.3 and Theorem 1.6, may be seen as analogues of the
result [43] characterizing nowhere dense graph classes as exactly the
_uniformly quasi-wide_ classes [16], and the result [2, 49] characterizing
nowhere dense classes as exactly those, whose monotone closure is monadically
dependent.

Central results in sparsity theory, characterizing nowhere dense classes, can
be usually grouped into two types: _qualitative characterizations_ and
_quantitative characterizations_. Qualitative characterizations typically say
that for every radius $r$, some quantity is bounded by a constant depending on
$r$ for all graphs in the class. Our two main results fall within this
category.

On the other hand, quantitative characterizations of nowhere dense classes are
phrased in terms of a fine analysis of densities of some parameters, such as
degeneracy, minimum degree, weak coloring numbers, neighborhood complexity, or
VC-density; those results almost always involve bounds of the form
$n^{\varepsilon}$ or $n^{1+\varepsilon}$, where $n$ is the number of vertices
of the considered graph, and $\varepsilon>0$ can be chosen arbitrarily small.
For instance, given a nowhere dense graph class $\mathcal{C}$, for every fixed
$r\in\mathrm{\mathbb{N}}$ and $\varepsilon>0$, all graphs $G$ whose
$r$-subdivision is a subgraph of a graph in $\mathcal{C}$ satisfy

$|E(G)|\leqslant O_{\mathcal{C},r,\varepsilon}(|V(G)|^{1+\varepsilon}).$

Similarly, a parameter called the _weak $r$-coloring number_ (for any fixed
$r\in\mathrm{\mathbb{N}}$, $\varepsilon>0$), is bounded by
$O_{\mathcal{C},r,\varepsilon}(n^{\varepsilon})$, for every $n$-vertex graph
$G$ in a nowhere dense class.

Both the qualitative and quantitative results are of fundamental importance in
sparsity theory, and lifting them to the setting of monadically dependent
graph classes is therefore desirable. Some of the most elaborate results of
sparsity theory combine both aspects of the theory. In particular for nowhere
dense model checking [38], the _splitter game_ [38] – a qualitative
characterization – is combined with the quantitative characterization in terms
of weak coloring numbers. The characterization in terms of the splitter game
relies on uniform quasi-wideness, and has been extended to the setting of
monadically stable graph classes, in terms of the flipper game [32], which in
turn relies on the characterization in terms of flip-flatness. Basing on this,
we believe that flip-breakability may be a first step towards obtaining a game
characterization of monadic dependence.

As we observe now, our results also provide a first quantitative
characterization of monadically dependent classes. As an analogue of the
notion of _containing the $r$-subdivision of a graph as a subgraph_, we
introduce the following concept of _radius- $r$ encodings_. Fix an integer
$r\geqslant 1$. Let $G=(A,B,E)$ be a bipartite graph with $|A|=|B|=n$ for some
$n$, and let $A=\\{a_{1},\ldots,a_{n}\\}$ and $B=\\{b_{1},\ldots,b_{n}\\}$.
Consider a graph $H$ which is a star/clique/half-graph $r$-crossing with roots
$a_{1},\ldots,a_{n}$ and $b_{1},\ldots,b_{n}$. Recall that $V(H)$ can be
partitioned into $r+2$ _layers_ , and there are $n^{2}$ distinguished
$r$-vertex _paths_ $\pi_{i,j}$ connecting $a_{i}$ and $b_{j}$, for
$i,j\in[n]$. Let $H^{\prime}$ be a graph obtained from $H$ by:

  1. 1.

adding arbitrary edges within each layer of $H$,

  2. 2.

removing all vertices of the paths $\pi_{i,j}$ for $i,j\in[n]$ such that
$\\{a_{i},b_{j}\\}\notin E(G)$,

  3. 3.

flipping pairs of layers arbitrarily.

We call $H^{\prime}$ a _radius- $r$ encoding of $G$_. In particular, every
flipped star/clique/half-graph $r$-crossing of order $n$ is a radius-$r$
encoding of the complete bipartite graph $K_{n,n}$. Moreover, the
comparability grid of order $n+1$ contains as an induced subgraph a radius-$1$
encoding of the complete bipartite graph $K_{n,n}$, which can be obtained from
the half-graph $1$-crossing of order $n+1$ by adding edges within the three
layers.

The following result follows easily from our Theorem 13.1, and from results of
Dvořák [23, 24].

######  Theorem 3.1.

Let $\mathcal{C}$ be a hereditary graph class. The following conditions are
equivalent:

  1. (i)

$\mathcal{C}$ is monadically dependent,

  2. (ii)

for every real $\varepsilon>0$ and integer $r\geqslant 1$, for every bipartite
graph $G$ such that $\mathcal{C}$ contains some radius-$r$ encoding of $G$, we
have that $|E(G)|\leqslant
O_{\mathcal{C},r,\varepsilon}(|V(G)|^{1+\varepsilon})$,

  3. (iii)

for every integer $r\geqslant 1$ there is an integer $N\geqslant 1$ such that
for every bipartite graph $G$ with $|V(G)|>N$ such that $\mathcal{C}$ contains
some radius-$r$ encoding of $G$, we have that $|E(G)|<\frac{|V(G)|^{2}}{4}$.

Theorem 3.1 may be a first step towards developing a quantitative theory of
monadically dependent classes. A challenging goal here is to generalize the
characterization of nowhere denseness in terms of weak coloring numbers, to
monadically dependent classes.

###### Flip-width.

The _flip-width_ parameters were introduced [55] with the aim of obtaining
quantitative characterizations of monadic dependence. The flip-width at radius
$r\geqslant 1$, denoted $\operatorname{fw}_{r}(\cdot)$, is an analogue of the
weak $r$-coloring number, and the notion of classes of bounded flip-width, and
almost bounded flip-width, generalize classes of bounded expansion and nowhere
dense classes to the dense setting. A graph class $\mathcal{C}$ has _bounded
flip-width_ if for every integer $r\geqslant 1$ there is a constant $k_{r}$
such that $\operatorname{fw}_{r}(G)\leqslant k_{r}$ for all graphs
$G\in\mathcal{C}$. A hereditary graph class $\mathcal{C}$ has _almost bounded
flip-width_ if for every integer $r\geqslant 1$ and real $\varepsilon>0$ we
have $\operatorname{fw}_{r}(G)\leqslant
O_{\mathcal{C},r,\varepsilon}(n^{\varepsilon})$ for all $n$-vertex graphs
$G\in\mathcal{C}$. 1.11 – equating monadic dependence with almost bounded
flip-width – therefore postulates a quantitative characterization of monadic
dependence, parallel to the characterization of nowhere denseness in terms of
weak coloring numbers.

As mentioned, our results imply the forward implication of 1.11: that every
hereditary class of almost bounded flip-width is monadically dependent.
Theorem 3.1 might be an initial step towards resolving the backwards direction
in 1.11, as by Theorem 3.1, 1.11 is equivalent to the following:

######  Conjecture 3.2.

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

  1. (i)

for every real $\varepsilon>0$ and integer $r\geqslant 1$, for every bipartite
graph $G$ such that $\mathcal{C}$ contains some radius-$r$ encoding of $G$, we
have:

$\frac{|E(G)|}{|V(G)|}\leqslant
O_{\mathcal{C},r,\varepsilon}(|V(G)|^{\varepsilon}),$

(equivalently, by Theorem 3.1, $\mathcal{C}$ is monadically dependent)

  2. (ii)

$\mathcal{C}$ has almost bounded flip-width: For every real $\varepsilon>0$
and integer $r\geqslant 1$, and graph $G\in\mathcal{C}$, we have:

$\operatorname{fw}_{r}(G)\leqslant
O_{\mathcal{C},r,\varepsilon}(|V(G)|^{\varepsilon}).$

Note that the implication ($ii$)$\rightarrow$($i$) in 3.2 holds, by Theorem
3.1 and Theorem 1.12. The following conjecture would imply the converse
implication.

######  Conjecture 3.3.

For every $r\geqslant 1$ there are integers $s,k\geqslant 1$ such that for
every graph $G$ we have:

$\operatorname{fw}_{r}(G)\leqslant\max_{H}\left(\frac{|E(H)|}{|V(H)|}\right)^{k},$

where the maximum ranges over all bipartite graphs $H$ such that $G$ contains
some radius-$s$ encoding of $H$ as an induced subgraph.

An analogue of 3.3 holds in the sparse setting. There, the flip-width
parameters are replaced by weak coloring numbers, and the maximum ranges over
all graphs $H$ such that $G$ contains some $s$-subdivision of $H$ as a
subgraph. 3.3 would furthermore imply the following characterization of
classes of bounded flip-width, analogous to a known characterization of
classes with bounded expansion in terms of weak coloring numbers [56].

######  Conjecture 3.4.

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

  1. (i)

for every integer $r\geqslant 1$ there is a constant $k_{r}$ such that for
every bipartite graph $G$ such that $\mathcal{C}$ contains some radius-$r$
encoding of $G$, we have that $|E(G)|\leqslant k_{r}\cdot|V(G)|$,

  2. (ii)

$\mathcal{C}$ has bounded flip-width: For every integer $r\geqslant 1$ there
is a constant $k_{r}$ such that for every graph $G\in\mathcal{C}$, we have
that $\operatorname{fw}_{r}(G)\leqslant k_{r}$.

Note that the implication ($ii$)$\rightarrow$($i$) follows from the results of
[55] (that every weakly sparse transduction of a class of bounded flip-width
has bounded expansion). The converse implication would resolve Conjecture 11.4
from [55], which predicts that if a class $\mathcal{C}$ has unbounded flip-
width, then $\mathcal{C}$ transduces a weakly sparse class of unbounded
expansion.

###### Near-twins.

A specific goal, not involving flip-width, which would be implied by the above
conjectures, can be phrased in terms of _near-twins_. Say that two distinct
vertices $u,v$ in a graph $G$ are $k$-near-twins, where
$k\in\mathrm{\mathbb{N}}$, if the symmetric difference of the neighborhoods of
$u$ and of $v$ consists of at most $k$ vertices. It is known [55] that every
graph $G$ with more than one vertex contains a pair of
$(2\operatorname{fw}_{1}(G))$-near-twins. Consequently, for every class
$\mathcal{C}$ of bounded flip-width there is a constant $k$ such that every
graph $G\in\mathcal{C}$ with more than one vertex contains a pair of $k$-near-
twins. Similarly, if $\mathcal{C}$ has almost bounded flip-width then every
$n$-vertex graph $G\in\mathcal{C}$ with $n>1$ contains a pair of
$O_{\mathcal{C},\varepsilon}(n^{\varepsilon})$-near-twins.

Therefore, a first step towards 1.11 is to prove that for all monadically
dependent classes, every $n$-vertex graph $G\in\mathcal{C}$ with $n>1$
contains a pair of $O_{\mathcal{C},\varepsilon}(n^{\varepsilon})$-near-twins.
Similarly, a step towards 3.4 is to prove the following consequence of
Conjecture 3.3 (in the case $r=1$), stated below.

######  Conjecture 3.5.

There is an integer $s\geqslant 1$ and an unbounded function
$f\colon\mathrm{\mathbb{N}}\to\mathrm{\mathbb{N}}$ such that every graph $G$
with more than one vertex and no pair of $d$-near twins, for some
$d\in\mathrm{\mathbb{N}}$, contains as an induced subgraph a radius-$s$
encoding of some bipartite graph $H$ with $|E(H)|/|V(H)|\geqslant f(d)$.

###### VC-density and Neighborhood Complexity.

Another, related conjecture [20, Conj. 2] bounds the _neighborhood complexity_
, or _VC-density_ of set systems defined by neighborhoods in graphs from a
monadically dependent graph class, and is phrased as follows.

######  Conjecture 3.6 ([20]).

Let $\mathcal{C}$ be a monadically dependent graph class and let
$\varepsilon>0$ be a real. Then for every graph $G\in\mathcal{C}$ and set
$A\subseteq V(G)$, we have that

$|\\{N(v)\cap A:v\in V(G)\\}|\leqslant
O_{\mathcal{C},\varepsilon}(|A|^{1+\varepsilon}).$

This conjecture is confirmed for all nowhere dense classes [26, 48], for all
monadically stable classes [20], and for all classes of bounded twin-width [8,
50].

###  4 Preliminaries

###### Sequences.

To address and order the combinatorial objects of this paper, we use _indexing
sequences_. These are sequences (usually denoted by $I,J$) of elements without
duplicates. We denote the sequence $(1,\dots,n)$ also sometimes by $[n]$. We
write $I\subseteq J$ if $I$ is a subsequence of $J$. We use the usual
comparison operators $<,>$ to indicate the order of elements within a
sequence. Given a sequence $I$, and an element $i\in I$, we denote by
$\mathrm{pred}_{I}(i)$ and $\mathrm{succ}_{I}(i)$ the predecessor and
successor of $i$ in $I$. Moreover, if $I=(a_{1},\ldots,a_{n})$, we define
$\mathrm{tail}(I):=(a_{2},\ldots,a_{n})$.

###### Graphs.

All graphs are simple and undirected. Unless a graph $G$ is considered to be
an input to an algorithm, we do not need to assume that $G$ is a finite graph.

The _length_ of a path equals its number of edges. The _distance_ between two
vertex sets $A$ and $B$ in a graph $G$, denoted by
$\textnormal{dist}_{G}(A,B)$, is the length of a shortest path with endpoints
in $A$ and $B$. Two sets $A,B$ are _non-adjacent_ if
$\textnormal{dist}(A,B)>1$. The _open_ and _closed $r$-neighborhoods_ of a
vertex $v$ are denoted, respectively, by

$N^{G}_{r}[u]=\\{v\in
V(G)\mid\textnormal{dist}_{G}({\\{u\\},\\{v\\}})\leqslant
r\\},\quad\quad\quad\quad N^{G}_{r}(u)=N^{G}_{r}[u]\setminus\\{v\\}.$

The _complement graph_ of a graph $G$ is denoted by $\bar{G}$. By default,
graphs have no colors, but we speak of _colored graphs_ when we allow vertex-
colors. In this case we treat the colors as a fixed set of unary predicates
which partition the vertex set, that is, each vertex has exactly one color. We
call $G^{+}$ an _$s$ -coloring of $G$_, if $G^{+}$ is obtained by coloring $G$
with $s$ many colors.

A _graph class_ is a set $\mathcal{C}$ of graphs. (In Section 17 we
additionally assume that $V(G)\subseteq\mathrm{\mathbb{N}}$ for all
$G\in\mathcal{C}$, and that $\mathcal{C}$ is closed under isomorphism, but
this assumption is not essential in other sections.) A graph class
$\mathcal{C}$ is _hereditary_ if for every graph $G\in\mathcal{C}$ and set
$W\subseteq V(G)$ we have that $G[W]\in\mathcal{C}$, where $G[W]$ denotes the
subgraph of $G$ induced by $W$.

###### Flips.

Fix a graph $G$ and a partition $\mathcal{K}$ of its vertices. We will think
of $\mathcal{K}$ as a coloring of the vertices of $G$. For every vertex $v\in
V(G)$ we denote by $\mathcal{K}(v)$ the unique color $X\in\mathcal{K}$
satisfying $v\in X$. Let $F\subseteq\mathcal{K}^{2}$ be a symmetric relation.
The _flip_ $G\oplus_{\mathcal{K}}F$ of $G$ is defined as the (undirected)
graph with vertex set $V(G)$, and edges defined by the following condition,
for distinct $u,v\in V(G)$:

$\\{u,v\\}\in
E(G\oplus_{\mathcal{K}}F)\Leftrightarrow\begin{cases}\\{u,v\\}\notin
E(G)&\text{if }(\mathcal{K}(u),\mathcal{K}(v))\in F,\\\ \\{u,v\\}\in
E(G)&\text{otherwise.}\end{cases}$

We call $G\oplus_{\mathcal{K}}F$ a _$\mathcal{K}$ -flip_ of $G$. If
$\mathcal{K}$ has at most $k$ parts, we say that $G\oplus_{\mathcal{K}}F$ a
_$k$ -flip_ of $G$. A crucial property of flips is that they are reversible
using first order-logic. We can recover the edges of the original graph in a
coloring of its flip as follows. Let $H:=G\oplus_{\mathcal{K}}F$ and $H^{+}$
be the coloring of $H$ where each part of $\mathcal{K}$ is assigned its own
color. Define the symmetric binary formula

$\varphi_{\mathcal{K},F}(x,y):=x\neq y\wedge\bigvee_{X,Y\in\mathcal{K}}x\in
X\wedge y\in Y\wedge\bigl{(}E(x,y)\texttt{ XOR }(X,Y)\in F\bigr{)}.$

We now have $G\models E(u,v)\Leftrightarrow
H^{+}\models\varphi_{\mathcal{K},F}(u,v).$

###### Logic.

All formulas are over the signature of (possibly colored) graphs. Let
$\alpha(x;y_{1},\ldots,y_{k})$ be a formula, with free variables partitioned
into $x$ and $y_{1},\ldots,y_{k}$, as indicated by the colon. Given a graph
$G$, vertices $v_{1},\ldots,v_{k}$, and a set $U\subseteq V(G)$, we denote

$\alpha(U;v_{1},\ldots,v_{k}):=\\{u\in
U:G\models\alpha(u;v_{1},\ldots,v_{k})\\}.$

Let $G^{+}$ be a graph with colors $U_{1},\ldots,U_{l}$. The _atomic type_ of
a tuple $\bar{v}=(v_{1},\ldots,v_{k})$ of vertices in $G^{+}$ is the
quantifier-free formula $\alpha(x_{1},\ldots,x_{k})$ defined as the
conjunction of all literals $\beta(x_{1},\ldots,x_{k})$ (that is, formulas
$x_{i}=x_{j}$, $E(x_{i},x_{j})$, $U_{1}(x_{i}),\ldots,U_{l}(x_{i})$, or their
negations) such that

$G^{+}\models\beta(\bar{v}).$

We write $\mathrm{atp}_{G^{+}}(v_{1},\ldots,v_{k})$ to denote the atomic type
of $\bar{v}$ in $G^{+}$.

###### Transductions and Monadic Dependence.

In the Introduction we defined the notions that a graph class $\mathcal{C}$
_transduces_ a graph class $\mathcal{D}$, and that a graph class $\mathcal{C}$
is monadically dependent. See Section 19.1 for a more formal treatment.

###### Computation Model.

Our proofs are effective. In the algorithmic statements, we assume that the
input graph is represented by its adjacency matrix. We assume the standard
word RAM model of computation, with machine words of length $O(\log n)$, where
$n$ is the size of the input. In this model, it is possible to store each
vertex of the input graph in a single machine word, and to determine the
adjacency of two vertices in time $O(1)$.

###### Asymptotic Notation.

We introduce two new notations that simplify our statements and proofs.

> $\mathrm{const}(p_{1},\ldots,p_{k})$ denotes a natural number, only
> depending on the parameters $p_{1},\ldots,p_{k}$.

We allow parameters of any kind, in particular, graph classes. Moreover, as an
analogue of the $O$-notation,

> $U_{p_{1},\ldots,p_{k}}(n)$ denotes an anonymous function that is non-
> negative and unbounded in $n$, and only depends on the parameters
> $p_{1},\ldots,p_{k}$.

More precisely, the $i$th occurrence of the notation
$U_{p_{1},\ldots,p_{k}}(n)$ in the text should be interpreted as
$f^{i}_{p_{1},\ldots,pk}(n)$, for some fixed unbounded function
$f^{i}_{p_{1},\ldots,p_{k}}:\mathrm{\mathbb{N}}\rightarrow\mathrm{\mathbb{N}}$
that depends only on the parameters $p_{1},\ldots,p_{k}$ and $i$. To
illustrate the use, we state Ramsey’s theorem with this notation.

######  Example 4.1.

For every $k$-coloring of the edges of the complete graph on vertex set $[n]$,
there exists a set $X\subseteq[n]$ of size $U_{k}(n)$ which induces a
monochromatic clique.

###### Ramsey Theory.

For $\ell\in\mathrm{\mathbb{N}}$ and a set $I$, let $I^{(\ell)}$ denote the
set of subsets $J\subseteq I$ of size $\ell$.

######  Lemma 4.2 (Ramsey’s Theorem, [51]).

For every $k,\ell,n\in\mathrm{\mathbb{N}}$ there exists
$N\in\mathrm{\mathbb{N}}$ such that for every

$c\colon[N]^{(\ell)}\to[k]$

there is some $I\in[N]^{(n)}$ such that $c(J)=c(J^{\prime})$ for all
$J,J^{\prime}\in I^{(\ell)}$.

Moreover, there is a function
$f\colon\mathrm{\mathbb{N}}^{3}\to\mathrm{\mathbb{N}}$ such that for every
$k,\ell\in\mathrm{\mathbb{N}}$ the function $m\mapsto f(k,\ell,m)$ is monotone
and unbounded, and there is an algorithm that, given numbers
$k,\ell,m\in\mathrm{\mathbb{N}}$ and a function $c\colon[m]^{(\ell)}\to[k]$,
computes in time $O_{k,\ell}(m^{\ell})$ a set $I\subseteq[m]$ of size
$f(k,\ell,m)$ such that $c(J)=c(J^{\prime})$ for all $J,J^{\prime}\in
I^{(\ell)}$.

See, e.g., [51, Thm. C] or [35, Thm. 5.4] for a (standard) proof of Lemma 4.2.
The “moreover” part of the statement above follows by tracing the
construction, which proceeds by induction on $\ell$, where in each stage of
the construction we iterate over some subset of $[m]$.

For a pair $(a,b)$ of elements of a linearly ordered set $(A,\leqslant)$, let
$\mathrm{otp}(a,b)\in\\{<,=,>\\}$ indicate whether $a<b$, $a=b$, or $a>b$
holds. For $\ell\geqslant 1$ and an $\ell$-tuple of elements
$a_{1},\ldots,a_{\ell}$ of a linearly ordered set $(A,\leqslant)$, define the
_order type_ of $(a_{1},\ldots,a_{\ell})$, denoted
$\mathrm{otp}(a_{1},\ldots,a_{\ell})$ as the tuple
$(\mathrm{otp}(a_{i},a_{j}))_{1\leqslant i<j\leqslant\ell}$.

We now reformulate Ramsey’s theorem using the $U$-notation, and also so that
it talks about $\ell$-tuples, rather than $\ell$-element subsets.

######  Lemma 4.3 (Reformulation of Ramsey’s Theorem).

For every $k,\ell,n$ and coloring

$c\colon[n]^{\ell}\to[k]$

there is a subset $I\subseteq[n]$ of size $U_{k,\ell}(n)$ such that
$c(a_{1},\ldots,a_{\ell})$ depends only on
$\mathrm{otp}(a_{1},\ldots,a_{\ell})$, for all $(a_{1},\ldots,a_{\ell})\in
I^{\ell}$.

Moreover, there is an algorithm that, given $c$, computes $I$ in time
$O_{k,\ell}(n^{\ell})$.

The conclusion of the lemma means that there is a function $f$ such that
$c(a_{1},\ldots,a_{\ell})=f(\mathrm{otp}(a_{1},\ldots,a_{\ell}))$, for all
$(a_{1},\ldots,a_{\ell})\in I^{\ell}$.

######  Lemma 4.4 (Bipartite Ramsey Theorem).

For every $k,\ell_{1},\ell_{2},n$ and coloring

$c\colon[n]^{\ell_{1}}\times[n]^{\ell_{2}}\to[k]$

there are subsets $I_{1},I_{2}\subseteq[n]$ of size
$U_{k,\ell_{1},\ell_{2}}(n)$ such that $c(\bar{a},\bar{b})$ depends only on
$\mathrm{otp}(\bar{a})$ and $\mathrm{otp}(\bar{b})$, for all $\bar{a}\in
I_{1}^{\ell_{1}}$ and $\bar{b}\in I_{2}^{\ell_{2}}$.

The conclusion of the lemma means that there is a function $f$ such that
$c(\bar{a},\bar{b})=f(\mathrm{otp}(\bar{a}),\mathrm{otp}(\bar{b}))$, for all
$\bar{a}\in I_{1}^{\ell_{1}}$ and $\bar{b}\in I_{2}^{\ell_{2}}$.

###### Proof.

Set $\ell=\ell_{1}+\ell_{2}$. The coloring $c$ can be viewed as a coloring
$c\colon[n]^{\ell}\to[k]$. By Lemma 4.3, there is a subset $I\subseteq[n]$ of
size $U_{k,\ell}(n)$ such that the restriction of $c$ to $I$ is homogeneous,
that is, $c(\bar{a})$ depends only on $\mathrm{otp}(\bar{a})$ for $\bar{a}\in
I^{\ell}$. We can assume that $|I|$ is even. Let $I_{1}$ be the first $|I|/2$
elements of $I\subseteq[n]$, and $I_{2}$ be the remaining $|I|/2$ elements of
$I$. Then $|I_{1}|=|I_{2}|\geqslant U_{k,\ell}(n)$. Let
$(\bar{a},\bar{b}),(\bar{a}^{\prime},\bar{b}^{\prime})\in
I_{1}^{\ell_{1}}\times I_{2}^{\ell_{2}}$ be two pairs such that
$\mathrm{otp}(\bar{a})=\mathrm{otp}(\bar{a}^{\prime})$ and
$\mathrm{otp}(\bar{b})=\mathrm{otp}(\bar{b}^{\prime}).$ Then
$\mathrm{otp}(\bar{a},\bar{b})=\mathrm{otp}(\bar{a}^{\prime},\bar{b}^{\prime})$,
since $\mathrm{otp}(a,b)={<}$ for all $a\in I_{1}$ and $b\in I_{2}$.
Therefore, $c(\bar{a},\bar{b})=c(\bar{a}^{\prime},\bar{b}^{\prime})$, by
homogeneity of $c$ restricted to $I$. ∎

##  Part I Structure

In this part we define three tameness conditions for graph classes:

  * •

_Prepattern-freeness_ : the absence of certain combinatorial obstructions
called _prepatterns_.

  * •

_Insulation property_ : the ability to guard any vertex set using so-called
_insulators_.

  * •

_Flip-breakability_ : the ability to break any vertex set into two distant
parts using few flips.

We show that for any graph class the following implications hold:

$\text{prepattern-free}\quad\Rightarrow\quad\text{insulation-
property}\quad\Rightarrow\quad\text{flip-
breakable}\quad\Rightarrow\quad\text{mon.\ dependent}$

We later close the circle of implications in Part II, where we show:

$\text{not prepattern-free}\quad\Rightarrow\quad\text{large flipped
crossings/comparability grids}\quad\Rightarrow\quad\text{mon.\ independent}$

###  5 Grids and Insulators

###### Grids.

The most basic building block of this section is the notion of _grids_.

######  Definition 5.1 (Grids).

Fix a non-empty sequence $I$ and an integer $h\geqslant 1$. A _grid_ $A$
_indexed by_ $I$ and of _height_ $h$ in a graph $G$ is a collection of
pairwise disjoint sets $A[i,r]\subseteq V(G)$, for $i\in I$ and $r\in[h]$,
called _cells_. Each grid is either tagged as _orderless_ or _ordered_.

To facilitate notation, we often assume, up to renaming, the indexing sequence
to be $I=(1,\ldots,n)$. We do so in the following. For subsets $J\subseteq I$
and $R\subseteq[h]$, we write $A[J,R]=\bigcup_{i\in J,r\in R}A[i,r]$. We often
use implicitly defined sets via wildcards and comparisons. For example
$A[{\leqslant}i,*]$ stands for $A\bigl{[}\\{1,\dots,i\\},[h]\bigr{]}$. In
particular, we use $A[i,*]:=\bigcup_{r\in[h]}A[i,r]$ and
$A[*,r]:=\bigcup_{i\in I}A[i,r]$, and refer to those sets as to _columns_ and
_rows_ of $A$, respectively. In slight abuse of notation, we often write $A$
instead of $A[*,*]$ to denote the set of all elements inside the grid. We
define the _interior_ of $A$ as $\mathrm{int}(A):=A\setminus(A[1,*]\cup
A[n,*]\cup A[*,h])$. Moreover, we say two columns $A[i,*]$ and $A[j,*]$ are
_close_ , if $|i-j|\leqslant 1$ and two rows $A[*,r]$ and $A[*,t]$ are _close_
, if $|r-t|\leqslant 1$. Two cells are _close_ if their respective columns and
rows are close.

Note that unlike standard matrix notation, to highlight the hierarchical
relationship between columns and rows, our notation $A[i,r]$ first mentions
the column index $i\in I$ and then the row index $r\in[h]$.

###### Insulators.

The following notion of _insulators_ serves a twofold purpose. On the one
hand, insulators enforce the necessary structure to obtain _flip-breakability_
(see Section 8). On the other hand, in Part II, we use insulators to build the
patterns presented in Theorem 1.6.

######  Definition 5.2 (Insulators).

An _insulator_ $\mathcal{A}=(A,\mathcal{K},F,R)$ _indexed by a sequence $I$_
of _height_ $h$ and _cost_ $k$ in a graph $G$ consists of

  * •

a grid $A$ indexed by $I$ and of height $h$,

  * •

a partition $\mathcal{K}$ of $V(G)$ into at most $k$ color classes,

  * •

a symmetric relation $F\subseteq\mathcal{K}^{2}$ specifying a flip
$G^{\prime}:=G\oplus_{\mathcal{K}}F$,

  * •

a relation $R\subseteq\mathcal{K}^{2}$.

We furthermore say that $\mathcal{A}$ is _orderless_ (_ordered_), if $A$ is
_orderless_ (_ordered_).

If $\mathcal{A}$ is _orderless_ , we demand:

  1. (U.$1$)

For all $i\in I$ there exists $a_{i}\in V(G)$ such that

$A[i,1]=\\{a_{i}\\}\quad\text{and}\quad
A[i,{\leqslant}r]=N^{G^{\prime}}_{r-1}[a_{i}]\text{ for all }r\in[h].$

$\blacktriangleright$ In particular, a column of an orderless insulator is
just the radius $h-1$ ball in a $k$-flip around single vertex sitting in the
bottom cell of that column.

If $\mathcal{A}$ is _ordered_ , we demand:

  1. (O.$1$)

If two vertices are in different rows of $A$, then they have different colors
in $\mathcal{K}$.

$\blacktriangleright$ This technical property ensures that the rows of the
insulator are sufficiently distinguishable. We will use this to argue that
certain modifications on the insulator can be performed without increasing its
cost.

  2. (O.$2$)

Every vertex $v\in A[i,r]$ with $r>1$, $i\in I$ has a neighbor in the cell
$A[i,r-1]$ in $G^{\prime}$.

$\blacktriangleright$ The mandatory downward edge, together with
(O.$4$)(O.4$.2$) and (O.$5$), ensures that each column is cohesive: we will
later observe that the columns of the insulator are first-order definable.
This property is crucial to obtain hardness results.

  3. (O.$3$)

For every $v\notin A[*,*]$ and $X\in\mathcal{K}$ we require that $v$ is
_homogeneous_ to $X\cap\mathrm{int}(A)$ in $G$
(that is, either all or no vertices in $X\cap\mathrm{int}(A)$ are adjacent to
$v$).

$\blacktriangleright$ The inside of the insulator is “insulated” from its
outside: the adjacencies between the two are described using only colors.

  4. (O.$4$)

For every $u\in A[i,r]$ with $r<h$, $i\in I$ and $v\in A$ we have the
following:
(Up to renaming, we assume $I=(1,\ldots,n)$.)

    1. (O.4$.1$)

If $u$ and $v$ are in rows that are not close and $u\in\mathrm{int}(A)$,
then they are non-adjacent in $G^{\prime}$.

    2. (O.4$.2$)

If $v\in A[{<}i,r-1]\cup A[{>}i,r+1]$, then $u$ and $v$ are non-adjacent in
$G^{\prime}$.

    3. (O.4$.3$)

If $v\in A[{>}i+1,\\{r,r-1\\}]$, then $G\models
E(u,v)\Leftrightarrow(\mathcal{K}(u),\mathcal{K}(v))\in R$.

    4. (O.4$.4$)

If $v\in A[{<}i-1,\\{r,r+1\\}]$, then $G\models
E(u,v)\Leftrightarrow(\mathcal{K}(v),\mathcal{K}(u))\in R$.

Otherwise, we make no claims regarding the adjacency of $u$ and $v$.

$\blacktriangleright$ Properties (O.$4$)(O.4$.1$), (O.$4$)(O.4$.3$), and
(O.$4$)(O.4$.4$) provide vertical and horizontal insulation inside the
insulator. Property (O.$4$)(O.4$.2$) helps to keep each column cohesive. See
Figure 7 for an illustration.

Figure 7: Illustration of how (O.$4$) controls the adjacency of a vertex $u$
within the insulator.

  5. (O.$5$)

There exists a bound $r<h$ and a $k$-flip $H$ of $G$ such that for every two
distinct vertices $u,v\in A[*,1]$.

$N_{r}^{H}[u]\cap N_{r}^{H}[v]=\varnothing.$

Moreover, there are vertices $\\{b(v)\in N_{r}^{H}[v]:v\in A[*,1]\\}$ and
$\\{c_{i}\in V(G):i\in I\\}$ and a symbol
${\sim}\in\\{{\leqslant},{\geqslant}\\}$ such that for every $i,j\in I$, $v\in
A[j,1]$ and

$G\models E(c_{i},b(v))\quad\text{if and only if}\quad i\sim j.$

$\blacktriangleright$ This property orders the columns. It will later be used
to first-order define the columns as intervals in the order.

######  Observation 5.3.

Every orderless insulator $\mathcal{A}=(A,\mathcal{K},F,R)$ where $F=R$ also
satisfies the properties (O.$2$), (O.$3$), and (O.$4$) of an ordered
insulator. Since the requirements of an orderless insulator put no
restrictions on $R$, in the orderless case we can always assume $F=R$.

Two example insulators are depicted in Figure 8.

Figure 8: On the left: an orderless insulator. Each column is just the ball
(in a flip) around the single vertex of its bottom cell. Apart from the
boundary, there are no connections in between columns. On the right: an
ordered insulator. It contains connections between columns, but they are well
controlled by property (O.$4$). Property (O.$5$) is witnessed by the
highlighted vertices. The purple $b(\cdot)$ vertices are contained in disjoint
radius $r=1$ balls around the vertices of the bottom cell. They are preordered
by the yellow $c(\cdot)$ vertices.

We will often identify an insulator $\mathcal{A}$ and its underlying grid $A$,
and write, for example $v\in\mathcal{A}$ to indicate that $v\in A[*,*]$. We
start by observing basic properties of insulators. The following property will
be crucial to obtain the model checking hardness result.

######  Lemma 5.4.

The columns of an insulator are definable in first-order logic in a coloring
of $G$.

More precisely: Let $\mathcal{A}$ be an insulator with grid $A$ of cost $k$
and height $h$ indexed by $I$ in a graph $G$. There exists a formula
$\alpha(x,y)$ (depending only on $k$ and $h$), a
$\mathrm{const}(k,h)$-coloring $G^{+}$ of $G$, and vertices $\\{a_{i}:i\in
I\\}$ such that for each $i\in I$

$A[i,*]=\\{v\in V(G):G^{+}\models\alpha(v,a_{i})\\}.$

We do not rely directly on this lemma, as we will later further process
insulators before proving hardness. However, we sketch a proof for instructive
purposes.

###### Proof sketch for Lemma 5.4.

All the formulas we write will work in a $\mathrm{const}(k,h)$-coloring
$G^{+}$ of $G$, but we omit the details of the coloring to streamline the
presentation. If $\mathcal{A}$ is orderless we use property (U.$1$). The
$a_{i}$ vertices are the singleton vertices in the bottom row of $\mathcal{A}$
and the formula $\alpha(x,y)$ is defined as

“$x$ and $y$ are at distance at most $h-1$ in the flip $G^{\prime}$ of $G$”.

If $\mathcal{A}$ is ordered, we use (O.$5$). There is a formula $\beta(x,y)$
that defines $b(v)$ for each $v\in A[i,*]$:

“$x$ is a $b$-vertex and contained in the $r$-ball around $y$ in the flip $H$
of $G$”.

Building on $\beta$, there is a formula $\gamma(x,y)$ which, given $v\in
A[j,*]$, defines $\\{c_{i}:R(i,j),i\in I\\}$:

“$x$ is a $c$-vertex and adjacent to $b(y)$ in $G$”.

As $R\in\\{\leqslant,\geqslant\\}$, we can now define a preorder $\prec$ on
the vertices of the bottom row $A[*,1]$ which respects the column order by
comparing their $\gamma$-neighborhoods:

$x\prec y:=\exists z:\gamma(z,x)\wedge\neg\gamma(z,y)\qquad\text{or}\qquad
x\prec y:=\exists z:\neg\gamma(z,x)\wedge\gamma(z,y)$

depending on the choice of $R$. We choose an arbitrary vertex $a_{i}$ of each
cell $A[i,1]$ of the bottom row. Using the preorder, we can write a formula
$\alpha_{1}(x,y)$ that defines $A[i,1]$ from $a_{i}$ as its equivalence class
in the preorder. For $1<r\leqslant h$, we can now inductively write a formula
$\alpha_{r}(x,y)$ that defines $A[i,{\leqslant}r]$ from $a_{i}$ as all the
vertices that are already in $A[i,{<}r]$, or adjacent to $A[i,{<}r]$ but not
to $A[i-1,{<}r]$ in $G^{\prime}$. Here we again use the preorder to define
$A[i-1,{<}r]$ from $a_{i}$. The correctness for vertices inside $\mathcal{A}$
follows from the properties (O.$2$) and (O.$4$)(O.4$.2$). Vertices from
outside $\mathcal{A}$ can be marked in the coloring and ignored. Setting
$\alpha:=\alpha_{h}$ finishes the proof sketch. ∎

######  Definition 5.5 (Subgrids and subinsulators).

Let $A$ be a grid indexed by a sequence $J$ and of height $h$ in a graph $G$.
For every subsequence $I\subseteq J$ of length at least two we define the
_subgrid_ $A|_{I}$ as the grid indexed by $\mathrm{tail}(I)$ and of height
$h$, containing the following cells. For all $i\in\mathrm{tail}(I)$ and
$r\in[h]$, depending on whether $A$ is _orderless_ or _ordered_ , we
respectively set

$A|_{I}[i,r]:=A[i,r]\quad\text{or}\quad A|_{I}[i,r]:=\bigcup\\{A[m,r]:m\in
I\text{ and }\mathrm{pred}_{I}(i)<m\leqslant i\\}.$

$A|_{I}$ is ordered (orderless) if and only if $A$ is ordered (orderless). See
Figure 9 for a depiction. For every insulator $(A|_{I},\mathcal{K},F,R)$
indexed by $J$, we moreover define the _subinsulator_
$\mathcal{A}|_{I}:=(A|_{I},\mathcal{K},F,R)$. The upcoming Lemma 5.9 will
prove the validity of this definition.

Figure 9: On the left/right: a subgrid of an orderless/ordered grid. The
original grid $A$ is depicted in gray. The dots at the bottom represent the
sequence $J$ indexing $A$. The subsequence $I\subseteq J$ is marked with
circles. The subgrid $A|_{I}$ is overlaid in red. It is indexed by
$\mathrm{tail}(I)$.

For an ordered insulator $\mathcal{A}$, in the definition of a subinsulator
$\mathcal{A}|_{I}$, it is necessary that the indexing sequence
$\mathrm{tail}(I)$ of $\mathcal{A}|_{I}$ excludes the first element of $I$:
each $i\in I$ represents the interval $(\mathrm{pred}_{I}(i),i]$ which is
undefined for the first element of $I$. In orderless insulators this problem
does not arise, but we choose to also exclude the first element of $I$ to
allow for uniform proofs which do not distinguish between the two. The
following observation about subgrids is crucial to their definition and will
later be used to build well-behaved subgrids using Ramsey-arguments.

######  Lemma 5.6.

Let $A$ be a grid indexed by $J$ and of height $h$ in a graph $G$. For every
subsequence $I\subseteq J$ of length at least two, in the subgrid $A|_{I}$,
the content of the column $A|_{I}[i,*]$ depends only on $A$, $i$ and
$\mathrm{pred}_{I}(i)$, instead of the whole sequence $I$. More precisely,
there exists a function $M_{A}:J\times J\rightarrow 2^{V(G)}$ such that for
every $I\subseteq J$ and $i\in\mathrm{tail}(I)$ we have

$A|_{I}[i,*]=M_{A}(\mathrm{pred}_{I}(i),i).$

###### Proof.

We define the function $\mu_{A}:J\times J\times[h]\rightarrow 2^{V(G)}$ as
follows. For all $i<j\in J$ and every $r\in[h]$, depending on whether $A$ is
_orderless_ or _ordered_ , we respectively set

$\mu_{A}(i,j,r):=A[j,r]\quad\text{or}\quad\mu_{A}(i,j,r):=\bigcup\\{A[m,r]:m\in
I\text{ and }i<m\leqslant j\\}.$

We can now define for all $i<j\in J$

$M_{A}(i,j):=\bigcup_{r\in[h]}\mu_{A}(i,j,r).\qed$

######  Observation 5.7 (Transitivity).

Let $A$ be a grid indexed by $I_{0}$, $I_{1}$ be a subsequence of $I_{0}$, and
$I_{2}$ be a subsequence of $\mathrm{tail}(I_{1})$. If $B=A|_{I_{1}}$ and
$C=B|_{I_{2}}$ then $C=A|_{I_{2}}$.

######  Observation 5.8 (Monotonicity and Coverability).

Let $A$ be a grid indexed by $J$ of height $h$ and $I$ be a subsequence of
$J$. For all $i\in\mathrm{tail}(I)$ and $r\in[h]$ we have

$A[i,r]~{}\subseteq~{}A|_{I}[i,r]~{}\subseteq~{}\bigcup\\{A[m,r]:m\in I\text{
and }\mathrm{pred}_{I}(i)<m\leqslant i\\}.$

We finally show that taking a subinsulator preserves its good properties
without increasing its cost.

######  Lemma 5.9.

Let $\mathcal{A}=(A,\mathcal{K},F,R)$ be an insulator indexed by $J$ on a
graph $G$. For every subsequence $I\subseteq J$ we have that
$\mathcal{A}|_{I}:=(A|_{I},\mathcal{K},F,R)$ is also an insulator on $G$.

###### Proof.

Up to renaming, we assume $J=(1,\ldots,n)$. Let $B:={A}|_{I}$ and
$G^{\prime}:=G\oplus_{\mathcal{K}}F$. In the orderless case, as the graph
$G^{\prime}$ remains the same and $B$ is obtained from $A$ by just dropping
columns, it is easy to see that (U.$1$) still holds. It remains to check the
ordered case.

  * •

To prove (O.$1$) and (O.$4$), we observe that for every $i\in I$ and $r\in[h]$

$B[*,r]\subseteq A[*,r]\quad\text{and}\quad B[<i,r]\subseteq
A[<i,r]\quad\text{and}\quad B[>i,r]\subseteq A[>i,r].$

Property (O.$1$) follows directly. To prove, for example, (O.$4$)(O.4$.4$),
assume $u\in B[i,r]$ and $v\in B[<i-1,\\{r,r+1\\}]$. Then also $u\in
B[>\mathrm{pred}_{I}(i),r]$ and $v\in B[<\mathrm{pred}_{I}(i),\\{r,r+1\\}]$.
As argued above, $u\in A[>\mathrm{pred}_{I}(i),r]$ and $v\in
A[<\mathrm{pred}_{I}(i),\\{r,r+1\\}]$. By property (O.$4$)(O.4$.4$) of
$\mathcal{A}$, we have $G\models
E(u,v)\Leftrightarrow(\mathcal{K}(v),\mathcal{K}(u))\in R$, as desired. The
remaining statements of (O.$4$) follow similarly.

  * •

To prove (O.$2$), let $u\in B[i,r]$ for $r>1$ and let us show that $u$ has a
neighbor in $B[i,r-1]$ in $G$. By construction, we have $u\in A[i^{\prime},r]$
for some $\mathrm{pred}_{I}(i)<i^{\prime}\leqslant i$. By (O.$2$) of
$\mathcal{A}$, $u$ has a neighbor $v$ in $A[i^{\prime},r-1]$ in $G^{\prime}$.
Again by construction, $A[i^{\prime},r-1]\subseteq B[i,r-1]$, so also $v\in
B[i,r-1]$.

  * •

For (O.$3$) to hold we must check, for every $u\notin B$ and
$X\in\mathcal{K}$, that $u$ is homogeneous to $X_{B}:=X\cap\mathrm{int}(B)$ in
$G$. As $G^{\prime}$ is a $\mathcal{K}$-flip of $G$, we can check the property
in $G^{\prime}$ instead. If $u\notin A$ this holds as
$X_{B}\subseteq\mathrm{int}(A)$ and (O.$3$) was already true in $\mathcal{A}$.

Assume now $u\in A[i,r]\setminus B$ for some $i\in J$ and $r\in[h]$. As we
already established (O.$1$), we know that all vertices from $X_{B}$ are in the
same row $B[*,r^{\prime}]\subseteq A[*,r^{\prime}]$ for some
$r^{\prime}\in[h]$. If $|r-r^{\prime}|>1$ then $u$ and $X_{B}$ are non-
adjacent in $G^{\prime}$ as $\mathcal{A}$ satisfies (O.$4$). Now assume
$|r-r^{\prime}|\leqslant 1$. Let $i_{0},i_{1},\ldots,i_{n}$ be the continuous
subsequence of $J$ where $i_{0}$ and $i_{n}$ are the first and last elements
of $I$. By construction, we have

$B[*,*]=A[\\{i_{1},\ldots,i_{n}\\},*]\quad\text{ and
}\quad\mathrm{int}(B)=A[\\{i_{2},\ldots,i_{n-1}\\},{<}h].$

Since $u\notin B$ we have $i<i_{1}$ or $i_{n}<i$. Assume $i<i_{1}$. Then we
have $X_{B}\subseteq A[{\leqslant}i_{1},r^{\prime}]\subseteq
A[{>}i,r^{\prime}]$, and we can again use (O.$4$) of $\mathcal{A}$. Now if
$r^{\prime}=r+1$ then $u$ is non-adjacent to $X_{B}$ in $G^{\prime}$. If
$r^{\prime}\in\\{r,r-1\\}$ then $u$ is adjacent to all of $X_{B}$ if
$(\mathcal{K}(u),X)\in R$ and non-adjacent to all of $X_{B}$ otherwise. In
each case $u$ is homogeneous to $X_{B}$. The case where $i_{n}<j$ follows by a
symmetric argument.

  * •

The property (O.$5$) of $\mathcal{A}$ is witnessed by

    * –

a symbol ${\sim}\in\\{\leqslant,\geqslant\\}$,

    * –

a $k$-flip $H$, and

    * –

vertices $\\{b(v)\in V(G):v\in A[*,1]\\}$ and $\\{c_{i}\in V(G):i\in J\\}$.

To witness (O.$5$) of $\mathcal{B}$, we use $\sim$, $H$, $\\{b(v)\in V(G):v\in
B[*,1]\\}$, and

    * –

$\\{c_{i^{\prime}}:i^{\prime}=\mathrm{succ}_{J}(\mathrm{pred}_{I}(i)),i\in\mathrm{tail}(I)\\}$
if $(\sim)=(\leqslant)$, or

    * –

$\\{c_{i}:i\in\mathrm{tail}(I)\\}$ if $(\sim)=(\geqslant)$. ∎

###  6 Prepatterns

Throughout the following sections, we will either make progress constructing
large insulators, or will obtain the following kind of preliminary patterns,
which are then processed further in Part II.

######  Definition 6.1.

Let $\mathcal{A}$ be an insulator indexed by a sequence $K$ with grid $A$ in a
graph $G$. Say that $G$ contains a _bi-prepattern_ of order $t$ on
$\mathcal{A}$ if there exist

  * •

index sequences $I,J\subseteq K$ of size $t$ and with $|I|=|J|=t$,

  * •

vertices $c_{i,j}\in V(G)$ for all $i\in I,j\in J$,

  * •

quantifier-free formulas $\alpha_{1}(x;y,s_{1})$ and $\alpha_{2}(x;y,s_{2})$
with parameters $s_{1},s_{2}\in V(G)$,

  * •

symbols $\sim_{1},\sim_{2}\in\\{=,\neq\\}$,

such that for all $i\in I,j\in J$,

$\displaystyle i$ $\displaystyle=\min\big{\\{}i^{\prime}\in
I:\alpha_{1}(A[i^{\prime},*];c_{i,j},s_{1})\sim_{1}\emptyset\big{\\}},$
$\displaystyle j$ $\displaystyle=\min\big{\\{}j^{\prime}\in
J:\alpha_{2}(A[j^{\prime},*];c_{i,j},s_{2})\sim_{2}\emptyset\big{\\}}.$

Let us give some intuition for the above definition. The bi-prepattern
consists of two sequences of columns indexed by $I$ and $J$. For each pair of
columns $(i,j)\in I\times J$, there exists a private vertex $c_{i,j}$ pairing
them up in the following sense. Column $i$ is the first column in $I$, in
which

  * •

$c_{i,j}$ has no $\alpha_{1}$-neighbor (if ${\sim_{1}}$ is $=$), or

  * •

$c_{i,j}$ has an $\alpha_{1}$-neighbor (if ${\sim_{1}}$ is $\neq$).

Similarly, $j$ is the first column in $J$ in which has an
$\alpha_{2}$-neighbor (resp. no $\alpha_{2}$-neighbor). Figure 10 (_left_)
illustrates this column pairing.

Figure 10: Schematic depiction of a bi-prepattern (left) and mono-prepattern
(right).

This pairing aspect will be used later to argue that large bi-prepatterns
witness monadic independence (or equivalently: they are obstructions for
monadic dependence). By Lemma 5.4, each column of the insulator can be first-
order defined from a single representative vertex. Bi-prepatterns therefore
logically resemble $1$-subdivided bicliques, where the column representatives
are the principle vertices and the vertices $c_{i,j}$ form the subdivision
vertices. Subdivided bicliques of unbounded size are witnesses for monadic
independence: they encode arbitrary bipartite graphs by coloring the
subdivision vertices. Therefore, bi-prepatterns may be thought of as
obstructions to monadic dependence. Moreover, by the strong structure
properties of insulators and since $\alpha_{1}$ and $\alpha_{2}$ are
quantifier-free, we can use bi-prepatterns to later extract from them our
concrete forbidden induced subgraph characterization.

In addition to the bi-prepatterns, our analysis produces a second kind of
obstruction called a _mono-prepattern_.

######  Definition 6.2.

Let $\mathcal{A}$ be an insulator indexed by a sequence $K$ with grid $A$ in a
graph $G$. Say that $G$ contains a _mono-prepattern_ of order $t$ on
$\mathcal{A}$ if there exist

  * •

index sequences $I,J$ with $I\subseteq K$ and $|I|=|J|=t$,

  * •

vertices $c_{j}\in V(G)$ for all $j\in J$,

  * •

vertices $b_{i,j}\in A[i,*]$ for all $i\in I,j\in J$,

  * •

a symbol ${\sim}\in\\{=,\neq,\leqslant,<,\geqslant,>\\}$,

such that for all $i\in I$ and $j,j^{\prime}\in J$,

$G\models E(c_{j},b_{i,j^{\prime}})\Leftrightarrow j\sim j^{\prime}.$

Similarly as in a bi-prepattern, in a mono-prepattern the $c_{j}$ vertices can
be used to pair up columns $(i,j)\in I\times I$. While the bi-prepattern
logically resembles a subdivided biclique (we pair elements from two sequences
$I$ and $J$), the mono-prepattern corresponds to a subdivided clique (we pair
elements from the same sequence $I$). Figure 10 (_right_) illustrates mono-
prepatterns.

######  Definition 6.3.

$G$ contains a _prepattern_ of order $t$ on an insulator $\mathcal{A}$ if it
either contains a bi-prepattern of order $t$ on $\mathcal{A}$ or a mono-
prepattern of order $t$ on $\mathcal{A}$.

######  Definition 6.4.

A class of graphs $\mathcal{C}$ is _prepattern-free_ , if for every
$k,r\in\mathrm{\mathbb{N}}$, there exists $t\in\mathrm{\mathbb{N}}$ such that
every graph $G\in\mathcal{C}$ does not contain prepatterns of order $t$ on
insulators of cost at most $k$ and height at most $r$ in $G$.

We later show in Theorem 13.1 that these obstructions are exhaustive:
prepattern-freeness is equivalent to monadic dependence. In the following
sections, we start by deriving structural properties of prepattern-free
classes.

###  7 The Insulation Property

Towards proving that prepattern-free classes are flip-breakable, we first show
that they possess a more fine-grained structure property which we call the
_insulation property_.

######  Definition 7.1.

Let $\mathcal{A}$ be an insulator with grid $A$ indexed by a sequence $I$ in a
graph $G$ and let $W\subseteq V(G)$. We say that $\mathcal{A}$ _insulates_ $W$
if there is a bijection $f:W\rightarrow I$, such that for all $v\in W$

$v\in A[f(v),1].$

A set $W$ is _$(r,k)$ -insulated_ in $G$ if there is an insulator
$\mathcal{A}$ of height $r$ and cost $k$ that insulates $W$.

######  Definition 7.2.

A class of graphs $\mathcal{C}$ has the _insulation property_ , if for every
radius $r\in\mathrm{\mathbb{N}}$ there exist a function
$N_{r}:\mathrm{\mathbb{N}}\rightarrow\mathrm{\mathbb{N}}$ and a constant
$k_{r}\in\mathrm{\mathbb{N}}$ such that for every $m\in\mathrm{\mathbb{N}}$,
$G\in\mathcal{C}$, $W\subseteq V(G)$ with $|W|\geqslant N_{r}(m)$, there is a
subset $W_{\star}\subseteq W$ of size at least $m$ that is
$(r,k_{r})$-insulated in $G$.

More briefly: $\mathcal{C}$ has the insulation property if for every
$r\in\mathrm{\mathbb{N}}$, $G\in\mathcal{C}$ and $W\subseteq V(G)$ there is a
subset $W_{\star}\subseteq W$ of size $U_{\mathcal{C},r}(|W|)$ that is
$(r,\mathrm{const}(\mathcal{C},r))$-insulated in $G$.

The goal of this section is to prove the following.

######  Proposition 7.3.

Every prepattern-free graph class has the insulation property.

We first notice that insulation for radius $r=1$ is trivial.

######  Lemma 7.4.

Fix a graph $G$. Every set $W\subseteq V(G)$ is $(1,1)$-insulated in $G$.

###### Proof.

Fix any enumeration $(a_{1},\ldots,a_{n})$ of $W$. Let $A$ be the orderless
grid indexed by the sequence $I:=(1,\ldots,n)$ and of height $1$ such that
$A[i,1]:=\\{a_{i}\\}$ for all $i\in I$. Now
$\mathcal{A}:=(A,\\{V(G)\\},\varnothing,\varnothing)$ is an orderless
insulator with cost and height $1$ that insulates $W$. ∎

In order to insulate sets with higher radii, we will grow insulators in
height.

######  Definition 7.5 (Row-Extensions).

Let $A$ be a grid indexed by $I$ and of height $h$. We say a grid $B$ is a
_row-extension_ of $A$, if it satisfies the following properties.

  * •

$B$ is indexed by $I$ and has height $h+1$.

  * •

For all $i\in I$ and $j\in[h]$ we have $B[i,j]=A[i,j]$.

  * •

Either $A$ and $B$ are both _orderless_ or both _ordered_.

Similarly, we say an insulator $\mathcal{B}$ is a _row-extension_ of an
insulator $\mathcal{A}$, if the grid of $\mathcal{B}$ is a row-extension of
the grid of $\mathcal{A}$.

Depending on whether the insulator at hand is orderless or ordered, we will
create row-extensions using one of the following two insulator growing lemmas.
To keep the presentation streamlined, the (quite technical) proofs of the two
lemmas are deferred to Section 10.

######  Lemma 7.6 (Orderless Insulator Growing).

Fix $k,t\in\mathrm{\mathbb{N}}$. For every graph $G$ and orderless insulator
$\mathcal{A}$ indexed by $J$ of cost $k$ in $G$, we can compute a subsequence
$I\subseteq J$ of length $U_{t}(|J|)$ such that either

  * •

$G$ contains a prepattern of order $t$ on $\mathcal{A}|_{I}$

  * •

$\mathcal{A}|_{I}$ is orderable, or

  * •

there exists a row-extension of $\mathcal{A}|_{I}$ of cost
$\mathrm{const}(k,t)$ in $G$.

Moreover, there is an algorithm that, given $G$ and $\mathcal{A}$, computes
the sequence $I$ and one of the three outcomes (a prepattern, a witnesses for
$\mathcal{A}|_{I}$ being orderable, or a row-extension) in time
$O_{k,t}(|V(G)|^{2})$.

The definition of an _orderable_ insulator will be given shortly after the
following lemma.

######  Lemma 7.7 (Ordered Insulator Growing).

Fix $k,t\in\mathrm{\mathbb{N}}$. For every graph $G$ and ordered insulator
$\mathcal{A}$ with cost $k$, indexed by $J$ in $G$, we can compute a
subsequence $I\subseteq J$ of length $U_{t}(|J|)$ such that either

  * •

$G$ contains a prepattern of order $t$ on $\mathcal{A}|_{I}$, or

  * •

$G$ contains a row-extension of $\mathcal{A}|_{I}$ with cost
$\mathrm{const}(k,t)$.

Moreover, there is an algorithm that, given $G$ and $\mathcal{A}$, computes
the sequence $I$ and one of the two outcomes (a prepattern or a row-extension)
in time $O_{k,t}(|V(G)|^{2})$.

Both insulator growing lemmas follow the same scheme. Given an insulator we
find a large subinsulator that either witnesses a lot of non-structure (in
form of a prepattern), or improves the structural guarantees of the original
insulator (in form of a row-extension). In the orderless case a third outcome
may appear: the subinsulator may be _orderable_. Orderable insulators are
orderless insulators which can be converted into ordered ones, as made precise
by the following definition and lemma.

######  Definition 7.8 (Orderable Insulators).

Let $\mathcal{A}$ be an orderless insulator with grid $A$ indexed by $I$ in a
graph $G$. We say that $\mathcal{A}$ is _orderable_ if there exist vertices
$\\{b_{i}\in A[i,*]:i\in I\\}$ and $\\{c_{i}\in V(G):i\in I\\}$ and a symbol
${\sim}\in\\{\leqslant,{\geqslant}\\}$ such that for all $i,j\in I$

$G\models E(c_{i},b_{j})\quad\text{if and only if}\quad i\sim j.$

######  Lemma 7.9.

Let $\mathcal{A}$ be an orderless insulator of cost $k$ and height $h$ in a
graph $G$ that insulates a set $W\subseteq V(G)$. If $\mathcal{A}$ is
orderable, then there exists an ordered insulator $\mathcal{B}$ of cost
$k\cdot h$ and height $h$ that also insulates $W$.

Moreover, there is an algorithm that, given $G$ and $\mathcal{A}$, computes
$\mathcal{B}$ in time $O_{k,h}(|V(G)|)$.

###### Proof.

Let $\mathcal{A}=(A,\mathcal{K},F,F)$ be as in the statement. Let $B$ be the
grid obtained by changing the tag of the grid $A$ from _orderless_ to
_ordered_. Towards ensuring (O.$1$), let $\mathcal{K}_{\star}$ be the size
$k\cdot h$ coloring obtained by taking the common refinement of the
$k$-coloring $\mathcal{K}$ and an $h$-coloring that assigns vertices from
different rows in $A$ different colors. Let $F_{\star}$ be the corresponding
refinement of $F$ such that
$G\oplus_{\mathcal{K}}F=G\oplus_{\mathcal{K}_{\star}}F_{\star}$. We check that
$\mathcal{B}:=(B,\mathcal{K}_{\star},F_{\star},F_{\star})$ is the desired
ordered insulator. The insulator property (O.$1$) holds by construction. By
5.3, (O.$2$), (O.$3$), and (O.$4$) carry over from $\mathcal{A}$. Finally,
(U.$1$) ensures for the $k$-flip $H:=G\oplus_{\mathcal{K}}F$ and $v\in A[i,1]$
that $N_{h-1}^{H}[v]=A[i,*]$. As $\mathcal{A}$ moreover is orderable (cf.
Definition 7.8), property (O.$5$) follows. The bound on the running time is
trivial. ∎

As we know how to grow orderless insulators, turn orderless, orderable
insulators into ordered ones, and grow ordered insulators, we can now grow
arbitrarily high insulators. This yields a proof of Proposition 7.3, which we
restate below with an added algorithmic conclusion.

######  Proposition 7.10.

Every prepattern-free graph class $\mathcal{C}$ has the insulation property.

Moreover, there is an algorithm that, given a radius $r$, a graph
$G\in\mathcal{C}$ and a set $W$, computes the subset $W_{\star}\subseteq W$
and a witnessing insulator in time $O_{\mathcal{C},r}(|V(G)|^{2})$.

###### Proof.

Fix a prepattern-free class $\mathcal{C}$ and $r\geqslant 1$. We prove that
for every $G\in\mathcal{C}$ and $W\subseteq V(G)$ there is a subset
$W_{r}\subseteq W$ of size $U_{\mathcal{C},r}(|W|)$ that is
$(r,k_{r})$-insulated in $G$, for some
$k_{r}\leqslant\mathrm{const}(\mathcal{C},r)$. This statement is proved by
induction on $r\geqslant 1$. The base case of $r=1$ follows immediately from
Lemma 7.4.

In the inductive step, assume the statement holds for some $r\geqslant 1$; we
prove it for $r+1$. Let $k_{r}\leqslant\mathrm{const}(\mathcal{C},r)$ be the
value obtained by inductive assumption. As $\mathcal{C}$ is prepattern-free,
there is some number $t=\mathrm{const}(\mathcal{C},r)$ such that no graph
$G\in\mathcal{C}$ contains a pattern of order $t$ on insulators of cost at
most $k_{r}\cdot r$ and height at most $r$ in $G$.

Let $G\in\mathcal{C}$ and $W\subseteq V(G)$. By the inductive assumption,
there is a subset $W_{r}\subseteq W$ of size $U_{\mathcal{C},r}(|W|)$ and an
insulator $\mathcal{A}_{r}$ of height $r$ and cost
$\mathrm{const}(\mathcal{C},r)$ which insulates $W_{r}$. Let $J$ denote the
indexing sequence of $\mathcal{A}_{r}$. We prove that there is a subset
$W_{r+1}\subseteq W_{r}$ of size $U_{\mathcal{C},r}(|W_{r}|)\geqslant
U_{\mathcal{C},r}(|W|)$ and an insulator $\mathcal{A}_{r+1}$ of height $r+1$
and cost $\mathrm{const}(\mathcal{C},r)$ which insulates $W_{r+1}$. We
consider two cases, depending on whether $\mathcal{A}_{r}$ is orderless or
ordered.

Assume first that $\mathcal{A}_{r}$ is orderless. We apply Lemma 7.6 to
$\mathcal{A}_{r}$. This yields a sequence $I\subseteq J$ of length
$U_{t}(|J|)$ such that one of the following three cases applies.

  1. 1.

$G$ contains a prepattern of order $t$ on $\mathcal{A}_{r}|_{I}$.

  2. 2.

$G$ contains a row-extension $\mathcal{A}_{r}|_{I}$ with cost
$\mathrm{const}(k_{r},t)\leqslant\mathrm{const}(\mathcal{C},r)$.

  3. 3.

$\mathcal{A}_{r}|_{I}$ is orderable.

We set $W^{\prime}:=A[*,1]$ where $A$ is the grid of $\mathcal{A}_{r}|_{I}$.
By the definition of an orderless subgrid we have $W^{\prime}\subseteq
W_{r}\subseteq W$ and

$|W^{\prime}|=|\mathrm{tail}(I)|=|I|-1\geqslant U_{t}(|J|).$

As $\mathcal{A}_{r}$ is of height $r$ and cost $k_{r}$, the same holds for
$\mathcal{A}_{r}|_{I}$. By our choice of $t$, the first case cannot apply. In
the second case, the row extension of $\mathcal{A}_{r}|_{I}$ witnesses that
$W^{\prime}$ is $(r+1,\mathrm{const}(\mathcal{C},r))$-insulated, and we
conclude by setting $W_{r+1}:=W^{\prime}$. It remains to handle the third
case. We apply Lemma 7.9 to the orderable insulator $\mathcal{A}_{r}|_{I}$,
yielding an ordered insulator $\mathcal{B}$ of cost $k_{r}\cdot r$ and height
$r$ that also insulates $W^{\prime}$. Up to renaming, we can assume that
$\mathcal{B}$ is indexed by $\mathrm{tail}(I)$, the same sequence that also
indexes $\mathcal{A}_{r}|_{I}$. We apply Lemma 7.7 to $\mathcal{B}$ with
$k:=k_{r}\cdot r$ and $t$. This yields a sequence $K\subseteq\mathrm{tail}(I)$
with $|K|=U_{t}(|J|)$ such that one of the following two cases applies.

  1. 1.

$G$ contains a prepattern of order $t$ on $\mathcal{B}|_{K}$.

  2. 2.

$G$ contains a row-extension of $\mathcal{B}|_{K}$ with cost
$\mathrm{const}(k,t)\leqslant\mathrm{const}(\mathcal{C},r)$.

By our choice of $t$, the first case cannot apply. In the second case, by
definition of an ordered subgrid, there exists a set $W_{r+1}\subseteq
W^{\prime}\subseteq W$ which is insulated by a row extension of
$\mathcal{B}|_{K}$ and has size at least

$|W_{r+1}|=|\mathrm{tail}(K)|=|K|-1\geqslant U_{t}(|J|).$

$W_{r+1}$ is the desired $(r+1,k)$-insulated set. This concludes the case
where $\mathcal{A}_{r}$ is orderless. If $\mathcal{A}_{r}$ is ordered we can
directly apply Lemma 7.7, which just improves the bounds. This completes the
inductive proof.

The induction can be easily turned into an algorithm. The trivial insulator
from Lemma 7.4 can be computed in time $O(|V(G)|)$. The running time of the
inductive step follows from the running times of Lemma 7.6, Lemma 7.9, and
Lemma 7.7. ∎

###  8 Flip-Breakability

In this section we show the following implications:

$\text{insulation property}\quad\Rightarrow\quad\text{flip-
breakable}\quad\Rightarrow\quad\text{monadically dependent}$

For convenience, we restate the definition of flip-breakability.

See 1.2

In short, $\mathcal{C}$ is flip-breakable if for every
$r\in\mathrm{\mathbb{N}}$, graph $G\in\mathcal{C}$ and $W\subseteq V(G)$,
there exist subsets $A,B\subseteq W$ with $|A|,|B|\geqslant
U_{\mathcal{C},r}(|W|)$ and a $\mathrm{const}(\mathcal{C},r)$-flip $H$ of $G$
with $\textnormal{dist}_{H}(A,B)>r$.

####  8.1 Insulation Property Implies Flip-Breakability

In this section we prove the following.

######  Proposition 8.1.

Every graph class $\mathcal{C}$ with the insulation property is flip-
breakable.

Moreover, if $\mathcal{C}$ is also prepattern-free, then there is an algorithm
that, given a radius $r$, graph $G$, and set $W$, computes in time
$O_{\mathcal{C},r}(|V(G)|^{2})$ subsets $A,B\subseteq W$, partition
$\mathcal{K}_{\star}$, and relation
$F_{\star}\subseteq\mathcal{K}_{\star}^{2}$ witnessing flip-breakability.
(This means $|A|,|B|\geqslant U_{\mathcal{C},r}(|W|)$,
$|\mathcal{K}_{\star}|\leqslant\mathrm{const}(\mathcal{C},r)$, and
$\textnormal{dist}_{H}(A,B)>r$ in the flip $H$ defined by
$\mathcal{K}_{\star}$ and $F_{\star}$.)

Let $W$ be a set of vertices in a graph $G$. We call $W$ _$(r,k)$ -flip-
breakable_, if there exist two disjoint sets $A,B\subseteq W$, each of size at
least $\frac{1}{3}|W|$, and a $k$-flip $H$ of $G$, such that

$N^{H}_{r}(A)\cap N^{H}_{r}(B)=\varnothing.$

Proposition 8.1 will be implied by the following.

######  Lemma 8.2.

Let $W$ be a $(2r+1,k)$-insulated set of at least $18r$ vertices in a graph
$G$. Then $W$ is $(r,2^{48r^{2}k})$-flip-breakable in $G$.

Moreover, there is an algorithm that, given a radius $r$, graph $G$, set $W$,
and an insulator witnessing that $W$ is $(2r+1,k)$-insulated, computes in time
$O_{r,k}(|V(G)|)$ the subsets $A,B\subseteq W$, partition
$\mathcal{K}_{\star}$, and relation
$F_{\star}\subseteq\mathcal{K}_{\star}^{2}$ that witness the
$(r,2^{48r^{2}k})$-flip-breakability of $W$.

###### Proof.

Let $\mathcal{A}=(A,\mathcal{K},F,R)$ be the insulator of cost $k$ and height
$2r+1$ that insulates $W$. Since we will only be using the insulator
properties (O.$3$) and (O.$4$) and by 5.3, we do not have to distinguish
whether $\mathcal{A}$ is orderless or ordered. Up to renaming, we can assume
that $A$ is indexed by a sequence $I=(1,\ldots,n)$ for some
$n\in\mathrm{\mathbb{N}}$. Let $l_{1},l_{2},r_{1},r_{2}\in I$ be the indices
such that $(l_{1},l_{1}+1,\ldots,l_{2})$ and $(r_{1},r_{1}+1,\ldots,r_{2})$
are the sequences containing the first and last $2r$ elements of $I$
respectively. Since $\mathcal{A}$ insulates $W$, we can choose indices
$m_{1}>\ell_{2}$ and $m_{2}<r_{1}$ such that $(m_{1},m_{1}+1,\ldots,m_{2})$
contains $2r$ elements and there are two disjoint sets $W_{1}:=W\cap M_{1}\cap
A[*,1]$ and $W_{2}:=W\cap M_{2}\cap A[*,1]$, where

$M_{1}:=\bigcup_{l_{2}<i<m_{1}}A[i,*]\quad\text{and}\quad
M_{2}:=\bigcup_{m_{2}<i<r_{1}}A[i,*],$

such that $W_{1}$ and $W_{2}$ each contain at least
$\frac{1}{2}(|W|-6r)\geqslant\frac{1}{3}|W|$ vertices. The sets $W_{1}$ and
$W_{2}$ will play the role of the sets $A$ and $B$ in the flip-breakability
statement. We define a new grid $B$ of height $h$ indexed by
$J:=(1,\ldots,3\cdot 2r+2)$ on the same vertex set as $A$. The rows of $B$ are
the same as the rows of $A$. The columns of $B$ are in order

$\underbrace{A[l_{1},*],\ \ldots,\ A[l_{2},*]}_{2r\text{ columns}},\ M_{1},\
\underbrace{A[m_{1},*],\ \ldots,\ A[m_{2},*]}_{2r\text{ columns}},\ M_{2},\
\underbrace{A[r_{1},*],\ \ldots,\ A[r_{2},*]}_{2r\text{ columns}}.$

See Figure 11 for a visualization. We observe that $B$ coarsens the columns of
$A$ in the following sense.

######  Observation 8.3.

Let $u\in B[j,t]$ and $v\in B[j^{\prime},t^{\prime}]$ such that $j<j^{\prime}$
for some $j,j^{\prime}\in J$ and $t,t^{\prime}\in[h]$. The also $u\in A[i,t]$
and $v\in A[i^{\prime},t^{\prime}]$ for some $i<i^{\prime}\in I$.

Additionally, the construction ensures that

  * •

$B$ has $(3\cdot 2r+2)\cdot(2r+1)\leqslant 24r^{2}$ cells,

  * •

$W_{1}\subseteq B[2r+1,1]$ and $W_{2}\subseteq B[4r+2,1]$, and

  * •

$\mathrm{int}(A)=\mathrm{int}(B)$.

Figure 11: An example of a coarsening for radius $r=2$. The coarsening $B$ (in
bold red) overlays the grid $A$ (in gray). The sequence $W$ is located in the
bottom row. The two subsequences $W_{1}$ and $W_{2}$ are marked with circles
and squares, respectively.

We build $\mathcal{K}_{\star}$ as a refinement of $\mathcal{K}$ by encoding
into the color of every vertex $v\in V(G)$ for every color $X\in\mathcal{K}$
and for every cell $B[i,j]$ of $B$ the information

  1. (C.$1$)

whether $v\in X$,

  2. (C.$2$)

whether $v\in B[i,j]$,

  3. (C.$3$)

whether $v$ is adjacent in $G$ to a vertex from $X\cap\mathrm{int}(B)$.

$\mathcal{K}_{\star}$ has at most $2^{k\cdot 24r^{2}\cdot 2}$ colors. By
(C.$1$), we can define for every $X\in\mathcal{K}_{\star}$ a color
$\mathcal{K}(X)\in\mathcal{K}$ such that for all $v\in X$ we have
$v\in\mathcal{K}(X)$. We define $F_{\star}\subseteq\mathcal{K}^{2}$ via the
following four rules.

  1. (F.$1$)

If $X\subseteq B[j,t]$ and $Y\subseteq B[j^{\prime},t^{\prime}]$ and
$j<j^{\prime}$ and $t^{\prime}\in\\{t,t-1\\}$, then

$(X,Y)\in
F_{\star}\Leftrightarrow\big{(}\mathcal{K}(X),\mathcal{K}(Y)\big{)}\in R.$

  2. (F.$2$)

If $X\subseteq B[j,t]$ and $Y\subseteq B[j^{\prime},t^{\prime}]$ and
$j>j^{\prime}$ and $t^{\prime}\in\\{t,t+1\\}$, then

$(X,Y)\in
F_{\star}\Leftrightarrow\big{(}\mathcal{K}(Y),\mathcal{K}(X)\big{)}\in R.$

  3. (F.$3$)

If $X\not\subseteq B$ and $Y\subseteq\mathrm{int}(B)$, or vice versa, then

$(X,Y)\in F_{\star}\Leftrightarrow\text{there is an edge between $X$ and $Y$
in $G$}.$

  4. (F.$4$)

Otherwise, $(X,Y)\in
F_{\star}\Leftrightarrow\big{(}\mathcal{K}(X),\mathcal{K}(Y)\big{)}\in F$.

By construction, $F_{\star}$ is symmetric and therefore describes a valid
flip. Let $G^{\prime}:=G\oplus_{\mathcal{K}}F$ and
$G_{\star}:=G\oplus_{\mathcal{K}_{\star}}F_{\star}$.

######  Claim 8.4.

Let $u\in\mathrm{int}(B)$ and $v\in B$ be vertices from rows that are not
close in $B$. Then $u$ and $v$ are non-adjacent in $G_{\star}$.

###### Proof.

Let $u$ and $v$ be as in the claim. Then case (F.$4$) applies and $u$ and $v$
are adjacent in $G_{\star}$ if an only if they are adjacent in $G^{\prime}$.
By construction of $B$, we have also $u\in\mathrm{int}(A)$ and $v\in A$ and
$u$ and $v$ are in rows that are not close in $A$. It follows by property
(O.$4$)(O.4$.1$) of $\mathcal{A}$ that $u$ and $v$ are non-adjacent in both
$G^{\prime}$ and $G_{\star}$. ∎

######  Claim 8.5.

Let $u\in\mathrm{int}(B)$ and $v\in B$ be vertices from columns that are not
close in $B$. Then $u$ and $v$ are non-adjacent in $G_{\star}$.

###### Proof.

Let $u\in B[j,t]$ and $v\in B[j^{\prime},t^{\prime}]$ be as in the claim for
some $j,j^{\prime}\in J$ and $t,t^{\prime}\in[h]$. If $u$ and $v$ are in rows
that are not close, then we are done by 8.4. We can therefore assume
$t^{\prime}\in\\{t-1,t,t+1\\}$.

Assume first that $j<j^{\prime}$. Since $B[j,*]$ and $B[j^{\prime},*]$ are not
close, we even have $j+1<j^{\prime}$. If $t^{\prime}=t+1$, then case (F.$4$)
applies and $u$ and $v$ are adjacent in $G_{\star}$ if an only if they are
adjacent in $G^{\prime}$. By 8.3, the adjacency between $u$ and $v$ in
$G^{\prime}$ can be determined using the insulator property (O.$4$)(O.4$.2$)
of $\mathcal{A}$: $u$ and $v$ are non-adjacent as desired. If
$t^{\prime}\in\\{t,t-1\\}$, then by (C.$2$), case (F.$1$) applies and the
following are equivalent. Let $X:=\mathcal{K}_{\star}(u)$ and
$Y:=\mathcal{K}_{\star}(v)$.

  1. 1.

The adjacency between $u$ and $v$ got flipped when going from $G$ to
$G_{\star}$.

  2. 2.

$\big{(}\mathcal{K}(X),\mathcal{K}(Y)\big{)}\in R$. (by (F.$1$))

  3. 3.

$u$ and $v$ are adjacent in $G$. (by 8.3 and (O.$4$)(O.4$.3$))

The equivalence between the first and the last item establishes that $u$ and
$v$ are non-adjacent in $G_{\star}$, as desired.

The proof for $j>j^{\prime}$ works symmetrically. If $t^{\prime}=t-1$, then
case (F.$4$) applies, and we argue using (O.$4$)(O.4$.2$). If
$t^{\prime}\in\\{t,t+1\\}$, then case (F.$2$) applies, and we argue using
(O.$4$)(O.4$.4$). ∎

######  Claim 8.6.

Let $u\in\mathrm{int}(B)$ and $v$ be a vertex not in $B$. Then $u$ and $v$ are
non-adjacent in $G_{\star}$.

###### Proof.

Let $X:=\mathcal{K}_{\star}(u)$ and $Y:=\mathcal{K}_{\star}(v)$ be the colors
of $u$ and $v$ in $\mathcal{K}_{\star}$. By (C.$2$), we have $Y\cap
A=\varnothing$ and $X\subseteq\mathrm{int}(A)$. It follows from property
(O.$3$) of $\mathcal{A}$ that every vertex from $Y$ is homogeneous to $X$ in
$G$. Moreover, by (C.$3$), either every or no vertex in $Y$ has a neighbor in
$X$ in $G$. It follows that the connection between $X$ and $Y$ is homogeneous
in $G$. Also, by (C.$3$), case (F.$3$) applies, and the following are
equivalent.

  1. 1.

The adjacency between $u$ and $v$ got flipped when going from $G$ to
$G_{\star}$.

  2. 2.

There is an edge between $X$ and $Y$ in $G$. (by (F.$3$))

  3. 3.

There is an edge between $u$ and $v$ in $G$. (by homogeneity of $X\ni u$ and
$Y\ni v$ in $G$)

The equivalence between the first and the last item establishes that $u$ and
$v$ are non-adjacent in $G_{\star}$, as desired. ∎

Combining 8.4, 8.5, and 8.6 yields the following crucial observation.

######  Observation 8.7.

In $G_{\star}$, if vertices $u\in\mathrm{int}(B)$ and $v\in V(G)$ are
adjacent, then they are in cells that are close in $B$.

A straightforward induction now yields that the $2r$-neighborhood of every
vertex $u\in W_{1}\subseteq B[2r+1,1]$ in $G_{\star}$ satisfies
$N^{G_{\star}}_{2r}(u)\subseteq B[{\leqslant}4r+1,*]$. In particular, it
contains no vertex from $W_{2}\subseteq B[4r+2,1]$. We therefore have
$N^{G_{\star}}_{r}(W_{1})\cap N^{G_{\star}}_{r}(W_{2})=\varnothing$ as
desired. This finishes the proof of the flip-breakability of $W$. To bound the
running time, note that $W_{1}$, $W_{2}$, $\mathcal{K}_{\star}$, and
$F_{\star}$ can all be computed in time $O_{r,k}(|V(G)|)$. ∎

We can now prove Proposition 8.1.

###### Proof of Proposition 8.1.

The non-algorithmic part of the statement immediately follows from Lemma 8.2.
For the algorithmic part, assume that $\mathcal{C}$ is also prepattern-free.
Given any set $W$, we can compute an insulated subset $W^{\prime}\subseteq W$
and a witnessing insulator $\mathcal{A}$ using Proposition 7.10. Applying the
algorithm given by Lemma 8.2 to $W^{\prime}$ and $\mathcal{A}$ yields the
desired result. ∎

####  8.2 Flip-Breakability Implies Monadic Dependence

We prove the second main implication of the section.

######  Proposition 8.8.

Every flip-breakable class of graphs is monadically dependent.

Let $\varphi(x,y)$ be a formula over the signature of colored graphs, $G^{+}$
be a colored graph, and $W$ be a set of vertices in $G^{+}$. We say that
$\varphi$ _shatters_ $W$ in $G^{+}$, if there exists vertices
$(a_{R})_{R\subseteq W}$ such that for all $b\in P$ and $R\subseteq W$,

$G^{+}\models\varphi(a_{R},b)\Leftrightarrow b\in R.$

Let $G$ be an (uncolored) graph, and $W$ be a set of vertices in $G$. We say
that $\varphi$ _monadically shatters_ $W$ in $G$, if there exists a coloring
$G^{+}$ of $G$ in which $\varphi$ shatters $W$.

######  Fact 8.9 ([4]).

A class of graphs $\mathcal{C}$ is monadically dependent if and only if for
every formula $\varphi(x,y)$ over the signature of colored graphs, there
exists a bound $m$ such that $\varphi$ monadically shatters no set of size $m$
in any graph of $\mathcal{C}$.

Proposition 8.8 will be implied by the following.

######  Lemma 8.10.

Let $\varphi(x,y)$ be a formula and $k\in\mathrm{\mathbb{N}}$. There exist
$r_{\varphi},m_{\varphi,k}\in\mathrm{\mathbb{N}}$, where $r_{\varphi}$ depends
only on $\varphi$, such that no graph $G$ contains a set of at least
$m_{\varphi,k}$ vertices $W$ such that

  * •

$\varphi$ monadically shatters $W$ in $G$, and

  * •

$W$ is $(r_{\varphi},k)$-flip-breakable in $G$.

In order to prove Lemma 8.10, we use the following statement, which is an
immediate consequence of Gaifman’s locality theorem [30]. For an introduction
of the locality theorem see for example [37, Sec. 4.1].

######  Corollary 8.11 (of [30, Main Theorem]).

Let $\varphi(x,y)$ be a formula. Then there are numbers
$r,t\in\mathrm{\mathbb{N}}$, where $r$ depends only on the quantifier-rank of
$\varphi$ and $t$ depends only on the signature and quantifier-rank of
$\varphi$, such that every (colored) graph $G$ can be vertex-colored using $t$
colors in such a way that for any two vertices $u,v\in V(G)$ with distance
greater than $r$ in $G$, $G\models\varphi(u,v)$ depends only on the colors of
$u$ and $v$. We call $r$ the _Gaifman radius_ of $\varphi$.

###### Proof of Lemma 8.10.

We set $r_{\varphi}$ to be the Gaifman radius of $\varphi$. Let $s$ be the
number of colors used by $\varphi$. As stated in Corollary 8.11, let $t$ be
the number of colors needed to determine the truth value of formulas in the
signature of $(s\cdot k)$-colored graphs that have the same quantifier-rank as
$\varphi(x,y)$. Let $m_{\varphi,k}:=3(t+1)$.

Assume now towards a contradiction the existence of an $(r_{\varphi},k)$-flip-
breakable in set $W$ in $G$ of size $m_{\varphi,k}$ such that $\varphi$
monadically shatters $W$ in $G$. Then there exists an $s$-coloring $G^{+}$ of
$G$ in which $\varphi$ shatters $W$. We apply flip-breakability which yields a
$k$-flip $H$ of $G$ together with two disjoint sets $A,B\subseteq W$ each of
size at least $t+1$, such that $N^{H}_{r}(A)\cap N^{H}_{r}(B)=\varnothing$. By
using $k$ colors to encode the flip, we can rewrite $\varphi$ to a formula
$\psi$ with the same quantifier-rank as $\varphi$, such that there exists a
$(s\cdot k)$-coloring $H^{+}$ of $H$ where for all $u,v\in V(G)$,

$G^{+}\models\varphi(u,v)\Leftrightarrow H^{+}\models\psi(u,v).$

In particular, $\psi$ shatters $W$ in $H^{+}$. Since $\psi$ has the same
quantifier-rank as $\varphi$ and is a formula over the signature of $s\cdot
k$-colored graphs, by Corollary 8.11 there exists a coloring of $H^{+}$ with
$t$ colors such that the truth of $\psi(u,v)$ in $H^{+}$ only depends on the
colors of $u$ and $v$ for all vertices $u$ and $v$ with distance greater than
$r$ in $H^{+}$. Recall that $A$ and $B$ each have size $t+1$. By the
pigeonhole principle, there exist two distinct vertices $a_{1},a_{2}\in A$
that are assigned the same color and two distinct vertices $b_{1},b_{2}\in B$
that are assigned the same color. Since $\psi$ shatters $W$ in $H^{+}$, there
exists a vertex $v\in V(G)$ such that

$H^{+}\models\psi(v,a_{1})\wedge\neg\psi(v,a_{2})\wedge\psi(v,b_{1})\wedge\neg\psi(v,b_{2}).$

By Corollary 8.11, $v$ must be contained in $N^{H}_{r}(A)\cap N^{H}_{r}(B)$,
as the truth of $\psi$ is inhomogeneous among both $v$ and $\\{a_{1},a_{2}\\}$
and among $v$ and $\\{b_{1},b_{2}\\}$. This is a contradiction to
$N^{H}_{r}(A)\cap N^{H}_{r}(B)~{}=~{}\varnothing$. ∎

Combining the results of Section 7 and Section 8 yields the desired chain of
implications.

$\text{prepattern-free}\quad\Rightarrow\quad\text{insulation-
property}\quad\Rightarrow\quad\text{flip-
breakable}\quad\Rightarrow\quad\text{mon.\ dependent}$

In the remaining two sections of Part I, we provide the deferred proofs of the
two insulator growing lemmas (Lemmas 7.6 and 7.7).

###  9 Sample Sets

We work towards proving Lemmas 7.6 and 7.7, which grow the height of an
insulator. In this section we show that in prepattern-free classes, given an
insulator $\mathcal{A}$, we can extract a subinsulator $\mathcal{B}$ and a
small _sample set_ of vertices which can be used to approximately represent
the connections of all the vertices in the graph towards $\mathcal{B}$. We
give some notation to make this statement precise.

######  Definition 9.1.

Given a graph $G$, a vertex $v\in V(G)$, and a set $A\subseteq V(G)$, we
define the _atomic type_ of $v$ over $A$ as

$\mathrm{atp}(v/A):=\\{(R,a):G\models R(v,a),R\in\\{E,=\\},a\in A\\}.$

######  Observation 9.2.

Let $G$ be a graph, $u,v\in V(G)$, and $A\subseteq B\subseteq V(G)$. Then

$\mathrm{atp}(u/A)\neq\mathrm{atp}(v/A)\quad\Rightarrow\quad\mathrm{atp}(u/B)\neq\mathrm{atp}(v/B).$

######  Definition 9.3.

Let $G$ be a graph containing an insulator $\mathcal{A}$ with grid $A$ indexed
by $I$. Let $v,s_{<},s_{>}$ be vertices from $G$, $i\in I$, and
$m\in\mathrm{\mathbb{N}}$. We say _$v$ is $(m,i,s_{<},s_{>})$-sampled on
$\mathcal{A}$_ if

$\mathrm{atp}(v/A[{<}i,*])=\mathrm{atp}(s_{<}/A[{<}i,*])\quad\text{and}\quad\mathrm{atp}(v/A[{\geqslant}i+m,*])=\mathrm{atp}(s_{>}/A[{\geqslant}i+m,*]).$

We call $m$ the _margin_ , $i$ the _exceptional index_ , $s_{<}$ the _left-
sample_ , and $s_{>}$ the _right-sample_.

######  Definition 9.4.

Fix $p\in\mathrm{\mathbb{N}}$. Let $G$ be a graph containing an insulator
$\mathcal{A}$ indexed by $I$ and let $S\subseteq V(G)$. We say _$S$ samples
$G$_ on $\mathcal{A}$ with margin $m$ if there exists functions
$\mathrm{ex}:V(G)\rightarrow I$ and $s_{<},s_{>}:V(G)\rightarrow S$ such that
every $v\in V(G)$ is
$\big{(}m,\mathrm{ex}(v),s_{<}(v),s_{>}(v)\big{)}$-sampled on $\mathcal{A}$.

We are now ready to state the main result of this section.

######  Lemma 9.5.

Fix $t\in\mathrm{\mathbb{N}}$. For every graph $G$ and insulator $\mathcal{A}$
indexed by $J$ in $G$, there is a subsequence $I\subseteq J$ of size
$U_{t}(|J|)$ such that either

  * •

$G$ contains a prepattern of order $t$ on $\mathcal{A}|_{I}$, or

  * •

there is a set $S\subseteq V(G)\setminus\mathcal{A}|_{I}$ of size
$\mathrm{const}(t)$ that samples $G$ on $\mathcal{A}|_{I}$ with margin $2$.

Moreover, there is an algorithm that, given $G$ and $\mathcal{A}$, computes
$I$ and one of the two outcomes (a prepattern or a sampling set $S$) in time
$O_{t}(|V(G)|^{2})$.

We will build the set $S$ iteratively by extracting single sampling vertices
one by one.

####  9.1 Extracting Single Sample Vertices

Before we show how to extract a new sample vertex, we state some auxiliary
lemmas about subinsulators and sampling sets.

######  Lemma 9.6.

Let $\mathcal{A}$ be an insulator indexed by $J$ in a graph $G$. Let $I$ be a
subsequence of $J$, $u,v\in V(G)$, and $i\in\mathrm{tail}(I)$. Let $A$ and $B$
be the grids of $\mathcal{A}$ and $\mathcal{A}|_{I}$ respectively. Then

$\mathrm{atp}(u/A[i,*])\neq\mathrm{atp}(v/A[i,*])\quad\Rightarrow\quad\mathrm{atp}(u/B[i,*])\neq\mathrm{atp}(v/B[i,*]).$

###### Proof.

Follows from 9.2 and 5.8. ∎

######  Lemma 9.7.

Let $\mathcal{A}$ be a grid indexed by a sequence $J$ of length at least four
in a graph $G$ and let $v\in V(G)$. There exists a subsequence $I\subseteq J$
of length $|I|\geqslant\frac{1}{2}|J|$ such that $v\notin\mathcal{A}|_{I}$.

Moreover, there is an algorithm that, given $G$ and $\mathcal{A}$, computes
$I$ in time $O(|V(G)|)$.

###### Proof.

Up to renaming, assume $J=(1,\ldots,n)$. If $v\notin\mathcal{A}|_{I}$, we can
just set $I:=J$. Otherwise, let $i\in J$ be such that $v\in A[i,*]$ where $A$
is the grid of $\mathcal{A}$. We choose $I$ as the larger of the two sequences
$(1,\dots,i-1)$ and $(i,\dots,n)$. Since $I$ has length at least two, this
defines a subinsulator. By 5.8, $v\not\in A|_{I}$. The bound on the running
time is obvious. ∎

######  Lemma 9.8.

Fix $m\in\mathrm{\mathbb{N}}$. Let $G$ be a graph containing an insulator
$\mathcal{A}$ indexed by $J$ and $S\subseteq V(G)$ be a set that samples $G$
on $\mathcal{A}$ with margin $m$. For every $I\subseteq J$, $S$ also samples
$G$ on $\mathcal{A}|_{I}$ with margin $m$.

###### Proof.

Let $B:={A}|_{I}$ be the grid of $\mathcal{A}|_{I}$. As in the first item in
the proof of Lemma 5.9, we observe for every $i\in I$

$B[{<}i,*]\subseteq A[{<}i,*]\quad\text{and}\quad B[{>}i,*]\subseteq
A[{>}i,*].$

Hence, by contrapositive of 9.2, for all vertices $u,s_{<},s_{>}$,

$\mathrm{atp}(v/A[{<}i,*])=\mathrm{atp}(s_{<}/A[{<}i,*])\quad\Rightarrow\quad\mathrm{atp}(v/B[{<}i,*])=\mathrm{atp}(s_{<}/B[{<}i,*]),$
$\mathrm{atp}(v/A[{>}i,*])=\mathrm{atp}(s_{>}/A[{>}i,*])\quad\Rightarrow\quad\mathrm{atp}(v/B[{>}i,*])=\mathrm{atp}(s_{>}/B[{>}i,*]).$

The lemma now follows from Definition 9.4. ∎

We will now show how to extract a new sample vertex. We start with a given set
of sample vertices $S$. In the absence of large prepatterns, we either find a
subinsulator on which $S$ samples $G$, or find a new vertex $v$ by which we
will later use to extend the sample set.

######  Lemma 9.9.

Fix $k,t\in\mathrm{\mathbb{N}}$. For every graph $G$ and insulator
$\mathcal{A}$ indexed by $J$, and every vertex set $S$ of size at most $k$,
there is a subsequence $I\subseteq J$ of size $U_{k,t}(|J|)$ such that either

  * •

$G$ contains a bi-prepattern of order $t$ on $\mathcal{A}|_{I}$, or

  * •

$S$ samples $G$ on $\mathcal{A}|_{I}$ with margin $2$, or

  * •

there is a vertex $v\notin\mathcal{A}|_{I}$, such that for all $s\in S$ and
every column $C$ in $\mathcal{A}|_{I}$

$\mathrm{atp}(v/C)\neq\mathrm{atp}(s/C).$

Moreover, there is an algorithm that, given $G$, $\mathcal{A}$, and $S$,
computes the sequence $I$ and one of the three outcomes (a bi-prepattern, the
conclusion that $S$ samples $G$, or a vertex $v$) in time
$O_{k,t}(|V(G)|^{2})$.

###### Proof.

We first show how to construct a sequence $I$ with the desired properties.
Afterwards we analyze the running time. Getting the desired bounds will then
require a small preprocessing that reduces the size of $J$. The proof is split
into multiple paragraphs.

###### Notation.

For vertices $v,s\in V(G)$ and a set $U\subseteq V(G)$, we say _$v$ is
$s$-connected to $U$_ if

$\mathrm{atp}(v/U)=\mathrm{atp}(s/U).$

We generalize this to sets $S_{\star}\subseteq S$ and say _$v$ is
$S_{\star}$-connected to $U$_ if

$\\{s\in S\mid\text{$v$ is $s$-connected to $U$}\\}=S_{\star}.$

###### Ramsey.

We start by defining some coloring to which we will apply Ramsey’s theorem.
Let $A$ be the grid of $\mathcal{A}$ and $M_{A}$ be the function from Lemma
5.6. For $t^{\prime}\in\\{6,4t\\}$ and $S_{1},\dots,S_{t^{\prime}-1}\subseteq
S$, we label all $t^{\prime}$-tuples $i_{1}<\dots<i_{t^{\prime}}\in J$ with a
color indicating whether

$\exists v\bigwedge_{l=1,\dots,t^{\prime}-1}\text{ $v$ is $S_{l}$-connected to
$M_{A}(i_{l},i_{l+1})$}.$ (1)

Applying Ramsey’s Theorem (Lemma 4.2) to this coloring gives us a subsequence
$I^{\prime}\subseteq J$ such that for all $t^{\prime}\in\\{8,6t\\}$ and
$S_{1},\dots,S_{t^{\prime}-1}\subseteq S$, the above equation (1) either holds
for all or no $t^{\prime}$-tuples $i_{1}<\dots<i_{t^{\prime}}\in I^{\prime}$.
Note that the number of colors is bounded by $\mathrm{const}(k,t)$, which
guarantees $|I^{\prime}|\geqslant U_{k,t}(|J|)$. We can assume without loss of
generality that $I:=\mathrm{tail}(I^{\prime})$ has length at least $24t$. In
order to simplify notation, we assume up to renaming that
$I^{\prime}=(0,\ldots,n)$ and $I=(1,\ldots,n)$. Let $B:=A|_{I^{\prime}}$ be
the grid of $\mathcal{B}:=\mathcal{A}|_{I^{\prime}}$. By Lemma 5.6, we observe
the following.

######  Observation 9.10.

For all $i\in I$ we have $B[i,*]=M_{A}(i-1,i)$.

We say a subsequence of a sequence $K$ is _$1$ -spaced_ if it contains no
consecutive elements from $K$.

######  Claim 9.11.

Let $s\in S$ and $\bar{w}\in\\{0,1\\}^{2t}$. If there is a $1$-spaced
subsequence $i_{1}<\dots<i_{2t}$ of $I$ such that

$\exists v\bigwedge_{l=1,\dots,2t}\text{$v$ is $s$-connected to $B[i_{l},*]$
if and only if $w_{l}=1$},$

then the above holds for all such $1$-spaced subsequences of the same length.

###### Proof.

By 9.10, the statement of the claim holds for a $1$-spaced subsequence
$i_{1}<\dots<i_{2t}$ if and only if equation (1) holds for the corresponding
$4t$-tuple

$i_{1}-1<i_{1}<i_{2}-1<i_{2}<\dots<i_{2t}-1<i_{2t}\in I^{\prime}$

of distinct elements and some $S_{1},\dots,S_{4t-1}\subseteq S$ with $s\in
S_{2l-1}\Leftrightarrow w_{l}=1$. Note that we use $1$-spacedness to guarantee
that all elements in the $4t$-tuple are distinct.

Assume there is a $1$-spaced subsequence satisfying the claimed statement, and
let $S_{1},\dots,S_{4t-1}\subseteq S$ be the sets witnessing the truth of
equation (1) for the corresponding $4t$-tuple. By Ramsey’s theorem, equation
(1) with $S_{1},\dots,S_{4t-1}\subseteq S$ holds for all $4t$-tuples, and
thus, the claimed statement holds for all $1$-spaced subsequences. ∎

######  Claim 9.12.

If there is $i,j\in I$ with $i+2<j$ and sets $P_{i},Q_{i},P_{j},Q_{j}\subseteq
S$ with $P_{i}\neq Q_{i}$ and $P_{j}\neq Q_{j}$ such that

$\displaystyle\exists v~{}$ $v$ is $P_{i}$-connected to $B[i,*]$
$\displaystyle\wedge$ $v$ is $Q_{i}$-connected to $B[i+1,*]$
$\displaystyle\wedge$ $v$ is $P_{j}$-connected to $B[j,*]$
$\displaystyle\wedge$ $v$ is $Q_{j}$-connected to $B[j+1,*]$

then the above holds for all $i,j\in I$ with $i+2<j$.

###### Proof.

We again use 9.10. Thus, the statement of the claim holds for a given $i,j\in
I$ if and only if equation (1) holds for the corresponding $6$-tuple

$i-1<i<i+1<j-1<j<j+1\in I^{\prime}$

of distinct elements and some $S_{1},\dots,S_{5}\subseteq S$ with
$S_{1}=P_{i}$ and $S_{2}=Q_{i}$ and $S_{4}=P_{j}$ and $S_{5}=Q_{j}$. The rest
follows as in 9.11. ∎

###### Constructing a Prepattern.

We say an index $i\in I$ is an _alternation point_ of a vertex $v$ on
$\mathcal{B}$ if $v$ is $P$-connected to $B[i,*]$ and $Q$-connected to
$B[i+1,*]$ for distinct sets $P\neq Q\subseteq S$.

######  Claim 9.13.

One of the following two conditions holds.

  1. 1.

For every vertex $v\in V(G)$ with alternation points $i,j\in I$, we have
$|i-j|\leqslant 2$.

  2. 2.

$G$ contains a bi-prepattern of order $t$ on $\mathcal{B}$.

###### Proof.

Assume the first condition fails and let $v\in V(G)$ be a vertex with
alternation points $i,j\in I$ such that $i+2<j$. By 9.12, we can assume
without loss of generality that $v$ has alternation points $6t$ and $19t$. In
the following, we find two $1$-spaced subsequences of $I$

$\displaystyle
I_{\star}=\underbrace{i_{1}<\dots<i_{t}}_{\subseteq(1,\ldots,4t)}\;\;<\;\;\underbrace{i_{\star\vphantom{t}}}_{\mathclap{\in\\{6t,6t+1\\}}}\;\;<\;\;\underbrace{i_{t+1}<\dots<i_{2t}}_{\subseteq(9t,11t)},$
$\displaystyle
J_{\star}=\underbrace{j_{1}<\dots<j_{t}}_{\subseteq(13t,\ldots,17t)}\;\;<\;\;\underbrace{j_{\star\vphantom{t}}}_{\mathclap{\in\\{19t,19t+1\\}}}\;\;<\;\;\underbrace{j_{t+1}<\dots<j_{2t}}_{\subseteq(22t,\ldots,24t)}$

and vertices $s_{1},s_{2}\in S$ satisfying the following property: Either

  * •

$i_{\star}$ is the first index among $I_{\star}$, such that $v$ is
$s_{1}$-connected to $B[i_{\star},*]$, or

  * •

$i_{\star}$ is the first index among $I_{\star}$, such that $v$ is _not_
$s_{1}$-connected to $B[i_{\star},*]$,

and moreover, either

  * •

$j_{\star}$ is the first index among $J_{\star}$, such that $v$ is
$s_{2}$-connected to $B[j_{\star},*]$, or

  * •

$j_{\star}$ is the first index among $J_{\star}$, such that $v$ is _not_
$s_{2}$-connected to $B[j_{\star},*]$.

We start by chosing $s_{1}\in S$ to be an arbitrary vertex witnessing the