Extension Preservation on Dense Graph Classes

Eleftheriadis, Ioannis

doi:10.4230/LIPIcs.CSL.2025.7

Extension Preservation on Dense Graph Classes

Ioannis Eleftheriadis

Department of Computer Science and Technology, University of Cambridge, UK

Abstract

Preservation theorems provide a direct correspondence between the syntactic structure of first-order sentences and the closure properties of their respective classes of models. A line of work has explored preservation theorems relativised to combinatorially tame classes of sparse structures [Atserias et al., JACM 2006; Atserias et al., SiCOMP 2008; Dawar, JCSS 2010; Dawar and Eleftheriadis, MFCS 2024]. In this article we initiate the study of preservation theorems for dense classes of graphs. In contrast to the sparse setting, we show that extension preservation fails on most natural dense classes of low complexity. Nonetheless, we isolate a technical condition which is sufficient for extension preservation to hold, providing a dense analogue to a result of [Atserias et al., SiCOMP 2008].

Keywords and phrases:

Extension preservation, finite model theory, dense graphs, cliquewidth

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Finite Model Theory

Funding:

The author is supported by a George and Marie Vergottis Scholarship awarded through Cambridge Trust, an Onassis Foundation Scholarship, and a Robert Sansom Studentship.

DOI:

10.4230/LIPIcs.CSL.2025.7

Event:

33rd EACSL Annual Conference on Computer Science Logic (CSL 2025)

Editors:

Jörg Endrullis and Sylvain Schmitz

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

The early days of finite model theory were considerably guided by attempts aiming to relativise theorems and techniques of classical model theory to the finite realm. While many of these were trivially shown to admit no meaningful relativisation, others were extended in a way that broadened their applicability and rendered them extremely useful tools in the study of finite models. Preservation theorems were at the heart of this approach. Most notably, the Łoś-Tarski preservation theorem which asserts that a first-order formula is preserved by extensions between all structures if and only if it is equivalent to an existential formula, was shown to fail in the finite from early on [28, 22]. On the contrary, the homomorphism preservation theorem asserting that a formula is preserved by homomorphisms if and only if it is existential-positive, was open for several years until it was surprisingly shown to extend to finite structures [27], leading to applications in constraint satisfaction problems and database theory.

Still, considering all finite structures allows for combinatorial complexity, giving rise to wildness from a model-theoretic perspective, and intractability from a computational perspective. Indeed, problems which are hard in general become tractable when restring to classes of finite structures which are, broadly-speaking, tame [12]. In the context of preservation theorems, restricting on a subclass weakens both the hypothesis and the conclusion, therefore leading to an entirely new question. A study of preservation properties for such restricted classes of finite structures was initiated in [4] and [3] for homomorphism and extension preservation respectively. This investigation led to the introduction of different notions of wideness, which allow for arguments based on the locality of first-order logic. However, as it was recently realised [14], these arguments require slightly restrictive closure assumptions which are not always naturally present. In particular, it was shown that homomorphism preservation holds over any hereditary quasi-wide class which is closed under amalgamation over bottlenecks.

Quasi-wideness is a Ramsey-theoretic condition which informally says that in any large enough structure in the class one can remove a bounded number of elements, called bottleneck points, so that there remains a large set of pairwise far-away elements. Here, the number of bottleneck points is allowed to dependent on the choice of distance. Hereditary quasi-wide classes were later identified with nowhere dense classes [24]. Over the years, a successful program was developed aiming to understand the combinatorial and model-theoretic features of nowhere dense classes, and exploit them for algorithmic purposes [25]. The culmination of this was the seminal result that first-order model checking is fixed-parameter tractable on nowhere dense classes [21].

In recent years, the focus has shifted towards extending this well understood theory to more general, possibly dense, well-behaved classes, which fall out of the classification provided by the sparsity program. In these efforts, the model-theoretic notions of monadic stability and monadic dependence have played central roles. Monadic stability, initially introduced by Baldwin and Shelah [5] in the context of classification of complete first-order theories, prohibits arbitrarily large definable orders in monadic expansions. In the language of first-order transductions, a class is monadically stable whenever it does not transduce the class of finite linear orders. More generally, a class is monadically dependent if it does not transduce the class of all graphs. In the context of monotone classes of graphs, Adler and Adler [1] first observed that the above notions coincide with nowhere density, a result which was also extended to arbitrary relational structures [7]. The generalisation of sparsity theory to dense classes eventually led to the result that first-order model checking is fixed-parameter tractable on all monadically stable graph classes [15], which in particular include transductions of nowhere dense classes. It is conjectured that the above result extends to all monadically dependent classes, while a converse was recently established for hereditary graph classes (under standard complexity-theoretic assumptions) [18].

The purpose of the present article is to initiate the investigation of preservation theorems on tame dense graph classes. Much like nowhere dense classes are equivalently characterised by quasi-wideness, monadically stable and monadically dependent graph classes also admit analogous wideness-type characterisations. In the case of monadic stability, the relevant condition is known as flip-flatness [17]; this may be viewed as a direct analogue of quasi-wideness which replaces the vertex deletion operation by flips, i.e. edge-complementations between subsets of the vertex set. For monadically dependent classes the relevant condition, known as flip-breakability [18], allows to find two large sets such that elements in one are far away from elements in the other, again after performing a bounded number of flips. However, unlike quasi-wideness which was introduced in the context of preservation and then shown to coincide with nowhere density, these conditions were introduced purely for the purpose of providing combinatorial characterisations of monadic stability and monadic dependence respectively. The immediate question thus becomes whether these conditions, or variants thereof, can be used to obtain preservation in restricted tame dense classes, in analogy to the use of wideness in [3, 4, 13, 14].

The first observation is that the arguments for homomorphism preservation are not directly adaptable in this context due to the nature of flips. Indeed, while the vertex-deletion operation respects the existence of a homomorphism between two structures, the flip operation is not at all rigid with respect to homomorphisms precisely because the latter do not reflect relations, e.g. the graph $K_{1}+K_{1}$ homomorphically maps to $K_{2}$ , but $\overline{(K_{1}+K_{1})}=K_{2}$ does not map to $\overline{K_{2}}=K_{1}+K_{1}$ . This issue evidently disappears if one considers embeddings. As it was observed in [14, Corollary 2.3], the extension preservation property implies the homomorphism preservation property in hereditary classes of finite structures, so considering extension preservation is more general for our purposes.

However, this generality comes at a cost. Indeed, the argument for extension preservation from [3] requires that the number of vertex-deletions is independent of the choice of radius, a condition known as almost-wideness. This is a more restrictive assumption which therefore applies to fewer sparse classes. It is not known whether extension preservation is obtainable for quasi-wide classes. At the same time, unlike [14, Theorem 4.2] whose proof is essentially a direct application of Gaifman’s locality theorem based on an argument of Ajtai and Gurevich [2], the proof of extension preservation [3, Theorem 4.3] is admittedly much more cumbersome. One explanation for this is that the homomorphism preservation argument relies on the fact that the disjoint union operation endows the category of graphs and homomorphisms with coproducts, i.e. for any graphs $A, B, C$ if there are homomorphisms $f:A\to C$ and $g:B\to C$ then there is a homomorphism $f+g:A+B\to C$ whose pre-compositions with the respective inclusion homomorphisms $\iota_{A}:A\to A+B$ and $\iota_{B}:B\to A+B$ are equal to $f$ and $g$ respectively. On the other hand, no construction satisfies the above property in the category of graphs with embeddings; in fact coproducts do not even exist in the category of graphs with strong homomorphisms (see [23, Corollary 4.3.15]).

Our first contribution is negative, showing that extension preservation can fail on tame dense classes of low complexity. In particular, we show that extension preservation fails on the class of all graphs of (linear) cliquewidth at most $k$ , for all $k\geq 4$ . This answers negatively a question of [14]. This is contrary to the sparse picture, where it was shown that extension preservation holds in the class of graphs of treewidth at most $k$ , for every $k\in\mathbb{N}$ [3, Theorem 5.2]. Interestingly, extension preservation holds for the class of all graphs of cliquewidth $2$ as this class coincides with the class of cographs which is known to be well-quasi-ordered [11]. Our construction is based on the encoding of linear orders via the neighbourhoods of certain vertices. Orders are also central to the original counterexample for the failure of extension preservation in the finite due to Tait [28]. There, the orders are crucially presented over a signature with two relation symbols and one constant, which does not allow for a direct translation to undirected graphs. Sadly, the fact that orders appear to provide counterexamples rules out the possibility of using an argument based on flip-breakability to establish preservation.

The second contribution of the article is positive. In particular, we provide a dense analogue to [3, Theorem 4.3]. For this, we introduce strongly flip-flat classes, i.e. those flip-flat classes such that the number of flips is independent of the choice of radius. Moreover, we formulate the dense analogue of the amalgamation construction, which we call the flip-sum, whose existence in the class is necessary for the argument to be carried out. The main theorem (Theorem 18 below) may thus be formulated as saying that extension preservation holds over any hereditary strongly flip-flat class which is closed under flip-sums over bottleneck partitions.

2 Preliminaries

We assume familiarity with the standard notions of finite model theory and structural graph theory, and refer to [19] and [25] for reference. In this article, graphs shall always refer to simple undirected graphs i.e. structures over the signature $\tau_{E}=\{E\}$ where $E$ is interpreted as a symmetric and anti-reflexive binary relation. For a graph $G$ we write $V(G)$ for its domain (or vertex set), and $E(G)$ for its edge set. In general, for a $\tau$ -structure $A$ and a relation symbol $R\in\tau$ of arity $r\in\mathbb{N}$ we write $R^{A}\subseteq A^{r}$ for the interpretation of $R$ in $A$ . We shall abuse notation and not distinguish between structures and their respective domains.

Given two structures $A, B$ in the same relational signature $\tau$ , a homomorphism $f:A\to B$ is a map that preserves all relations, i.e. for all $R\in\tau$ and tuples $\bar{a}$ from $A$ we have $\bar{a}\in R^{A}\implies f(\bar{a})\in R^{B}$ . A strong homomorphism is a homomorphism $f:A\to B$ that additionally reflects all relations, i.e. $f(\bar{a})\in R^{B}\implies\bar{a}\in R^{A}$ . An injective strong homomorphism is called an embedding or extension.

A $\tau$ -structure $B$ is said to be a weak substructure of a $\tau$ -structure $A$ if $B\subseteq A$ and the inclusion map $\iota:B\hookrightarrow A$ is a homomorphism. Likewise, $B$ is an induced substructure of $A$ if the inclusion map is an embedding; we write $B\leq A$ for this. Given a structure $A$ and a subset $S\subseteq A$ we write $A[S]$ for the unique induced substructure of $A$ with domain $S$ . An induced substructure $B$ of $A$ is said to be proper if $B\subsetneq A$ ; we write $B\lneq A$ for this. We say that a class of structures in the same signature is hereditary if it is closed under induced substructures. Moreover a class is called addable if it is closed under taking disjoint unions, which we denote by $A+B$ .

By the Gaifman graph of a structure $A$ we mean the undirected graph $\mathsf{Gaif}(A)$ with vertex set $A$ such that two elements are adjacent if, and only if, they appear together in some tuple of a relation of $A$ . Given a structure $A$ , $r\in\mathbb{N}$ , and $a\in A$ , we write $N^{A}_{r}(a)$ for the $r$ -neighbourhood of $a$ in $A$ , that is, the set of elements of $A$ whose distance from $a$ in $\mathsf{Gaif}(A)$ is at most $r$ . We shall often abuse notation and write $N^{A}_{r}(a)$ for the induced substructure $A[N^{A}_{r}(a)]$ of $A$ . For a set $C\subseteq A$ we define $N^{A}_{r}(C):=\bigcup_{a\in C}N^{A}_{r}(a)$ . A set $S\subseteq A$ is said to be $r$ -independent if $b\notin N^{A}_{r}(a)$ for any $a,b\in S$ .

For $r\in\mathbb{N}$ , let $\mathrm{dist}(x,y)\leq r$ be the first-order formula expressing that the distance between $x$ and $y$ in the Gaifman graph is at most $r$ , and $\mathrm{dist}(x,y)>r$ its negation. Clearly, the quantifier rank of $\mathrm{dist}(x,y)\leq r$ is at most $r$ . A basic local sentence is a sentence

\exists x_{1},\dots,x_{n}(\bigwedge_{i\neq j}\mathrm{dist}(x_{i},x_{j})>2r% \land\bigwedge_{i\in[n]}\psi^{N_{r}(x_{i})}(x_{i})),

where $\psi^{N_{r}(x_{i})}(x_{i})$ denotes the relativisation of $\psi$ to the $r$ -neighbourhood of $x_{i}$ , i.e. the formula obtained from $\psi$ by replacing every quantifier $\exists x\ \theta$ with $\exists x(\mathrm{dist}(x_{i},x)\leq r\land\theta)$ , and likewise every quantifier $\forall x\ \theta$ with $\forall x(\mathrm{dist}(x_{i},x)\leq r\to\theta)$ . We call $r$ the locality radius, $n$ the width, and $\psi$ the local condition of $\phi$ . Recall the Gaifman locality theorem [19, Theorem 2.5.1].

Theorem 1 (Gaifman Locality).

Every first-order sentence of quantifier rank $q$ is equivalent to a Boolean combination of basic local sentences of locality radius $7^{q}$ .

A class $\mathcal{C}$ of structures is said to be quasi-wide if for every $r\in\mathbb{N}$ there exist $k_{r}\in\mathbb{N}$ and $f_{r}:\mathbb{N}\to\mathbb{N}$ such that for all $m\in\mathbb{N}$ and all $A\in\mathcal{C}$ of size at least $f_{r}(m)$ there exists $S\subseteq A$ such that $A\setminus S$ contains an $r$ -independent set of size $m$ . Moreover, if $k_{r}:=k\in\mathbb{N}$ is independent of $r$ , then $\mathcal{C}$ is said to be almost-wide. Finally, we say that a class $\mathcal{C}$ is uniformly quasi-wide (uniformly almost-wide respectively) if the hereditary closure of $\mathcal{C}$ is quasi-wide (almost-wide respectively).

For a graph $G$ and a pair of disjoint vertex subsets $U$ and $V$ , the subgraph semi-induced by $U$ and $V$ is the bipartite graph with sides $U$ and $V$ that contains all edges of $G$ with one endpoint in $U$ and second in $V$ . By the half-graph of order $n$ we mean the bipartite graph with vertices $\{u_{i},v_{i}:i\in[n]\}$ and edges $\{(u_{i},v_{j}):i\leq j\}$ .

For first-order formulas $\delta(x)$ and $\phi(x,y)$ the interpretation $I_{\delta,\phi}$ is defined to be the operation that maps a graph $G$ to the graph $H:=I_{\delta,\phi}(G)$ with vertex set $V(H):=\left\{v\in V(G)\colon G\models\delta(v)\right\}$ and edge set

E(H):=\left\{(u,v)\in V(H)^{2}\colon u\neq v\land G\models(\phi(u,v)\lor\phi(v% ,u))\right\}.

For a graph class $\mathcal{C}$ , we write $I_{\delta,\phi}(\mathcal{C}):=\{I_{\delta,\phi}(G):G\in\mathcal{C}\}$ . We say that a class $\mathcal{C}$ is an interpretation of a class $\mathcal{D}$ , or that $\mathcal{D}$ interprets $\mathcal{C}$ , if there is some $I_{\delta,\phi}$ such that $\mathcal{C}\subseteq I_{\delta,\phi}(\mathcal{D})$ . We say that $\mathcal{C}$ is a transduction of a class $\mathcal{D}$ , or $\mathcal{D}$ transduces $\mathcal{C}$ , if there are $k\in\mathbb{N}$ and unary predicates $P_{1},\dots,P_{k}$ and formulas $\delta(x)$ and $\phi(x,y)$ over the signature $\tau_{E}\cup\{P_{1},\dots,P_{k}\}$ such that $\mathcal{C}\subseteq I_{\delta,\phi}(\mathcal{D}^{k})$ , where $\mathcal{D}^{k}$ is the class of all $\tau_{E}\cup\{P_{1},\dots,P_{k}\}$ -structures whose $\tau_{E}$ -reducts are in $\mathcal{D}$ . A graph class $\mathcal{C}$ is monadically dependent if $\mathcal{C}$ does not transduce the class of all graphs. $\mathcal{C}$ is moreover monadically stable if $\mathcal{C}$ does not transduce the class of all half-graphs.

We say that a formula $\phi$ is preserved by extensions over a class of structures $\mathcal{C}$ if for all $A,B\in\mathcal{C}$ such that there is a embedding from $B$ to $A$ , $B\models\phi$ implies that $A\models\phi$ . We say that a class of structures $\mathcal{C}$ has the extension preservation property if for every formula $\phi$ preserved by extensions over $\mathcal{C}$ there is an existential formula $\psi$ such that $M\models\phi\iff M\models\psi$ for all $M\in\mathcal{C}$ . We analogously define the homomorphism preservation property, replacing “embeddings” with “homomorphisms” and “existential” with “existential positive” in the above.

Given a formula $\phi$ and a class of structures $\mathcal{C}$ , we say that $M\in\mathcal{C}$ is a minimal induced model of $\phi$ in $\mathcal{C}$ if $M\models\phi$ and for any proper induced substructure $N$ of $M$ with $N\in\mathcal{C}$ we have $N\not\models\phi$ . The relationship between minimal models and extensions preservation is highlighted by the following folklore lemma. We provide a proof for completeness.

Lemma 2.

Let $\mathcal{C}$ be a hereditary class of finite structures. Then a sentence preserved by extensions in $\mathcal{C}$ is equivalent to an existential sentence over $\mathcal{C}$ if and only if it has finitely many minimal induced models in $\mathcal{C}$ .

Proof.

Suppose that $\phi$ has finitely many minimal induced models in $\mathcal{C}$ , say $M_{1},\dots,M_{n}$ . For each $i\in[n]$ , let $\psi_{i}$ be the primitive sentence inducing a copy of $M_{i}$ and write $\psi:=\bigvee_{i\in[n]}\psi_{i}$ ; evidently $\psi$ is existential. We argue that $\phi$ is equivalent to $\psi$ over $\mathcal{C}$ . Indeed, if $A\in\mathcal{C}$ models $\phi$ then $A$ contains a minimal induced model $B$ of $\phi$ as an induced substructure. By hereditariness $B\in\mathcal{C}$ and so $B$ is isomorphic to some $M_{i}$ . Since there is clearly an embedding $B\to A$ it follows that $A\models\psi$ . On the other hand if $A\models\psi$ , then $A\models\psi_{i}$ for some $i\in[n]$ and so some $M_{i}$ embeds into $A$ . Since $M_{i}\models\phi$ and $\phi$ is preserved by extensions this implies that $A\models\phi$ as required.

Conversely, assume that $\phi$ is equivalent to an existential sentence over $\mathcal{C}$ . In particular, $\phi$ is equivalent to some disjunction $\bigvee_{i\in[n]}\psi_{i}$ where each $\psi_{i}$ is primitive. It follows that each $\psi_{i}$ is the formula inducing one of finitely many structures $M^{i}_{1},\dots,M^{i}_{k_{i}}$ . Now, if $A$ is a minimal induced model of $\phi$ then in particular $A\models\psi_{i}$ for some $i\in[n]$ , i.e. there is some $j\in[k_{i}]$ and an embedding $h:M^{i}_{j}\to A$ . If $h$ is not surjective, then $A[h[M^{i}_{j}]]$ is a proper induced substructure of $A$ , which is in $\mathcal{C}$ by hereditariness, and models $\phi$ ; this contradicts the minimality of $A$ . Hence, the size of every minimal induced model of $\phi$ in $\mathcal{C}$ is bounded by $\max_{i\in[n]}\max_{j\in[k_{i}]}|M^{i}_{j}|$ . It follows that $\phi$ can have only finitely many minimal induced models in $\mathcal{C}$ . $\hfill\blacktriangleleft$

3 Failure of preservation on graphs of cliquewidth 4

One consequence of Lemma 2 is that extension preservation holds over any class $\mathcal{C}$ that is well-quasi-ordered by the induced substructure relation, i.e. classes for which there exists no infinite collection of members which pairwise do not embed into one another. In particular, this applies to the class of cographs [11], which are precisely the graphs of cliquewidth $2$ (see [9] for background on cliquewidth). Hence, one may reasonably inquire whether extension preservation is generally true for the class $\mathcal{CW}_{k}$ of all graphs of cliquewidth at most $k$ . This would in particular reflect an analogous phenomenon that is true in the sparse setting, that is, that extension preservation holds over the class $\mathcal{TW}_{k}$ of all graphs of treewidth at most $k$ [3, Theorem 5.2].

Classes of bounded cliquewidth are not monadically stable, as even the class of cographs contains arbitrarily large semi-induced half-graphs, but they are monadically dependent. In fact, their structural properties imply tame behaviour going much beyond the context of first-order logic (see [10] for a survey). Still, as it turns out, extension preservation fails even at the level of cliquewidth $4$ . To show this, we produce a formula $\phi$ preserved by extensions over the class of all finite undirected graphs, which admits infinitely many minimal models of cliquewidth $4$ . In particular, Lemma 2 implies that extension preservation fails on any class that includes these minimal models. Our idea is based on encoding two interweaving linear orders on the two parts of a semi-induced graph. Two vertices on the same part are comparable in this ordering whenever their neighbourhoods in the other part are set-wise comparable. This effectively forces a semi-induced half-graph.

Our formula is in the form of an implication, proceeded by a primitive part which induces a gadget corresponding to the beginning and end of the two linear orders. The antecedent of the implication first makes sure that the above relation is a pre-ordering on each side of the semi-induced graph, while it imposes that the vertices of the gadget corresponding to the minimal and maximal elements are indeed minimal and maximal in this pre-ordering. Moreover, it essentially ensures that successors, i.e. vertices of the same part whose neighbourhoods over the other part differ by a single element, are adjacent on one part and non-adjacent on the other. The consequent then imposes that any vertex on the first side has an adjacent successor, while every vertex on the other side has a non-adjacent successor. Because each one of the two pre-orders precisely compares neighbourhoods over the other part, this forces the pre-orders to be anti-symmetric, and thus the two parts to have the same number of vertices.

Finally, two additional vertices are also added on one side of the semi-induced bipartite graph, which are part of the gadget and serve no role in this ordering. These make sure that our intended minimal models form an anti-chain in the embedding relation, as they crucially result in the existence of a unique embedding of the gadget into the models (Lemma 5 below).

We now turn to formal definitions. Let $I(v_{1},v_{2},v_{3},v_{4},v_{5},v_{6},u_{1},u_{2},u_{3},u_{4},u_{5},u_{6},a,b)$ be the formula that induces the graph of Figure 1 below. In the following, we treat the free variables of $I$ as constants for simplicity. The notation $\forall(x\in U)$ will denote the relativisation of the universal quantifier to the neighbours of $v_{1}$ that are not $v_{2}$ , i.e. $\forall(x\in U)\ \psi(x)$ is shorthand for $\forall x(E(x,v_{1})\land x\neq v_{2}\to\psi(x))$ . Likewise, the notation $\forall(x\in V)$ denotes the relativisation of the universal quantifier to the non-neighbours of $v_{1}$ that are not $a$ or $b$ , i.e. $\forall(x\in V)\ \psi(x)$ is shorthand for $\forall x(\neg E(x,v_{1})\land x\neq a\land x\neq b\to\psi(x))$ . Existential quantifiers relativised to $U$ and $V$ are defined analogously. Consider the auxiliary formulas:

x\leq_{V}y:=\forall(z\in U)[E(z,x)\to E(z,y)];

x<_{V}y:=x\leq_{V}y\land\neg(y\leq_{V}x);

\chi_{1}:=\forall(x\in V)\forall(y\in V)[x\leq_{V}y\lor y\leq_{V}x];

\chi_{2}:=\forall(x\in U)[E(x,v_{6})\to x=u_{6}];

\chi_{3}:=\forall(x\in V)\forall(y\in V)[x<_{V}y\land E(x,y)\to\exists!(z\in U% )(E(y,z)\land\neg E(x,z))].

In analogy, we define:

x\leq_{U}y:=\forall(z\in V)[E(z,x)\to E(z,y)];

x<_{U}y:=x\leq_{U}y\land\neg(y\leq_{U}x);

\xi_{1}:=\forall(x\in U)\forall(y\in U)[x\leq_{U}y\lor y\leq_{U}x];

\xi_{2}:=\forall(x\in V)[E(x,u_{1})\to x=v_{1}];

\xi_{2^{*}}:=\forall(x\in V)\ E(x,u_{6});

\xi_{3}:=\forall(x\in U)\forall(y\in U)[x<_{U}y\land\neg E(x,y)\to\exists!(z% \in V)(E(y,z)\land\neg E(x,z))].

We then define:

\phi_{1}:=\chi_{1}\land\chi_{2}\land\chi_{3};

\phi_{2}:=\forall(x\in V)[x\neq v_{1}\to\exists(y\in V)(E(x,y)\ \land\ x<_{V}y% )];

\psi_{1}:=\xi_{1}\land\xi_{2}\land\xi_{2^{*}}\land\xi_{3};

\psi_{2}:=\forall(x\in U)[x\neq u_{6}\to\exists(y\in U)(\neg E(x,y)\land x<_{U% }y)].

Putting the above together we finally define:

\phi:=\exists\bar{v},\bar{u},a,b(I(\bar{v},\bar{u},a,b)\land[\phi_{1}(\bar{v},% \bar{u},a,b)\land\psi_{1}(\bar{v},\bar{u},a,b)\to\phi_{2}(\bar{v},\bar{u},a,b)% \land\psi_{2}(\bar{v},\bar{u},a,b)])

Figure 1: The gadget induced by

I(\bar{v},\bar{u},a,b)

.

Proposition 3.

The formula $\phi$ is preserved by extensions over the class of all finite graphs.

Proof.

Let $G, H$ be two graphs such that $G$ embeds into $H$ , and $G\models\phi$ . Without loss of generality we assume that $V(G)\subseteq V(H)$ and that the identity map is an embedding. We shall argue that $H\models\phi$ .

Since $G\models\phi$ , we may fix (tuples of) vertices $\bar{v},\bar{u},a,b\in V(G)$ such that $G\models I(\bar{v},\bar{u},a,b)$ . Evidently, $H$ also models $I(\bar{v},\bar{u},a,b)$ . If $H\not\models(\phi_{1}(\bar{v},\bar{u},a,b)\land\psi_{1}(\bar{v},\bar{u},a,b))$ then $H\models\phi$ ; we may therefore assume that $H\models(\phi_{1}(\bar{v},\bar{u},a,b)\land\psi_{1}(\bar{v},\bar{u},a,b))$ . Let $U:=N_{H}(v_{1})\setminus\{v_{2}\}\subseteq V(H)$ be the neighbours of $v_{1}$ in $H$ that are not $v_{2}$ , and $V:=V(H)\setminus(U\cup\{a,b\})\subseteq V(H)$ be the non-neighbours of $v_{1}$ that are not $a$ or $b$ (in particular $v_{1}\in V$ ). We call the vertices $x\in V$ $V$ -elements. For each $V$ -element $x$ we write $U_{x}:=\{y\in U:H\models E(x,y)\}$ for the $U$ -neighbourhood of $x$ . We similarly define $U$ -elements and $V$ -neighbourhoods. From each of the conjuncts $\chi_{i}$ of $\phi_{1}$ we deduce that in $H$ :

$\chi_{1}$ :: $V$ -elements have pairwise comparable $U$ -neighbourhoods;
$\chi_{2}$ :: the only member of $U_{v_{6}}$ is $u_{6}$ ;
$\chi_{3}$ :: if two adjacent $V$ -elements $x, y$ satisfy $U_{x}\subsetneq U_{y}$ then $|U_{y}|=|U_{x}|+1$ .

We shall argue that items $(1)$ - $(3)$ are still true within $G$ , replacing $V$ with $V^{\prime}:=V\cap V(G)$ and $U$ with $U^{\prime}:=U\cap V(G)$ , and so $G\models\phi_{1}(\bar{v},\bar{u},a,b)$ . We write $U^{\prime}_{x}:=U_{x}\cap V(G)$ for the relativised $U^{\prime}$ -neighbourhoods. Clearly, items $(1)$ and $(2)$ are still true in $G$ . For item $(3)$ , suppose that $x,y\in V^{\prime}$ are two adjacent $V^{\prime}$ -elements, such that $V^{\prime}_{x}\subsetneq V^{\prime}_{y}$ . Since $V$ -elements in $H$ have pairwise comparable $U$ -neighbourhoods, we deduce that $V_{x}\subsetneq V_{y}$ and therefore that $|V_{y}|=|V_{x}|+1$ as $H$ satisfies $\chi_{3}$ . In particular, it follows that $|V^{\prime}_{y}|=|V^{\prime}_{x}|+1$ as required, and so $G$ models $\chi_{3}(\bar{v},\bar{u},a,b)$ and consequently $\phi_{1}(\bar{v},\bar{u},a,b)$ .

Similarly, from each of the conjuncts $\xi_{i}$ of $\psi_{1}$ we deduce that in $H$ :

$\xi_{1}$ :: $U$ -elements have pairwise comparable $V$ -neighbourhoods;
$\xi_{2}$ :: the only element of $V_{u_{1}}$ is $v_{1}$ ;
$\xi_{2^{*}}$ :: $V_{u_{6}}$ is equal to $V$ ;
$\xi_{3}$ :: if two non-adjacent $U$ -elements satisfy $V_{x}\subsetneq V_{y}$ then $|V_{y}|=|V_{x}|+1$ .

Arguing as before, we obtain that $G\models\psi_{1}(\bar{v},\bar{u},a,b)$ . Since $G\models\phi$ and $G\models(\phi_{1}(\bar{v},\bar{u},a,b)\land\psi_{1}(\bar{v},\bar{u},a,b))$ we deduce that $G\models(\phi_{2}(\bar{v},\bar{u},a,b)\land\psi_{2}(\bar{v},\bar{u},a,b))$ , i.e. the following are true in $G$ :

$\phi_{2}$ :: every $V^{\prime}$ -element that is not $v_{1}$ is adjacent to a $V^{\prime}$ -element of strictly greater $U^{\prime}$ -neighbourhood;
$\psi_{2}$ :: every $U^{\prime}$ -element that is not $u_{6}$ is non-adjacent to a $U^{\prime}$ -element of strictly greater $V^{\prime}$ -neighbourhood.

We proceed to show that the above implies that $V=V^{\prime}$ and $U^{\prime}=U$ , and hence $G=H$ . In particular, this implies that $H\models\phi$ as claimed.

Since $G$ is finite and satisfies $\phi_{2}$ we obtain some $n\in\mathbb{N}$ and a sequence of distinct elements $\alpha_{1}:=v_{6},\alpha_{2},\dots,\alpha_{n}:=v_{1}$ of $V^{\prime}$ such that $U^{\prime}_{\alpha_{i}}\subsetneq U^{\prime}_{\alpha_{i+1}}$ and $G\models E(\alpha_{i},\alpha_{i+1})$ for all $i\in[n-1]$ . In particular, $U_{\alpha_{i}}\subsetneq U_{\alpha_{i+1}}$ and $H\models E(\alpha_{i},\alpha_{i+1})$ for all $i\in[n]$ . As $H$ satisfies $\chi_{3}$ we obtain that $|U_{\alpha_{i+1}}|=|U_{\alpha_{i}}|+1$ for all $i$ . Moreover, since $H$ satisfies $\chi_{2}$ and every element of $U$ is adjacent to $v_{1}$ , we obtain that $U_{\alpha_{1}}=\{u_{6}\}$ and $U_{\alpha_{n}}=U$ . In particular, we deduce that $n=|U|\leq|V^{\prime}|$ . Symmetrically, we obtain some $k\in\mathbb{N}$ and a sequence of elements $\beta_{1}:=u_{1},\beta_{2},\dots,\beta_{k}:=u_{6}$ of $U^{\prime}$ such that $V^{\prime}_{\beta_{i}}\subsetneq V^{\prime}_{\beta_{i+1}}$ and $G\models\neg E(\beta_{i},\beta_{i+1})$ for all $i\in[k-1]$ . Hence, $V_{\beta_{i}}\subsetneq V_{\beta_{i+1}}$ and $H\models\neg E(\beta_{i},\beta_{i+1})$ for all $i\in[k-1]$ . Once again, since $H$ satisfies $\xi_{2}$ , $\xi_{2^{*}}$ , and $\xi_{3}$ we obtain that $V_{\beta_{1}}=\{v_{1}\}$ , $V_{\beta_{n}}=V$ , and $|V_{\beta_{i+1}}|=|V_{\beta_{i}}|+1$ . It thus follows that $k=|V|\leq|U^{\prime}|$ . Putting the above together we have that

|U|\leq|V^{\prime}|\leq|V|\leq|U^{\prime}|\leq|U|.

Consequently, $n=k$ while $V=V^{\prime}=\{\alpha_{1},\dots,\alpha_{n}\}$ and $U=U^{\prime}=\{\beta_{1},\dots,\beta_{n}\}$ as needed. $\hfill\blacktriangleleft$

We now define the intended minimal induced models of our formula $\phi$ .

Definition 4.

For $n\geq 7$ we define the graph $\mathcal{H}_{n}$ with vertex and edge set

V(\mathcal{H}_{n}):=\{v_{1},\dots,v_{n}\}\cup\{u_{1},\dots,u_{n}\}\cup\{a\}% \cup\{b\};

E(\mathcal{H}_{n}):=\{(v_{i},u_{j}):i\leq j\}\cup\{(v_{i},v_{j}):j=i+1\}\cup\{% (u_{i},u_{j}):j\neq i+1\}

\cup\ \{(a,u_{i}):i\geq 2\}\cup\{(b,u_{i}):i\geq n-1\}\cup\{(a,v_{2}),(b,v_{n-% 1})\},

respectively. We also write $\mathcal{I}_{n}$ for the subgraph of $\mathcal{H}_{n}$ induced on the set

V(\mathcal{I}_{n}):=\{v_{1},v_{2},v_{3},v_{n-2},v_{n-1},v_{n},u_{1},u_{2},u_{3% },u_{n-2},u_{n-1},u_{n},a,b\}\subseteq V(\mathcal{H}_{n}).

Figure 2: The graph

\mathcal{H}_{7}

.

We aim to establish that the graphs $\mathcal{H}_{n}$ are all minimal induced models of $\phi$ . Towards this, we first argue that the only embedding of $\mathcal{I}_{n}$ in $\mathcal{H}_{n}$ is the inclusion map. While this lemma is not conceptually difficult, it requires analysing and ruling out different cases corresponding to potential images of the gadget. Its proof may be found in Appendix A.

Lemma 5.

Let $n\geq 7$ and $f:\mathcal{I}_{n}\to\mathcal{H}_{n}$ be an embedding. Then $f$ is the inclusion map.

Proposition 6.

For each $n\geq 7$ the graphs $\mathcal{H}_{n}$ are minimal induced models of $\phi$ .

Proof.

We fix some $n\geq 7$ . We first argue that $\mathcal{H}_{n}\models\phi$ for every $n\geq 7$ . Indeed, we clearly have that

\mathcal{H}_{n}\models I(v_{1},v_{2},v_{3},v_{n-2},v_{n-1},v_{n},u_{1},u_{2},u% _{3},u_{n-2},u_{n-1},u_{n},a,b).

Moreover, the set $U:=\{u_{1},\dots,u_{n}\}\subseteq V(\mathcal{H}_{n})$ is precisely the set of neighbours of $v_{1}$ which are not $v_{2}$ , while the set $V:=\{v_{1},\dots,v_{n}\}\subseteq V(\mathcal{H}_{n})$ is precisely the set of non-neighbours of $v_{1}$ which are not $a$ or $b$ . Evidently, we then have that for every vertex $v_{i}\in V\setminus\{v_{1}\}$ the vertex $v_{i-1}\in V$ is adjacent to $v_{i}$ and its neighbourhood over $U$ strictly contains that of $v_{i}$ . Consequently $\mathcal{H}_{n}\models\phi_{2}(\bar{v},\bar{u},a,b)$ . Likewise, for every vertex $u_{i}\in U\setminus\{u_{n}\}$ the vertex $u_{i+1}\in U$ is non-adjacent to $u_{i}$ and its neighbourhood over $V$ strictly contains that of $u_{i}$ . It follows that $\mathcal{H}_{n}\models\psi_{2}(\bar{v},\bar{u},a,b)$ , and so $\mathcal{H}_{n}\models\phi$ as required.

Now, suppose that $H$ is a proper induced subgraph of $\mathcal{H}_{n}$ , and assume for a contradiction that $H\models\phi$ , i.e. there are vertices $x_{1},\dots,x_{6},y_{1},\dots,y_{6},\alpha,\beta$ of $H$

H\models(I(\bar{x},\bar{y},\alpha,\beta)\land[\phi_{1}(\bar{x},\bar{y},\alpha,% \beta)\land\psi_{1}(\bar{x},\bar{y},\alpha,\beta)\to\phi_{2}(\bar{x},\bar{y},% \alpha,\beta)\land\psi_{2}(\bar{x},\bar{y},\alpha,\beta)]).

Since these vertices induce a copy of $\mathcal{I}_{n}$ , it follows by Lemma 5 that

(x_{1},x_{2},x_{3},x_{4},x_{5},x_{6},y_{1},y_{2},y_{3},y_{4},y_{5},y_{6},% \alpha,\beta)=\\ (v_{1},v_{2},v_{3},v_{n-2},v_{n-1},v_{n},u_{1},u_{2},u_{3},u_{n-2},u_{n-1},u_{% n},a,b),

and so $\mathcal{I}_{n}\leq H\lneq\mathcal{H}_{n}$ . Moreover, letting $U^{\prime}:=U\cap V(H)$ and $V^{\prime}:=V\cap V(H)$ we see that

$\blacksquare$

the elements in $V^{\prime}$ have pairwise comparable neighbourhoods over $U^{\prime}$ , and the elements of $U^{\prime}$ have pairwise comparable neighbourhoods over $V^{\prime}$ ;
$\blacksquare$

the only neighbour of $v_{n}$ in $U^{\prime}$ is $u_{n}$ , and the only neighbour of $u_{1}$ in $V^{\prime}$ is $v_{1}$ ;
$\blacksquare$

$u_{n}$ is adjacent to every element of $V$ ;
$\blacksquare$

if $x,y\in V^{\prime}$ are adjacent and the $U^{\prime}$ -neighbours of $y$ are strictly more than the $U^{\prime}$ -neighbours of $x$ then there is some $i\in[n-1]$ such that $y=v_{i}$ and $x=v_{i+1}$ , and there is a unique vertex in $U^{\prime}$ that is adjacent to $y$ and not adjacent to $x$ , namely $u_{i}$ ;
$\blacksquare$

if $x,y\in U^{\prime}$ are adjacent and the $V^{\prime}$ -neighbours of $y$ are strictly more than the $V^{\prime}$ -neighbours of $x$ then there is some $i\in[n-1]$ such that $y=v_{i+1}$ and $y=v_{i}$ , and there is a unique vertex in $V^{\prime}$ that is adjacent to $y$ and not adjacent to $x$ , namely $v_{i}$ .

It follows that $H\models(\phi_{1}(\bar{v},\bar{u},a,b)\land\psi_{1}(\bar{v},\bar{u},a,b))$ . Since $H\models\phi$ this implies that $H\models(\phi_{2}(\bar{v},\bar{u},a,b)\land\psi_{2}(\bar{v},\bar{u},a,b))$ . However, since $V(H)\subsetneq V(\mathcal{H}_{n})$ , there is some $i\in[4,n-3]$ such that $v_{i}\notin V(H)$ or $u_{i}\notin V(H)$ . Assume the former, and let $i\in[4,n-3]$ be maximal such that $v_{i}\notin V(H)$ . It follows that there is no vertex in $x\in V^{\prime}$ that is adjacent to $v_{i+1}$ and its neighbourhood over $U^{\prime}$ is strictly greater than that of $v_{i+1}$ , contradicting that $H\models\psi_{1}(\bar{v},\bar{u},a,b)$ . By a symmetric argument we obtain a contradiction if $u_{i}\notin V(H)$ , and thus follows that $H\not\models\phi$ . $\hfill\blacktriangleleft$

Theorem 7.

Extension preservation fails on any hereditary graph class containing the graphs $\mathcal{H}_{n}$ for arbitrarily large $n\in\mathbb{N}$ .

Proof.

Let $\mathcal{C}$ be a class of graphs containing the graphs $\mathcal{H}_{n}$ for arbitrarily large $n$ . Since the formula $\phi$ is preserved under extensions over the class of all finite graphs, it is in particular preserved under extensions over $\mathcal{C}$ . Since $\mathcal{C}$ is hereditary and $\phi$ has infinitely many minimal induced models in $\mathcal{C}$ , namely the graphs $\mathcal{H}_{n}$ , it follows by Lemma 2 that $\phi$ is not equivalent to an existential formula over $\mathcal{C}$ . $\hfill\blacktriangleleft$

Finally, we observe that the graphs $\mathcal{H}_{n}$ have bounded cliquewidth, which is easily seen to be at most $4$ . For this, we crucially use the fact that successive pairs are adjacent on one side and non-adjacent on the other. One could simplify the construction, e.g. by using adjacency to denote succession on both sides, but this would slightly increase the cliquewidth.

Observation 8.

The graphs $\mathcal{H}_{n}$ have (linear) cliquewidth $4$ .

Corollary 9.

Extension preservation fails on $\mathcal{CW}_{k}$ for every $k\geq 4$ .

As witnessed by the above, orders appear to provide strong counterexamples to extension preservation. In the next section we explore preservation in certain monadically stable classes, where no such issues are expected to arise.

4 Extension preservation on strongly flip-flat classes

Local information on dense graphs can be as complicated as global information, as for instance is the case with cliques. This fact seemingly renders locality useless in the context of dense graph classes. Nonetheless, our understanding of tame classes indicates that it is still possible to recover meaningful local information, after possibly “sparsifying” our graphs in a controlled manner. The flip operation, which is central to the emerging theory of dense graph classes, plays precisely this role. We introduce it in the following definition.

Definition 10.

Let $G$ be a graph and $k\in\mathbb{N}$ . A $k$ -partition $P$ of $G$ is a partition of the vertex set into $k$ labelled parts $P_{1},\dots,P_{k}$ , i.e. $V(G)=\bigcup_{i\in[k]}P_{i}$ and $P_{i}\cap P_{j}=\emptyset$ for $i\neq j$ . By a $k$ -flip $F$ we denote a symmetric subset of $[k]^{2}$ , i.e. a set of tuples $F=\{(i,j):i,j\in[k]\}$ such that $(i,j)\in F\iff(j,i)\in F$ . Given a $k$ -partition $P$ of $G$ and a $k$ -flip $F$ we define the graph $G\triangle_{F}P$ on the same vertex set as $G$ and on the edge set

E(G\triangle_{F}P):=E(G)\triangle\{(u,v):u\neq v,u\in P_{i},v\in P_{j},\text{ % and }(i,j)\in F\}.

where $\triangle$ denotes the symmetric difference operation.

We note that the notation for flips existing in the literature uses the notation $\oplus$ rather than $\triangle$ (e.g. in [17]); here we have opted for the latter as the symbol $\oplus$ was used in [3] and [14] to denote the amalgamation operation. Moreover, instead of partitioning our graph, we may define $k$ -flips by applying a sequence of at most $k$ atomic operations, each one switching the edges and non-edges between two arbitrary subsets $A, B$ of our vertex set. Evidently, these definitions are equivalent up to blowing up the number of flips by a value that only depends on $k$ , while we have opted for the partition definition here to simplify our construction in Definition 14 below.

Definition 11.

We say that a hereditary class of graphs $\mathcal{C}$ is flip-flat¹¹1The original definition of flip-flatness in [17] is the uniform variant of the definition we have provided here. A simple analysis of the obstructions to monadic stability from [16], reveals that these definitions are equivalent for hereditary classes of graphs. if for every $r\in\mathbb{N}$ there exist $k_{r}\in\mathbb{N}$ and a function $f_{r}:\mathbb{N}\to\mathbb{N}$ satisfying that for every $m\in\mathbb{N}$ and every $G\in\mathcal{C}$ of size at least $f_{r}(m)$ there is a $k_{r}$ -partition $P$ of $G$ , a $k_{r}$ -flip $F\subseteq[k_{r}]^{2}$ , and a set $A\subseteq V(G)$ of size at least $m$ which is $r$ -independent in $G\triangle_{F}P$ . If in the above $k_{r}:=k\in\mathbb{N}$ does not depend on $r$ , then we say that $\mathcal{C}$ is strongly flip-flat.

It was established in [17, Theorem 1.3] that a hereditary class of graphs is flip-flat if, and only if, it is monadically stable. In particular, every transduction of a quasi-wide class is flip-flat. The qualitative difference between strong flip-flatness and flip-flatness is precisely the same as that of almost-wideness and quasi-wideness. We make this idea precise in the following straightforward proposition, which establishes that every transduction of a uniformly almost-wide class is strongly flip-flat. For this, we use the following lemma from [29, Lemma H.3], which follows easily from Gaifman’s locality theorem.

Lemma 12 (Flip transfer lemma, [29]).

There exists a (computable) function $\Xi:\mathbb{N}^{3}\to\mathbb{N}$ satisfying the following. Fix $k,c,q\geq 1$ and $\mathcal{T}_{\delta,\phi}$ a transduction involving $c$ colours and formulas of quantifier rank at most $q$ . Let $G, H$ be graphs such that $H\in T_{\delta,\phi}(G)$ . Then for every $k$ -partition $P$ of $G$ and $k$ -flip $F$ there exists a $\Xi(k,c,q)$ -partition $P_{H}$ of $H$ and a $\Xi(k,c,q)$ -flip $F_{H}$ such that for all $u,v\in V(H)$ :

\mathrm{dist}_{G\triangle_{F}P}(u,v)\leq 2^{q}\cdot\mathrm{dist}_{H\triangle_{% F_{H}}P_{H}}(u,v).

Proposition 13.

Every transduction of a uniformly almost-wide graph class is strongly flip-flat.

Proof.

Let $\mathcal{C}$ be a uniformly almost-wide graph class and fix $k_{\mathcal{C}}\in\mathbb{N}$ witnessing this, so that for every $r,m\in\mathbb{N}$ there is $f_{r}(m)\in\mathbb{N}$ satisfying that every $G$ of size at least $f_{r}(m)$ in the hereditary closure of $\mathcal{C}$ contains an $r$ -independent set of size $m$ after removing at most $k_{\mathcal{C}}$ elements. Let $\mathcal{D}$ a class such that there is a transduction $T_{\delta,\phi}$ satisfying $\mathcal{D}\subseteq T_{\delta,\phi}(\mathcal{C})$ . Let $c\in\mathbb{N}$ be the number of unary predicates used by $T$ , and $q$ be the maximum of the quantifier ranks of $\delta$ and $\phi$ . We argue that $\mathcal{D}$ is strongly flip-flat with $k:=\Xi(2^{k_{\mathcal{C}}},c,q)$ .

Indeed, fix $r,m\in\mathbb{N}$ and a graph $H\in\mathcal{D}$ of size at least $f_{2^{q}\cdot r}(m)$ . It follows that there exists some $G\in\mathcal{C}$ such that $H\in T_{\delta,\phi}(G)$ , and since $f_{2^{q}\cdot r}(m)\leq|V(H)|$ , we obtain by uniform almost-wideness that $G[V(H)]$ contains a $(2^{q}\cdot r)$ -independent set of size $m$ after removing a set of size at most $k_{\mathcal{C}}$ . In particular, there is a $2^{k_{\mathcal{C}}}$ -partition $P$ of $G$ and a $2^{k_{\mathcal{C}}}$ -flip $F$ such that $(G\triangle_{F}P)[V(H)]$ contains an $(2^{q}\cdot r)$ -independent subset of size $m$ ; call this set $A$ . Consequently, Lemma 12 implies that there is a $k$ -partition $P$ of $H$ and a $k$ -flip $F$ such that for all $a,b\in A\subseteq V(H)$

r=\frac{2^{q}\cdot r}{2^{q}}\leq\frac{\mathrm{dist}_{G\triangle_{F}P}(a,b)}{2^% {q}}\leq\mathrm{dist}_{H\triangle_{F_{H}}P_{H}}(a,b),

i.e. $A$ is an $r$ -independent set of size $m$ in $H\triangle_{F_{H}}P_{H}$ . It follows that $\mathcal{D}$ is strongly flip-flat. $\hfill\blacktriangleleft$

In particular, transductions of bounded degree classes, classes of bounded shrub-depth [20], and transductions of proper minor-closed classes [4, Theorem 5.3] are all strongly flip-flat. However, obtaining preservation via locality and wideness in the style of [3, 4, 13, 14] additionally requires subtle closure assumptions. The proofs of the above articles are essentially structured into two parts. The first part argues via locality that for every formula $\phi$ preserved by extensions (or homomorphisms in the case of [4, 13, 14]) over a class $\mathcal{C}$ closed under substructures and disjoint unions there exist $r,m\in\mathbb{N}$ such that no minimal induced model of $\phi$ in $\mathcal{C}$ can contain an $r$ -independent set of size $m$ . In the second part, wideness is used to bound the size of minimal models of $\phi$ , as large enough models would have to contain $r$ -independent sets of size $m$ , under the proviso that a bounded number of bottleneck points have been removed. To account for the removal of these points, we have to work with an adjusted formula $\phi^{\prime}$ in an expanded vocabulary, together with suitably adjusted structures ([2] called these plebian companions) on which we apply the argument of the first part. Working with $\phi^{\prime}$ , however, has translated the requirement of closure under disjoint unions to closure under a more involved operation which depends on the choice of bottlenecks. Consequently, preservation can fail on natural tame classes which do not satisfy this closure condition, e.g. for planar graphs [14, Theorem 5.8].

In the context of vertex deletions, the corresponding operation was amalgamation over bottlenecks [14, Theorem 4.2]. Here, we must formulate a different operation to account for the fact that flips are required to witness wideness. This is precisely the construction below.

Definition 14.

Given $k\in\mathbb{N}$ , a graph $G$ , a $k$ -partition $P$ of $G$ , and a $k$ -flip $F\subseteq[k^{2}]$ we write $G\star_{(F,P)}G$ for the graph whose vertex set $V(G\star_{(F,P)}G):=V(G+G)$ is the same as the disjoint union of two copies of $G$ , and whose edge set is

E(G\star_{(F,P)}G):=E(G+G)\cup\{(u,v):u,v\text{ are in distinct copies of }G,u% \in P_{i},v\in P_{j},(i,j)\in F\}

We call this the flip-sum of $G$ over $(F,P)$ .

Figure 3: The graph

H\star_{(F,P)}H

, where

H

is the half-graph of order

4

,

P

is the partition into red (top) and blue (bottom) vertices and

F=\{(1,2),(2,1)\}

.

We now introduce the relevant translation for the formulas.

Definition 15.

Given a $k$ -flip $F\subseteq[k]^{2}$ , consider the formula

E_{F}(x,y):=E(x,y)\bigtriangleup_{(i,j)\in F}(P_{i}(x)\land P_{j}(y)).

over the signature $\tau_{E}^{k}:=\tau_{E}\cup\{P_{1},\dots,P_{k}\}$ , where $\bigtriangleup_{(i,j)\in F}$ denotes the consecutive application of the $\mathsf{XOR}$ operator over all tuples $(i,j)\in F$ . Given a $\tau_{E}$ -formula $\phi$ , we define the $\tau_{E}^{k}$ -formula $\phi^{k}$ obtained from $\phi$ by replacing every atom $E(x,y)$ with the formula $E_{F}(x,y)$ . Moreover, for every graph $G$ and $k$ -partition $P$ we write $G_{(F,P)}$ for the $\{P_{1},\dots,P_{k}\}$ -expansion of $G\triangle_{F}P$ where each predicate is interpreted by the respective part of $P$ . It is then clear from the definitions and the fact that the flip operation is involutive that

G\models\phi\iff G_{(F,P)}\models\phi^{k}.

Our goal in Theorem 18 is to start with a strongly flip-flat class and a formula $\phi$ and apply the argument of [3, Theorem 4.3] to the formula $\phi^{k}$ and the structures $G_{(F,P)}$ . However, as previously explained, $\phi^{k}$ is not necessarily preserved under embeddings over $\mathcal{C}$ . We can nonetheless use the following easy lemma in case that the class is closed under the desired flip-sums, which will be sufficient for our purposes.

Lemma 16.

Let $\mathcal{C}$ be a hereditary class of graphs and $\phi$ a formula preserved under extensions over $\mathcal{C}$ . Fix a graph $G\in\mathcal{C}$ , a $k$ -partition $P$ of $G$ , and a $k$ -flip $F\subseteq[k]^{2}$ . If $G\star_{(F,P)}G\in\mathcal{C}$ then

G_{(F,P)}\models\phi^{k}\implies G_{(F,P)}+G_{(F,P)}[S]\models\phi^{k}

for any $S\subseteq V(G)$ .

Proof.

Fix $\mathcal{C},\phi,G,P,F$ as in the statement above, and let $S\subseteq V(G)$ . Write $G^{*}$ for the subgraph of $G\star_{(F,P)}G$ induced on the vertex set of $G+G[S]$ ; it follows that $G^{*}\in\mathcal{C}$ by hereditariness. As $G_{(F,P)}\models\phi^{k}$ we obtain that $G\models\phi$ , and since $G^{*}$ contains an induced copy of $G$ and $\phi$ is preserved by extensions over $\mathcal{C}$ it follows that $G^{*}\models\phi$ . Let $P^{*}$ be the natural $k$ -partition of $G^{*}$ inherited from $G$ , i.e. for each $i\in[k]$ the $i$ -th part $P^{*}_{i}$ of $P^{*}$ contains the union of the $i$ -th parts of $G$ and $G[S]$ . It follows from the definitions that the structure $G^{*}_{(F,P^{*})}$ is isomorphic to $G_{(F,P)}+G_{(F,P)}[S]$ . Finally, since $G^{*}\models\phi$ we obtain that $G^{*}_{(F,P^{*})}\models\phi^{k}$ and so $G_{(F,P)}+G_{(F,P)}[S]\models\phi^{k}$ as claimed. $\hfill\blacktriangleleft$

We shall also make use of the following observation, which simply says that the induced substructures of $G_{(F,P)}$ are the same as expansions of flips of induced substructures of $G$ .

Observation 17.

Let $G$ be a graph, $P$ a $k$ -partition of $G$ , and $F$ a $k$ -flip. Then for every $S\subseteq V(G)$ the structure $G_{(F,P)}[S]$ is equal to $G[S]_{(F,P_{S})}$ , where $P_{S}$ is the $k$ -partition of $G[S]$ obtained by restricting each part of $P$ on $S$ .

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

Theorem 18.

Fix a hereditary class of graphs $\mathcal{C}$ . Suppose that there is some $k\in\mathbb{N}$ such that for all $r\in\mathbb{N}$ there is a function $f_{r}:\mathbb{N}\to\mathbb{N}$ satisfying that for every $m\in\mathbb{N}$ and every $G\in\mathcal{C}$ of size at least $f(m)$ there is a $k$ -partition $P$ of $V(G)$ , some $k$ -flip $F$ , and $A\subseteq V(G)$ such that

1.

$|A|\geq m$ ;
2.

$A$ is $r$ -independent in $G\triangle_{F}P$ ;
3.

$G\star_{(F,P)}G\in\mathcal{C}$ .

Then extension preservation holds over $\mathcal{C}$ .

The proof of Theorem 18 is an adaptation of the proof of [3, Theorem 4.3], which established that extension preservation holds over any class closed under weak substructures and disjoint unions which is wide, i.e. for every $r\in\mathbb{N}$ there exists $f_{r}:\mathbb{N}\to\mathbb{N}$ such that for every $m\in\mathbb{N}$ every structure with at least $f_{r}(m)$ -many elements contains an $r$ -independent set of size $m$ . Here, we replace wideness by strong flip-flatness by working with the formula $\phi^{k}$ of Definition 15. Moreover, as previously explained, addability is replaced by assumption 3 above. Preservation is then ensured by Lemma 22. Finally, going from closure under weak substructures to closure under induced substructures follows by analysing [3, Theorem 4.3]. The detailed proof can be found in Appendix B.

Example 19.

For $d\in\mathbb{N}$ , write $\mathcal{D}_{d}$ be the class of all graphs $G$ such that the maximum degree of $G$ is at most $d$ , or the maximum degree of $\overline{G}$ , i.e. the complement graph of $G$ , is at most $d$ . Let $f_{r}(m)=(m-1)(d+1)^{r}+1$ and consider a graph $G\in\mathcal{D}_{d}$ of size at least $f_{r}(m)$ . If $G$ has maximum degree $d$ , then $G$ must contain an $r$ -independent set of size $m$ . Consequently, letting $P=\{V(G)\}$ and $F=\emptyset$ , we see that $G\star_{(F,P)}G$ is simply the disjoint union of two copies of $G$ , which still has maximum degree $d$ and is therefore in $\mathcal{D}_{d}$ . On the other hand if $\overline{G}$ has maximum degree $d$ , then for $P=\{V(G)\}$ and $F=\{(1,1)\}$ , we see that $\bar{G}=G\triangle_{F}P$ has an $r$ -independent set of size $m$ . Since $G\star_{(F,P)}G$ is the complement of the disjoint union of two copies of $\overline{G}$ and so $\overline{G\star_{(F,P)}G}$ has maximum degree $d$ , it follows that ${G\star_{(F,P)}G}\in\mathcal{D}_{d}$ . Consequently, extension preservation holds over $\mathcal{D}_{d}$ by Theorem 18.

As mentioned above, Lemma 2 implies that any well-quasi-ordered class has the extension preservation property. In particular, this applies to classes of bounded shrubdepth [20, Corollary 3.9]. Still, in the following example we indirectly show that the class of all graphs of $\mathcal{SC}$ -depth at most $k$ has extension preservation by showing that it satisfies the requirements of Theorem 18, as an illustration that, although closure under flip-sums is a technical condition, it can be present in interesting tame dense classes.

Definition 20 ([20], Definition 3.5).

We inductively define the class $\mathcal{SC}(k)$ as:

$\blacksquare$

$\mathcal{SC}(0)=\{K_{1}\}$ ;
$\blacksquare$

If $G_{1},\dots,G_{n}\in\mathcal{SC}(k),H:=G_{1}+\dots+G_{n}$ and $X\subseteq V(H)$ , then $\overline{H}^{X}:=H\triangle_{F}P\in\mathcal{SC}(k+1)$ for $P_{1}:=X,P_{2}:=V(H)\setminus X$ and $F=\{(1,1)\}$ , i.e. $\overline{H}^{X}$ is the graph obtained from $H$ by flipping the edges within $X$ .

Example 21.

Fix $k\in\mathbb{N}$ and let $G\in\mathcal{SC}(k)$ . Consider an $\mathcal{SC}$ -decomposition tree of $G$ , i.e. a labelled tree $\mathcal{T}$ of height $k+1$ whose leaves are labelled by the vertices of $G$ , every non-leaf node is labelled by the graph $\overline{(G_{1}+\dots G_{n})}^{X}$ where $G_{i}$ are the labels of its children, $X$ is a subset of $\bigcup_{i\in[n]}V(G_{i})$ , and the root $\rho$ is labelled by $G$ . Let $f(m)=m^{k+1}$ , and suppose that $|G|>f(m)$ . Since $\mathcal{T}$ has height $k+1$ and its leaves correspond to the vertices of $G$ , there must exist some vertex $t$ of $\mathcal{T}$ with at least $m$ children. Let $t_{1}:=\rho,t_{2},\dots,t_{\ell}:=t$ be the unique path from the root of $\mathcal{T}$ to $t$ , and for each $i\in[\ell]$ let $X_{i}\subseteq V(G)$ be the set coming from the label of $t_{i}$ . Letting $P$ the partition of $V(G)$ into $2^{\ell}$ parts depending on the membership of a vertex within each of $X_{1},\dots,X_{\ell}$ and $F\subseteq[2^{\ell}]^{2}$ be the flip that corresponds to complementing each of $X_{1},\dots,X_{\ell}$ , it follows that $G\triangle_{F}P$ contains at least $m$ distinct connected components. Let $\mathcal{T}^{\prime}$ be the tree obtained from $\mathcal{T}$ by the following operation. We first create a copy of each subtree of $\mathcal{T}$ rooted at a child of $t_{\ell}$ and connect them to $t_{\ell}$ . The labels are naturally carried from each original subtree to the copy. If the label of $t_{\ell}$ in $\mathcal{T}$ was $\overline{(G_{1}+\dots+G_{m})}^{X}$ , then its label in $\mathcal{T}^{\prime}$ is $\overline{(G_{1}+G^{\prime}_{1}+\dots+G_{m}+G_{m}^{\prime})}^{X\cup X^{\prime}}$ where each $G_{i}^{\prime}$ corresponds to the copy of $G_{i}$ , and $X^{\prime}$ corresponds to the set of copies of the vertices in $X$ . From there, we perform the same operation for $i=\ell-1,\dots,1$ , this time copying only the children of $t_{i}$ that are not $t_{i+1}$ . This completes the construction of $\mathcal{T}^{\prime}$ . It is easy to then see than the root of $\mathcal{T}^{\prime}$ corresponds to the graph $G\star_{(F,P)}G$ , thus witnessing that $G\star_{(F,P)}G\in\mathcal{SC}(k)$ . It follows that the class $\mathcal{SC}(k)$ satisfies the requirements of Theorem 18, and thus extension preservation holds over this class.

5 Conclusion

We conclude with some questions and remarks. Firstly, it would be of independent interest to provide a characterisation of strongly flip-flat classes, akin to the characterisation of almost-wide classes via shallow minors given in [24, Theorem 3.21]. This could either be a characterisation via excluded induced subgraphs occurring in flips, in analogy to the one of monadic stability provided in [15], or in terms of shallow vertex minors, in analogy to the one in [8].

Moreover, it is unclear whether one can produce a formula preserved by extensions with minimal induced models of cliquewidth $3$ . The issue with interweaving definable orders is that one simultaneously requires for two sets to semi-induce a half-graph while (non-)adjacency is used to mark successors; this requires to keep track of at least four colours classes in a clique decomposition. We therefore leave the question of whether extension preservation holds over graphs of cliquewidth $3$ open. It is also easily seen that the structures $\mathcal{H}_{n}$ have twin-width $2$ (see [6] for definitions). The status of extension preservation on the class of all graphs of twin-width $1$ is also unknown.

The role of orders was crucial in our construction in Section 3. In the context of undirected graphs, orders are instantiated through half-graphs. It natural to then inquire if, for every fixed $k,\ell\in\mathbb{N}$ , the class of all graphs of cliquewidth at most $k$ which omit semi-induced half-graphs of size larger than $\ell$ has the extension preservation property. Every such class is known to be equal to a transduction of a class of bounded treewidth by [26], and so by Proposition 13, it is strongly flip-flat. It would therefore be interesting to provide a direct combinatorial argument witnessing this, so as to be able to verify if such classes satisfy the closure requirements of Theorem 18.

References

[1] Hans Adler and Isolde Adler. Interpreting nowhere dense graph classes as a classical notion of model theory. European Journal of Combinatorics, 36:322–330, 2014. doi:10.1016/j.ejc.2013.06.048.
[2] Miklos Ajtai and Yuri Gurevich. Datalog vs first-order logic. Journal of Computer and System Sciences, 49(3):562–588, 1994. 30th IEEE Conference on Foundations of Computer Science. doi:10.1016/S0022-0000(05)80071-6.
[3] Albert Atserias, Anuj Dawar, and Martin Grohe. Preservation under extensions on well-behaved finite structures. SIAM Journal on Computing, 38(4):1364–1381, 2008. doi:10.1137/060658709.
[4] Albert Atserias, Anuj Dawar, and Phokion G Kolaitis. On preservation under homomorphisms and unions of conjunctive queries. Journal of the ACM (JACM), 53(2):208–237, 2006. doi:10.1145/1131342.1131344.
[5] John T Baldwin and Saharon Shelah. Second-order quantifiers and the complexity of theories. Notre Dame Journal of Formal Logic, 26(3):229–303, 1985. doi:10.1305/NDJFL/1093870870.
[6] Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width I: tractable fo model checking. ACM Journal of the ACM (JACM), 69(1):1–46, 2021. doi:10.1145/3486655.
[7] Samuel Braunfeld, Anuj Dawar, Ioannis Eleftheriadis, and Aris Papadopoulos. Monadic nip in monotone classes of relational structures. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023.
[8] Hector Buffière, Eun Jung Kim, and Patrice Ossona de Mendez. Shallow vertex minors, stability, and dependence. arXiv preprint arXiv:2405.00408, 2024.
[9] Bruno Courcelle and Stephan Olariu. Upper bounds to the clique width of graphs. Discrete Applied Mathematics, 101(1):77–114, 2000. doi:10.1016/S0166-218X(99)00184-5.
[10] Konrad K. Dabrowski, Matthew Johnson, and Daniël Paulusma. Clique-width for hereditary graph classes, pages 1–56. London Mathematical Society Lecture Note Series. Cambridge University Press, 2019. doi:10.1017/9781108649094.002.
[11] Peter Damaschke. Induced subgraphs and well-quasi-ordering. Journal of Graph Theory, 14(4):427–435, 1990. doi:10.1002/JGT.3190140406.
[12] Anuj Dawar. Finite model theory on tame classes of structures. In International Symposium on Mathematical Foundations of Computer Science, pages 2–12. Springer, 2007. doi:10.1007/978-3-540-74456-6_2.
[13] Anuj Dawar. Homomorphism preservation on quasi-wide classes. Journal of Computer and System Sciences, 76(5):324–332, 2010. doi:10.1016/J.JCSS.2009.10.005.
[14] Anuj Dawar and Ioannis Eleftheriadis. Preservation theorems on sparse classes revisited. arXiv preprint arXiv:2405.10887, 2024. doi:10.48550/arXiv.2405.10887.
[15] Jan Dreier, Ioannis Eleftheriadis, Nikolas Mählmann, Rose McCarty, Michał Pilipczuk, and Szymon Toruńczyk. First-order model checking on monadically stable graph classes. arXiv preprint arXiv:2311.18740, 2023.
[16] Jan Dreier, Nikolas Mählmann, and Sebastian Siebertz. First-order model checking on structurally sparse graph classes. In STOC 2023, pages 567–580. ACM, 2023. doi:10.1145/3564246.3585186.
[17] Jan Dreier, Nikolas Mählmann, Sebastian Siebertz, and Szymon Toruńczyk. Indiscernibles and Flatness in Monadically Stable and Monadically NIP Classes. In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), volume 261 of Leibniz International Proceedings in Informatics (LIPIcs), pages 125:1–125:18, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2023.125.
[18] Jan Dreier, Nikolas Mählmann, and Szymon Toruńczyk. Flip-breakability: A combinatorial dichotomy for monadically dependent graph classes. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1550–1560, 2024. doi:10.1145/3618260.3649739.
[19] H-D. Ebbinghaus and J. Flum. Finite Model Theory. Springer, 2nd edition, 1999.
[20] Robert Ganian, Petr Hliněnỳ, Jaroslav Nešetřil, Jan Obdržálek, and Patrice Ossona De Mendez. Shrub-depth: Capturing height of dense graphs. Logical Methods in Computer Science, 15, 2019.
[21] Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs. J. ACM, 64(3), June 2017. doi:10.1145/3051095.
[22] Yuri Gurevich. Toward logic tailored for computational complexity. Computation and Proof Theory, pages 175–216, 1984.
[23] Ulrich Knauer and Kolja Knauer. Algebraic Graph Theory: Morphisms, Monoids and Matrices. De Gruyter, Berlin, Boston, 2019. doi:doi:10.1515/9783110617368.
[24] Jaroslav Nešetřil and Patrice Ossona De Mendez. First order properties on nowhere dense structures. The Journal of Symbolic Logic, 75(3):868–887, 2010. URL: http://www.jstor.org/stable/20799288, doi:10.2178/JSL/1278682204.
[25] Jaroslav Nešetřil and Patrice Ossona De Mendez. Sparsity: graphs, structures, and algorithms, volume 28. Springer Science & Business Media, 2012.
[26] Jaroslav Nešetřil, Patrice Ossona de Mendez, Michał Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. Rankwidth meets stability. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2014–2033. SIAM, 2021.
[27] Benjamin Rossman. Homomorphism preservation theorems. Journal of the ACM (JACM), 55(3):1–53, 2008. doi:10.1145/1379759.1379763.
[28] W. W. Tait. A counterexample to a conjecture of Scott and Suppes. Journal of Symbolic Logic, 24(1):15–16, 1959. doi:10.2307/2964569.
[29] Szymon Toruńczyk. Flip-width: Cops and robber on dense graphs. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 663–700. IEEE, 2023.

Appendix A The proof of Lemma 5

Here we provide a proof of Lemma 5, which we now restate.

See 5

This is achieved in two steps. First, we consider the subgraph $\mathcal{I}^{\prime}$ of $\mathcal{H}_{n}$ induced on $\{v_{1},v_{2},v_{3},u_{1},u_{2},u_{3},a\}$ . Evidently, the map $g_{n}:\mathcal{I}^{\prime}\to\mathcal{H}_{n}$ sending

(v_{1},v_{2},v_{3},u_{1},u_{2},u_{3},a)\mapsto(v_{n-2},v_{n-1},v_{n},u_{n-2},u% _{n-1},u_{n},b)

is an embedding. We argue that this is the only non-trivial embedding of $\mathcal{I}^{\prime}$ in $\mathcal{H}_{n}$ .

Lemma 22.

Let $n\geq 7$ and $f:\mathcal{I}^{\prime}\to\mathcal{H}_{n}$ be an embedding. Then $f$ is either the inclusion map or equal to $g_{n}$ .

Proof.

As before, we write $V:=\{v_{1},\dots,v_{n}\}\subseteq V(\mathcal{H}_{n})$ and $U:=\{u_{1},\dots,u_{n}\}\subseteq V(\mathcal{H}_{n})$ . We shall consider the possible images of the vertex $v_{2}$ . Suppose that $f(v_{2})=u_{i}$ for some $i\in[n]$ . Clearly, since the vertices $v_{1},v_{3},a$ are pairwise non-adjacent, we cannot have $f[\{v_{1},v_{3},a\}]\subseteq U$ . We hence distinguish cases.

1.

Suppose that $v_{1},v_{3},a$ are all mapped to vertices in $V$ under $f$ . Since these are non-adjacent, we must have $f[\{v_{1},v_{3},a\}]=\{v_{m},v_{r},v_{\ell}\}$ for some $m+2<r+1<\ell\leq i$ . Now, consider $f(u_{1})$ ; this must be some vertex in $\mathcal{H}_{n}$ which is adjacent to only one of $v_{m},v_{r},v_{\ell}$ and not adjacent to $u_{i}$ . This necessarily implies that $f(u_{1})=v_{i+1}$ , $f(v_{1})=v_{\ell}$ while $\ell=i$ . Consider $f(u_{2})$ ; this must be a vertex non-adjacent to $v_{i+1}$ , and adjacent to $u_{i},v_{i}$ and exactly one of $\{v_{m},v_{r}\}$ . From this we deduce that $f(u_{2})=v_{i-1}$ , $f(a)=v_{r}$ , and $r=i-2$ . Finally, the vertex $f(u_{3})$ must be adjacent to $v_{m},v_{i-2},v_{i},u_{i},v_{i+1}$ and non-adjacent to $v_{i-1}$ ; obviously no such vertex exists in $\mathcal{H}_{n}$ , and we thus obtain a contradiction.
2.

Suppose that two of $v_{1},v_{3},a$ are mapped to vertices in $V$ and one is mapped to a vertex in $U$ . In this case we must have that $f[\{v_{1},v_{3},a\}]=\{u_{m},v_{r},v_{\ell}\}$ for some $m+1<r+1<\ell\leq i$ . Consider $f(u_{1})$ ; this must be non-adjacent to $v_{i}$ and adjacent to exactly one of $u_{m},v_{r},v_{\ell}$ . This further results in two distinct cases. If $f(u_{1})=v_{i+1}$ , then we have $f(v_{1})=v_{\ell}$ and $\ell=i$ , which leads to a contradiction with an analogous argument to the above. If $f(u_{1})=u_{i-1}$ , then necessarily $f(v_{1})=v_{r}$ while $m=i-2,r=i-1,\ell=i$ . Considering $f(u_{2})$ , we now see that this vertex must be non-adjacent to $u_{i-1}$ and adjacent to $u_{i},v_{i-1}$ and exactly one of $\{u_{i-2},v_{i}\}$ ; evidently there is no such vertex in $\mathcal{H}_{n}$ and we thus obtain a contradiction.
3.

Suppose that exactly one of $v_{1},v_{3},a$ is mapped to a vertex in $V$ and two are mapped to vertices of $U$ . This forces that $f[\{v_{1},v_{3},a\}]=\{u_{m-1},u_{m},v_{\ell}\}$ for some $m<\ell\leq i$ and $m+1<i$ . Again, consider $f(u_{1})$ ; this is non-adjacent to $u_{i}$ and adjacent to exactly one of $\{u_{m},u_{m+1},v_{\ell}\}$ . Once again this leads to two options. If $f(u_{1})=v_{i+1}$ , then we have $f(v_{1})=v_{\ell}$ and $\ell=i$ , which leads to a contradiction as in Case $1$ . On the other hand, if $f(u_{1})=u_{i-1}$ then we necessarily obtain that $f(v_{1})=u_{m-1}$ while $m=i-2$ and $\ell=i$ . The vertex $f(u_{2})\in\mathcal{H}_{n}$ must then be non-adjacent to $u_{i-1}$ and adjacent to $u_{i-1},u_{i}$ and exactly one of $u_{i-2},v_{i}$ ; since there is no such vertex in $\mathcal{H}_{n}$ we once again obtain a contradiction.
4.

Suppose that one of $v_{1},v_{3},a$ is mapped to $a$ or $b$ under $f$ . Since $u_{3}$ is adjacent to all of $v_{1},v_{2},v_{3},a$ it must necessarily be that $f(u_{3})=u_{m}$ for some $m>i+1$ . The vertex $f(u_{2})$ must then be non-adjacent to $u_{m}$ , and adjacent to $u_{i}$ and exactly two of $f(v_{1}),f(v_{3}),f(a)$ . As no such vertex exists in this case, we obtain a contradiction.

Since the above cases lead to a contradiction, we see that $f(v_{2})\notin U$ . Since no $v_{i}$ for $i\in[n]\setminus\{2,n-1\}$ has three neighbours which induce an independent set, this necessarily implies that $f(v_{2})$ is equal to $v_{2}$ or $v_{n-1}$ . Assume that $f(v_{2})=v_{2}$ . Again, since $v_{1},v_{3},a$ share no edges, we must necessarily have $f[\{v_{1},v_{3},a\}]=\{v_{1},v_{3},a\}$ . Since $u_{3}$ is adjacent to all of $v_{1},v_{2},v_{3},a$ we see that $f(u_{3})=u_{m}$ for some $m\geq 3$ . As $u_{2}$ is non-adjacent to $u_{3}$ and adjacent to $v_{2}$ to exactly two of $v_{1},v_{3},a$ , we see that $f(u_{3})=u_{3}$ and $f(u_{2})=u_{2}$ , which in turn ensure that $f$ is the inclusion map. By similar reasoning, we deduce that if $f(v_{2})$ is equal to $v_{n-1}$ then $f=g_{n}$ as required. $\hfill\blacktriangleleft$

Proof of Lemma 5.

Let $f:\mathcal{I}_{n}\to\mathcal{H}_{n}$ be an embedding. It follows by Lemma 22 that either $f$ is the inclusion map, or it is the map given by swapping the two induced copies of $\mathcal{I}^{\prime}$ , i.e. the map

(v_{1},v_{2},v_{3},u_{1},u_{2},u_{3},a)\mapsto(v_{n-2},v_{n-1},v_{n},u_{n-2},u% _{n-1},u_{n},b);

(v_{n-2},v_{n-1},v_{n},u_{n-2},u_{n-1},u_{n},b)\mapsto(v_{1},v_{2},v_{3},u_{1}% ,u_{2},u_{3},a).

Since $u_{n-2}$ is adjacent to $v_{2}$ , the latter case would imply that $u_{1}$ is adjacent to $v_{n-1}$ , which is a contradiction. Hence, $f$ is the inclusion map as claimed. $\hfill\blacktriangleleft$

Appendix B The proof of Theorem 18

Before proceeding with Theorem 18 we introduce some relevant definitions. Fix a relational signature $\tau$ and $q,d\in\mathbb{N}$ , and let $A$ be a $\tau$ -structure. By the $(q,d)$ -type of some $a\in A$ we shall mean the set containing all the $\mathsf{MSO}$ formulas $\theta(x)$ of quantifier rank²²2Here both first-order and second-order quantifiers contribute to the quantifier rank. at most $q$ , up to logical equivalence, such that $N_{d}^{A}(a)\models\theta(a)$ . When we speak of a $(q,d)$ -type $t$ over $\tau$ , without reference to a particular element in a structure, we shall mean a $(q,d)$ -type of some element in some $\tau$ -structure. We say that an element $a\in A$ realises a $(q,d)$ -type $t$ whenever $N_{d}^{A}(a)\models\theta(a)$ for all $\theta(x)\in t$ . Evidently, the number of $(q,d)$ -types is bounded by some $p\in\mathbb{N}$ depending only on $\tau$ and $q$ . Given a $\tau$ -structure $A$ , a set $C\subseteq A$ , and a $(q,d)$ -type $t$ , we say that $t$ is covered by $C$ in $A$ if all $a\in A$ realising $t$ satisfy $N_{d}^{A}(a)\subseteq C$ . For $n\in\mathbb{N}$ we also say that $t$ is $n$ -free over $C$ in $A$ if there is a $2d$ -independent set $S\subseteq A$ of size $n$ such that each $a\in S$ realises $t$ and $N_{d}^{A}(a)\cap C=\emptyset$ .

Lemma 23.

Fix a relational signature $\tau$ and $q,d\in\mathbb{N}$ . Let $p$ be the number of $(q,d)$ -types over $\tau$ . Then for every $\tau$ -structure $A$ and $n\in\mathbb{N}$ , there exists a radius $e\leq 2dp$ and a set $D\subseteq A$ of at most $(n-1)p$ points such that each $(q,d)$ -type is either covered by $N_{e}^{A}(D)$ or is $n$ -free over over $N_{e}^{A}(D)$ .

Proof.

Fix an enumeration $t_{1},\dots,t_{p}$ of all $(q,d)$ -types over $\tau$ . We shall define $D$ and $e$ inductively starting at $D_{0}=\emptyset$ and $e_{0}=0$ . Assuming $D_{i}$ and $e_{i}$ have been defined, we let $C=N_{e_{i}}^{A}(D_{i})$ . If all types are covered by $C$ or are $n$ -free over $C$ then we are done; otherwise, we let $j\in[p]$ be minimal such that $t_{j}$ is neither covered by $C$ nor $n$ -free over $C$ . We then define a set $E\subseteq A$ inductively, starting with $E_{0}:=\emptyset$ and at step $\ell+1$ adding to $E_{\ell}$ a realisation $a\in A\setminus N_{2d}^{A}(C\cup E_{\ell})$ of $t_{j}$ if there exists one; this iteration must stop within $n-1$ steps, as otherwise $t_{j}$ would be $n$ -free over $C$ . In particular, $|E|\leq n-1$ and $t_{j}$ is covered by $N_{e_{i}+2d}^{A}(D_{i}\cup E)$ . We subsequently let $D_{i+1}=D_{i}\cup E$ and $e_{i+1}=e_{i}+2d$ . It follows that the construction must stop within at most $p$ steps, since at each step we cover a previously uncovered type, which in addition, remains covered for the rest of the construction. Consequently, $|D|\leq(n-1)p$ and $e\leq 2dp$ as claimed. $\hfill\blacktriangleleft$

See 18

Proof.

Fix $\mathcal{C}$ as above, and let $\phi$ be a formula preserved by extensions overs $\mathcal{C}$ . We shall obtain a bound on the size of the minimal induced models of $\phi$ , by arguing that any large enough model of $\phi$ contains a proper induced substructure which also models $\phi$ . We can then conclude that $\phi$ is equivalent to an existential formula over $\mathcal{C}$ using Lemma 2.

Letting $k\in\mathbb{N}$ be as the in the statement of Theorem 18, we consider the formula $\phi^{k}$ from Definition 15. Using Gaifman’s locality theorem we rewrite $\phi^{k}$ into a boolean combination of basic local sentences, i.e. we may assume that there is some $\ell\in\mathbb{N}$ and $\tau_{E}^{k}$ -sentences $\psi_{i}$ for $i\in[\ell]$ such that

\phi^{k}=\bigvee_{i\in\ell}\psi_{i}\text{ and }\psi_{i}=\bigwedge_{j\in A_{i}}% \chi_{ij}\land\bigwedge_{j\in B_{i}}\neg\chi_{ij},

where each $\chi_{ij}$ is a basic local sentence. We henceforth fix the following constants:

$\blacksquare$

$\rho$ is the maximum over all the locality radii of the $\chi_{ij}$ ;
$\blacksquare$

$s$ is the sum of all widths of the $\chi_{ij}$ ;
$\blacksquare$

$\gamma$ is the maximum over all the quantifier ranks of the $\chi_{ij}$ ;
$\blacksquare$

$q:=\gamma+3\rho+3$ ;
$\blacksquare$

$d:=2(\rho+1)(\ell+1)s+6\rho+2$ ;
$\blacksquare$

$p$ is the number of $(q,d)$ -types over the signature $\tau_{E}^{k}$ ;
$\blacksquare$

$n:=(\ell+2)s$ ;
$\blacksquare$

$m:=(n-1)q+s+\ell s+1$ ;
$\blacksquare$

$r:=4dp+2\rho+1$ .

Our goal is to establish that any minimal induced model of $\phi$ in $\mathcal{C}$ must have size less than $f_{r}(m)$ , where $f$ is as in the statement of Theorem 18. So, assume that some $G\models\phi$ has size at least $f_{r}(m)$ . It follows by assumption that there is a $k$ -partition $P$ and a $k$ -flip $F$ such that $G\triangle_{F}P$ contains an $r$ -independent set of size $m$ . We henceforth work with the structure $G^{*}:=G_{(F,P)}$ , i.e. the expansion of $G\triangle_{F}P$ with unary predicates corresponding to the parts of $P$ . By definition, we have that $G^{*}\models\phi^{k}$ .

By Lemma 23 we obtain a radius $e\leq 2dp$ and a set $D\subseteq V(G^{*})$ of at most $(n-1)p$ vertices such that each $(q,d)$ -type in $G^{*}$ is either covered by $N_{e}^{G^{*}}(D)$ or is $n$ -free over $N_{e}^{G^{*}}(D)$ ; we henceforth refer to types of the former kind as rare, and to types of the latter kind as frequent.

We proceed to inductively construct increasing sequences of sets $S_{0}\subseteq S_{1}\subseteq\dots\subseteq V(G^{*})$ , $C_{0}\subseteq C_{1}\subseteq\dots\subseteq V(G^{*})$ , and $I_{0}\subseteq I_{1}\subseteq\dots\subseteq I$ which satisfy the following conditions for every $i$ :

1.

$S_{i}\subseteq N_{\rho}^{G^{*}}(C_{i})$ ;
2.

$|C_{i}|\leq is$ ;
3.

$|I_{i}|=i$ ;
4.

no disjoint extension of $G^{*}[S_{i}]$ satisfies $\bigvee_{j\in I_{i}}\psi_{j}$ ;
5.

$N_{e}^{G^{*}}(D)$ and $N_{d}^{G^{*}}(C_{i})$ are disjoint.

Clearly, this construction must terminate within $\ell$ steps. Indeed, assume for a contradiction that we have constructed $S_{\ell},C_{\ell},$ and $I_{\ell}$ satisfying conditions 1-5 above. If so, then $I_{\ell}=I$ while $G^{*}+G^{*}[S_{\ell}]$ is a disjoint extension of $G^{*}[S_{\ell}]$ which satisfies $\phi^{k}=\bigvee_{i\in I}\psi_{i}$ by Lemma 16, therefore contradicting condition 4. At the end of the construction we will obtain some $N<\ell$ and some $S_{N}\subsetneq V(G^{*})$ satisfying $G^{*}[S_{N}]\models\phi^{k}$ . Combining Definition 15 with 17, this will imply that $G[S_{N}]\models\phi$ , and hence that $G$ cannot be a minimal model of $\phi$ as required.

Initially, we set $S_{0}=C_{0}=I_{0}=\emptyset$ . Assume that $S_{i},C_{i},$ and $I_{i}$ have been defined. Write $H^{*}:=G^{*}+G^{*}[S_{i}]$ for the disjoint union of $G^{*}$ with its substructure induced on $S_{i}$ . By our closure assumptions on $\mathcal{C}$ and Lemma 16 we deduce that $H^{*}\models\phi^{k}$ . In particular, there exists some $i^{\prime}\in I$ such that $H^{*}\models\psi_{i^{\prime}}$ , while $i^{\prime}\notin I_{i}$ due to property 4. We let $I_{i+1}=I_{i}\cup\{i^{\prime}\}$ and henceforth drop the reference to the index $i^{\prime}$ as it will remain fixed for the remaining of the argument, e.g. by writing $\psi$ and $\chi_{j}$ instead of $\psi_{i^{\prime}}$ and $\chi_{i^{\prime}j}$ respectively.

As $H^{*}$ satisfies $\psi=(\bigwedge_{j\in A}\chi_{j}\land\bigwedge_{j\in B}\neg\chi_{j})$ , it satisfies the basic local sentences $\chi_{j}$ with $j\in A$ . For each $j\in A$ , we may thus choose a minimal set $W_{j}\subseteq V(H^{*})$ of witnesses for the outermost existential quantifiers of the basic local sentence $\chi_{j}$ , and let $W:=\bigcup_{j\in A}W_{j}$ be their union. As $s$ is the sum of the widths of all the $\chi$ ’s it follows that $|W|\leq s$ . We partition $W$ into those witnesses that appear in the disjoint copy of $G^{*}$ , and those that appear in the disjoint copy of $G^{*}[S_{i}]$ , and write $W_{G}$ and $W_{H}$ for these respective parts.

Now, suppose that some $v\in W_{G}$ satisfies $N_{\rho+1}^{G^{*}}(C_{i})\cap N_{\rho}^{G^{*}}(v)\neq\emptyset$ ; we argue that we may replace $v$ with some witness $v^{\prime}\in V(G^{*})$ such that $N_{\rho+1}^{G^{*}}(C_{i})\cap N_{\rho}^{G^{*}}(v^{\prime})=\emptyset$ . Indeed, we first choose some $u\in C_{i}$ such that $N_{\rho+1}^{G^{*}}(u)\cap N_{\rho}^{G^{*}}(v)\neq\emptyset$ . Consequently, we have that $N_{\rho}^{G^{*}}(v)\subseteq N_{3\rho+1}^{G^{*}}(u)\subseteq N_{d}^{G^{*}}(u)$ . Property 5 then ensures that the $(q,d)$ -type $t$ (in $G^{*}$ ) of $u$ is frequent, and so it has $n>(\ell+1)s\geq|W\cup C_{i}|$ realisations whose $d$ -neighbourhoods are pairwise disjoint and disjoint from $N_{e}^{G^{*}}(D)$ . We may thus pick a realisation $u^{\prime}\in V(G^{*})$ of $t$ such that $N_{\rho+1}^{G^{*}}(W\cup C_{i})\cap N_{3\rho+1}^{G^{*}}(u^{\prime})=\emptyset$ . Let $\tau$ be the $(\gamma,\rho)$ -type of $v$ , and consider the formula

\theta(x):=\exists y[\forall z(\mathrm{dist}(y,z)\leq\rho\to\mathrm{dist}(x,z)% \leq 3\rho+1)\land\bigwedge_{\eta\in\tau}\eta^{N_{r}(y)}(y)].

Clearly, the quantifier rank of $\theta$ is bounded by $3\rho+3+\gamma\leq q$ , while $N_{d}^{G^{*}}(u)\models\theta(u)$ with $v$ serving as the existential witness. Consequently $\theta(x)$ is in $t$ , and as $u$ and $u^{\prime}$ have the same $(q,d)$ -type, it follows that $N_{d}^{G^{*}}(u^{\prime})\models\theta(u^{\prime})$ . It follows that there is $v^{\prime}\in V(G^{*})$ such that $N_{\rho}^{G^{*}}(v^{\prime})\subseteq N_{3\rho+1}^{G^{*}}(u^{\prime})\subseteq N% _{d}^{G^{*}}(u^{\prime})$ , while $v$ and $v^{\prime}$ have the same $(\gamma,\rho)$ -type. In particular, their $\rho$ -neighbourhoods satisfy the same $\mathsf{FO}$ -formulas of quantifier rank $\leq\gamma$ . Finally, observe that $N_{\rho+1}^{G^{*}}(W\cup C_{i})\cap N_{3\rho+1}^{G^{*}}(v^{\prime})=\emptyset$ and so $N_{\rho+1}^{G^{*}}(C_{i})\cap N_{\rho}^{G^{*}}(v^{\prime})=\emptyset$ ; we may thus replace $v$ by $v^{\prime}$ in $W_{G}$ as a witness.

After replacing all such witnesses in _G, we can ensure that

|\{v\in W_{G}:N_{\rho+1}^{G^{*}}(C_{i})\cap N_{\rho}^{G^{*}}(v)\neq\emptyset\}% |=0

Consider the induced substructure $U^{*}:=G^{*}[N_{e}^{G^{*}}(D)\cup N_{\rho}^{G^{*}}(W_{G})\cup S_{i}]$ . We claim that $U^{*}$ satisfies $\bigwedge_{j\in A}\chi_{j}$ . Indeed, notice that $S_{i}\subseteq N_{\rho}^{G^{*}}(C_{i})$ , while $N_{\rho+1}^{G^{*}}(C_{i})$ is disjoint from $N_{e}^{G^{*}}(D)$ by property 5 and disjoint from $N_{\rho}^{G^{*}}(W_{G})$ by $(\star)$ . It follows that $U^{*}$ is the disjoint union of $G^{*}[N_{e}^{G^{*}}(D)\cup N_{\rho}^{G^{*}}(W_{G})]$ and $G^{*}[S_{i}]$ ; thus all the witnesses from $W$ and their $\rho$ -neighbourhoods can be found in $U^{*}$ , implying that $U^{*}\models\chi_{j}$ for all $j\in A$ as these are basic local sentences.

Now, observe that $U^{*}$ is a proper induced substructure of $G^{*}$ . This is because

|D\cup W_{G}\cup C_{i}|\leq(n-1)p+s+\ell s<m;

N_{e}^{G^{*}}(D)\cup N_{\rho}^{G^{*}}(W_{G})\cup S_{i}\subseteq N_{2dp+\rho}^{% G^{*}}(D\cup W_{G}\cup C_{i})\subseteq N_{\left\lfloor{r/2}\right\rfloor}^{G^{% *}}(D\cup W_{G}\cup C_{i}),

and so, unlike $G^{*}$ , $U^{*}$ does not contain an $r$ -independent set of size $m$ . Consequently, if $U^{*}\models\phi^{k}$ then we set $S_{N}:=N_{e}^{G^{*}}(D)\cup N_{\rho}^{G^{*}}(W_{G})\cup S_{i}$ and our construction terminates.

We hereafter assume that $U^{*}\not\models\phi^{k}$ , and proceed with the definition of $S_{i+1}$ and $C_{i+1}$ . Since $U^{*}\models\bigwedge_{j\in A}\chi_{j}$ it must be that $U^{*}\not\models\bigwedge_{j\in B}\neg\chi_{j}$ . We can therefore fix some $j\in B$ such that $U^{*}\models\chi_{j}$ . Suppose that

\chi_{j}=\exists x_{1},\dots,\exists x_{s^{\prime}}[\bigwedge_{a\neq b}\mathrm% {dist}(x_{a},x_{b})>2\rho^{\prime}\land\bigwedge_{a}\xi^{N_{\rho^{\prime}}(x_{% a})}(x_{a})]

for some $\rho^{\prime}\leq\rho$ , $s^{\prime}\leq s$ , and a formula $\xi$ of quantifier rank $\gamma^{\prime}\leq\gamma$ . Fix a set $V=\{w_{1},\dots,w_{s^{\prime}}\}\subseteq U^{*}$ of witnesses for the outermost existential quantifier of $\chi_{j}$ . Notice that if the $(q,d)$ -type in $G^{*}$ of every $w\in V$ was rare then $N_{\rho^{\prime}}^{G^{*}}(V)\subseteq N_{e}^{G^{*}}(D)\subseteq V(G^{*})$ , implying that $G^{*}\models\chi_{j}$ and thus $H^{*}\models\chi_{j}$ as $H^{*}$ is a disjoint extension of $G^{*}$ and $\chi_{j}$ is a basic local sentence. We can thus fix some $w\in V$ whose $(q,d)$ -type in $G^{*}$ , say $t_{w}$ , is frequent. As a result, there is a set $Z\subseteq V(G^{*})$ of $n$ realisations of $t_{w}$ whose $d$ -neighbourhoods are pairwise disjoint and disjoint from $N_{e}^{G^{*}}(D)$ . Now, since $4\rho+3\leq d$ , $n=(\ell+2)s$ , and $|C_{i}|\leq\ell s$ , there exists a subset $Z^{\prime}\subseteq Z$ of at least $s$ elements which additionally satisfies $N_{\rho+1}^{G^{*}}(C_{i})\cap N_{\rho}^{G^{*}}(Z^{\prime})=\emptyset$ .

Consider $F:=N_{\rho^{\prime}}^{U^{*}}(w)$ . Evidently, $U^{*}[F]=G^{*}[F]$ and so $G^{*}[F]\models\xi^{N_{\rho^{\prime}}(x)}(w)$ . For a set variable $X$ consider the formula $\xi^{N_{\rho^{\prime}}(x)\cap X}(x,X)$ obtained from $\xi$ by simultaneously relativising the quantifiers of $\xi$ to the $r^{\prime}$ -neighbourhoods of $x$ and to the set $X$ . Observe that the quantifier rank of $\xi^{N_{\rho^{\prime}}(x)\cap X}(x,X)$ is at most $\gamma^{\prime}+\rho^{\prime}<q$ , and moreover $G^{*}\models\xi^{N_{\rho^{\prime}}(x)\cap X}(w,F)$ . Since $\rho^{\prime}<d$ it follows that the $\mathsf{MSO}$ formula $\exists X\xi^{N_{\rho^{\prime}}(x)\cap X}(x,X)$ is in $t_{w}$ . As every $\omega\in Z^{\prime}$ has the same $(q,d)$ -type in $G^{*}$ as $w$ , we may find sets $F_{\omega}\subseteq N_{\rho^{\prime}}^{G^{*}}(\omega)$ for every $\omega\in Z^{\prime}$ such that $G^{*}\models\xi^{N_{\rho^{\prime}}(x)\cap X}(\omega,F_{\omega})$ . In particular, this implies that $G^{*}[F_{\omega}]\models\xi^{N_{\rho^{\prime}}(x)}(\omega)$ . We finally let:

C_{i+1}=C_{i}\cup Z^{\prime};\quad S_{i+1}=S_{i}\cup\bigcup_{\omega\in Z^{% \prime}}F_{\omega}.

We argue that these satisfy the properties 1-5. First, observe that $|C_{i+1}|=|C_{i}|+s\leq is+s=(i+1)s$ . Moreover, as $F_{\omega}\subseteq N_{\rho^{\prime}}^{G^{*}}(\omega)$ , $\omega\in C_{i+1}$ , and $\rho^{\prime}\leq\rho$ we have $S_{i+1}\subseteq N_{\rho}^{G^{*}}(C_{i+1})$ . By the fact that every $\omega\in Z^{\prime}$ realises a frequent type we also have that $N_{e}^{G^{*}}(D)\cap N_{d}^{G^{*}}(C_{i+1})=\emptyset$ . It remains to argue that no disjoint extension of $G^{*}[S_{i+1}]$ satisfies $\bigvee_{j\in I_{i+1}}\psi_{j}$ .

Towards this, we note that $G^{*}[S_{i+1}]$ is a disjoint extension of $G^{*}[S_{i}]$ by the fact that $S_{i}\subseteq N_{\rho}^{G^{*}}(C_{i})$ and $N_{\rho+1}^{G^{*}}(C_{i})\cap N_{\rho}^{G^{*}}(Z^{\prime})=\emptyset$ . Therefore, no disjoint extension of $G^{*}[S_{i+1}]$ satisfies $\psi_{j}$ for $j\in I_{i}$ . At the same time, every disjoint extension of $G^{*}[S_{i+1}]$ contains witnesses for the outermost existential quantifiers of $\chi_{i^{\prime}j}$ , namely the elements $\omega\in Z^{\prime}$ , which are pairwise at distance at least $2d>2\rho^{\prime}$ and satisfy $G^{*}[F_{\omega}]\models\xi^{N_{\rho^{\prime}}(x)}(\omega)$ and $N_{\rho^{\prime}}^{G^{*}[S_{i+1}]}(\omega)=F_{\omega}$ , and thus $G^{*}[S_{i+1}]\models\xi^{N_{\rho^{\prime}}(x)}(\omega)$ . It follows that every disjoint extension of $G^{*}[S_{i+1}]$ satisfies $\chi_{i^{\prime}j}$ , and so it cannot satisfy $\psi_{i^{\prime}}$ as needed. This complete our inductive construction of $S_{i+1},C_{i+1}$ , and $I_{i+1}$ . $\hfill\blacktriangleleft$

[bib.bib1] [1] Hans Adler and Isolde Adler. Interpreting nowhere dense graph classes as a classical notion of model theory. European Journal of Combinatorics, 36:322–330, 2014. doi:10.1016/j.ejc.2013.06.048.

[bib.bib2] [2] Miklos Ajtai and Yuri Gurevich. Datalog vs first-order logic. Journal of Computer and System Sciences, 49(3):562–588, 1994. 30th IEEE Conference on Foundations of Computer Science. doi:10.1016/S0022-0000(05)80071-6.

[bib.bib3] [3] Albert Atserias, Anuj Dawar, and Martin Grohe. Preservation under extensions on well-behaved finite structures. SIAM Journal on Computing, 38(4):1364–1381, 2008. doi:10.1137/060658709.

[bib.bib4] [4] Albert Atserias, Anuj Dawar, and Phokion G Kolaitis. On preservation under homomorphisms and unions of conjunctive queries. Journal of the ACM (JACM), 53(2):208–237, 2006. doi:10.1145/1131342.1131344.

[bib.bib5] [5] John T Baldwin and Saharon Shelah. Second-order quantifiers and the complexity of theories. Notre Dame Journal of Formal Logic, 26(3):229–303, 1985. doi:10.1305/NDJFL/1093870870.

[bib.bib6] [6] Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width I: tractable fo model checking. ACM Journal of the ACM (JACM), 69(1):1–46, 2021. doi:10.1145/3486655.

[bib.bib7] [7] Samuel Braunfeld, Anuj Dawar, Ioannis Eleftheriadis, and Aris Papadopoulos. Monadic nip in monotone classes of relational structures. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023.

[bib.bib8] [8] Hector Buffière, Eun Jung Kim, and Patrice Ossona de Mendez. Shallow vertex minors, stability, and dependence. arXiv preprint arXiv:2405.00408, 2024.

[bib.bib9] [9] Bruno Courcelle and Stephan Olariu. Upper bounds to the clique width of graphs. Discrete Applied Mathematics, 101(1):77–114, 2000. doi:10.1016/S0166-218X(99)00184-5.

[bib.bib10] [10] Konrad K. Dabrowski, Matthew Johnson, and Daniël Paulusma. Clique-width for hereditary graph classes, pages 1–56. London Mathematical Society Lecture Note Series. Cambridge University Press, 2019. doi:10.1017/9781108649094.002.

[bib.bib11] [11] Peter Damaschke. Induced subgraphs and well-quasi-ordering. Journal of Graph Theory, 14(4):427–435, 1990. doi:10.1002/JGT.3190140406.

[bib.bib12] [12] Anuj Dawar. Finite model theory on tame classes of structures. In International Symposium on Mathematical Foundations of Computer Science, pages 2–12. Springer, 2007. doi:10.1007/978-3-540-74456-6_2.

[bib.bib13] [13] Anuj Dawar. Homomorphism preservation on quasi-wide classes. Journal of Computer and System Sciences, 76(5):324–332, 2010. doi:10.1016/J.JCSS.2009.10.005.

[bib.bib14] [14] Anuj Dawar and Ioannis Eleftheriadis. Preservation theorems on sparse classes revisited. arXiv preprint arXiv:2405.10887, 2024. doi:10.48550/arXiv.2405.10887.

[bib.bib15] [15] Jan Dreier, Ioannis Eleftheriadis, Nikolas Mählmann, Rose McCarty, Michał Pilipczuk, and Szymon Toruńczyk. First-order model checking on monadically stable graph classes. arXiv preprint arXiv:2311.18740, 2023.

[bib.bib16] [16] Jan Dreier, Nikolas Mählmann, and Sebastian Siebertz. First-order model checking on structurally sparse graph classes. In STOC 2023, pages 567–580. ACM, 2023. doi:10.1145/3564246.3585186.

[bib.bib17] [17] Jan Dreier, Nikolas Mählmann, Sebastian Siebertz, and Szymon Toruńczyk. Indiscernibles and Flatness in Monadically Stable and Monadically NIP Classes. In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), volume 261 of Leibniz International Proceedings in Informatics (LIPIcs), pages 125:1–125:18, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2023.125.

[bib.bib18] [18] Jan Dreier, Nikolas Mählmann, and Szymon Toruńczyk. Flip-breakability: A combinatorial dichotomy for monadically dependent graph classes. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1550–1560, 2024. doi:10.1145/3618260.3649739.

[bib.bib19] [19] H-D. Ebbinghaus and J. Flum. Finite Model Theory. Springer, 2nd edition, 1999.

[bib.bib20] [20] Robert Ganian, Petr Hliněnỳ, Jaroslav Nešetřil, Jan Obdržálek, and Patrice Ossona De Mendez. Shrub-depth: Capturing height of dense graphs. Logical Methods in Computer Science, 15, 2019.

[bib.bib21] [21] Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs. J. ACM, 64(3), June 2017. doi:10.1145/3051095.

[bib.bib22] [22] Yuri Gurevich. Toward logic tailored for computational complexity. Computation and Proof Theory, pages 175–216, 1984.

[bib.bib23] [23] Ulrich Knauer and Kolja Knauer. Algebraic Graph Theory: Morphisms, Monoids and Matrices. De Gruyter, Berlin, Boston, 2019. doi:doi:10.1515/9783110617368.

[bib.bib24] [24] Jaroslav Nešetřil and Patrice Ossona De Mendez. First order properties on nowhere dense structures. The Journal of Symbolic Logic, 75(3):868–887, 2010. URL: http://www.jstor.org/stable/20799288, doi:10.2178/JSL/1278682204.

[bib.bib25] [25] Jaroslav Nešetřil and Patrice Ossona De Mendez. Sparsity: graphs, structures, and algorithms, volume 28. Springer Science & Business Media, 2012.

[bib.bib26] [26] Jaroslav Nešetřil, Patrice Ossona de Mendez, Michał Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. Rankwidth meets stability. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2014–2033. SIAM, 2021.

[bib.bib27] [27] Benjamin Rossman. Homomorphism preservation theorems. Journal of the ACM (JACM), 55(3):1–53, 2008. doi:10.1145/1379759.1379763.

[bib.bib28] [28] W. W. Tait. A counterexample to a conjecture of Scott and Suppes. Journal of Symbolic Logic, 24(1):15–16, 1959. doi:10.2307/2964569.

[bib.bib29] [29] Szymon Toruńczyk. Flip-width: Cops and robber on dense graphs. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 663–700. IEEE, 2023.