Weakly-Sparse and Strongly Flip-Flat Classes of Graphs Are Uniformly Almost-Wide

When Trakhtenbrot showed that the set of first-order formulas (FO formulas for short) that are valid on finite structures is co-recursively enumerable, but not recursively enumerable, a beam of light was shed on the curious inversion of finite structures and infinite structures; as the same set is recursively enumerable (Gödel’s completeness), but not co-recursively enumerable (Church’s theorem) on structures. This gave birth to finite model theory [21] and boosted the motivation to show its differences with the world of infinites. Some classical results, such as the compactness theorem, almost immediately broke down; some, like the Löwenheim-Skolem theorem, became meaningless; and some remained valid in finite structures, such as Ehrenfeuchet-Fraïssé games. Moreover, many results were discovered to be native of finites and not hold in the infinites such as Fagin showing that on finites structures ${\mathrm{\Sigma }}_1^1=\mathrm{𝖭𝖯}$ [6].

A category of theorems from classical model theory are preservation theorems. They describe the relation between syntactic and semantic properties of first-order formulas. Łoś-Tarski, Lyndon’s positivity and Homomorphism preservation theorem are examples of preservation theorems [29]. The Łoś-Tarski theorem, also known as extension preservation theorem, which asserts that a first-order formula is preserved under embeddings between all structures if and only if it is equivalent to an existential formula, was shown to fail in the finite from early on [38]. On the contrary, Rossman showed that the homomorphism preservation theorem asserting that a formula is preserved by homomorphisms if and only if it is existential-positive, holds on finite structures [2]. Before Rossman, Atserias et al. attempted to show positive results regarding both extension and homomorphism preservation by further restricting finite structures to tame classes defined by sparsity conditions (with additional closure conditions) [4, 5, 12, 11], and the notions such as wideness, quasi-wideness, almost-wideness and their uniform versions were introduced for that purposes.

These notions proved to be useful in other contexts. Informally, a class of graphs $𝒞$ is said quasi-wide if, for every integer $r$ and in any large enough graph $G$ from $𝒞$, we can find a small set of vertices $S$ and a large enough set $B\subseteq V(G)\setminus S$ such that any two vertices in $B$ are at distance at least $r+1$ in $G\setminus S$, i.e., the induced graph on $V(G)\setminus S$. Being uniformly quasi-wide, means that the above statement is true not only for any large enough graph, but also for their large enough subgraphs. The well-known notion of nowhere dense classes of graphs are characterised to be exactly the uniformly quasi-wide classes of graphs [33], and this characterisation lies at the heart of another combinatorial characterisation of nowhere dense classes of graphs through the notion of splitter game, which helped proving that FO model checking on nowhere dense classes of graphs is fixed parameter tractable [27].

It is therefore natural to ask for which other graph classes such characterisations or algorithmic results can be obtained, and there is a large effort from the finite model theory and algorithmic/structural graph theory communities to push them to hereditary dense structures (see for instance [19, 23, 16, 39] to cite a few). With this aim, the well-studied model-theoretic notion of monadic stability beautifully manifested itself.

The concept of monadic stability was introduced by Baldwin and Shelah [7], and was mainly studied within model theory and in connection with Shelah’s classification theory [37]. Their work provides an understanding of the structure of monadically stable classes from the model-theoretic perspective. However, describing their combinatorial properties has started only recently. Immediately after, the two combinatorial characterisations of monadically stable graph classes through the notions of flip-flatness [18] and the flipper game [24], came handy in proving that FO-model checking is fixed parameter tractable on monadically stable classes of graphs [17, 16]. Informally, flip-flatness means that in a big enough graph we can perform a certain number of flips, that is flipping the adjacency between a pair of subsets of vertices, such that in the final structure, there exists a large enough set of vertices that are pairwise far away. When the number of flips is independent from the distance between the far-away subset of vertices and only depends on the class, we call the class strongly flip-flat. Recently, Eleftheriadis extended the result on extension preservation theorem to a restriction of the strongly flip-flat classes of graphs [22].

We recall Eleftheriadis’ theorem after explaining the notation. If $G$ is a graph and $F=(A,B)$ is a pair of subsets of vertices of $G$, the flip of $G$ on $F$, denoted by $G\oplus F$, is the graph obtained from $G$ by flipping the edges between vertices in $A$ and vertices in $B$, where $A$ and $B$ can have non-empty intersection. Flipping edges between $A$ and $B$ means replacing every edge by a non-edge and every non-edge by an edge. One can check that $G\oplus F\oplus F^{\prime }=G\oplus F^{\prime }\oplus F$. A family $ℱ$ of $k$ pairs of subsets of vertices is called a $k$-flip in $G$, and for a $k$-flip $ℱ:=\{F_1,\mathrm{\dots },F_k\}$ in $G$, we denote by $G\oplus ℱ$ the graph $G\oplus F_1\oplus F_2\oplus \mathrm{\cdots }\oplus F_k$, and by $G{\star }_{ℱ}G$ the graph $G^{\prime }\oplus {ℱ}^{\prime }$ where $G^{\prime }$ is the disjoint union of two copies $G_1$ and $G_2$ of $G$ and ${ℱ}^{\prime }=\{(A_1,B_2)\mid (A,B)\in ℱ,A_1\text{(resp. }{B}_2\text{)}$ the copy of $A\text{(resp. }B\text{)}$ in $G_1\text{(resp. }{G}_2\text{)}\}$.

The first two conditions are imposing strong flip-flatness and the third condition is a closure condition which does not naturally hold. While it is evident that strongly flip-flat classes of graphs are a subset of flip-flat graph classes, a clear characterisation is still needed.

We initiate a characterisation of strongly flip-flat graph classes by looking at their intersection with weakly sparse classes of graphs, i.e., classes of graphs that exclude some biclique. The reason we believe this is a good starting point is that, for many classes of dense graphs, their intersection with weakly sparse classes of graphs has been observed to be well-behaved classes of graphs, and as such examples we can cite:

• $\mathrm{■}$

  Bounded shrubdepth $\cap$ Weakly sparse $=$ Bounded treedepth [14] (see also the discussion of [25]),

• $\mathrm{■}$

  Bounded clique-width $\cap$ Weakly sparse $=$ Bounded tree-width [10, Theorem 5.9(4)],

• $\mathrm{■}$

  Bounded linear clique-width $\cap$ Weakly sparse $=$ Bounded path-width [28]. In [28] Gurski and Wanke only state the result for graphs of bounded clique-width, which is an improvement on the bound given in [10, Theorem 5.9(4)]. However, they indeed prove that one can construct a tree decomposition from a given clique-width expression (equivalently NLC-width expression), while keeping the shape of the expression. Hence, when the expression has the form of a path, i.e., linear clique-width is bounded, the resulting tree will look like a path, i.e., path-width is bounded.

• $\mathrm{■}$

  Monadically stable $\cap$ Weakly sparse $=$ Nowhere dense [20, 36, 3]

• $\mathrm{■}$

  Monadically dependent $\cap$ Weakly sparse $=$ Nowhere dense [20] (see also [34]), and

• $\mathrm{■}$

  Bounded flip-width $\cap$ Weakly sparse $=$ Bounded expansion [39].

Hence, following this line of research, we prove the following.

FO-transductions are a way of constructing new classes of graphs from a given class $𝒞$ by the means of FO formulas. Basically, we have the power to colour the vertices of the graphs arbitrarily, but with a constant number of colours, and then change the vertex and edge set as the given FO formulas dictates. These formulas can use the colours. When a class $𝒞$ has property $𝒫$, for any FO-transduction of $𝒞$, we say that it is structurally $𝒫$. For example, it has been shown that structurally nowhere dense classes of graphs are monadically stable and hence flip-flat [36, 3, 18]. On the other hand, it is shown that, for some weakly sparse classes of graphs, their FO-transductions are exactly some well-known, yet dense classes of graphs. As a prominent example, it is proven that structurally bounded tree-depth classes of graphs are exactly bounded shrubdepth classes of graphs [26]. In addition to this, Eleftheriadis also showed that in the setting of hereditary classes of graphs, transductions of uniformly almost-wide classes of graphs are strongly flip-flat [22]. Therefore, we conjecture the following, supported by the sparsification conjecture stating that monadically stable graph classes are exactly the structurally nowhere dense classes of graphs.

We believe our main theorem is a step towards proving the conjecture, and allow us to confirm it on structurally bounded expansion graph classes. Nešetřil and Ossona De Mendez showed that for a hereditary class of graphs $𝒞$, if there are $s\in \mathbb{N}$ and a function $t:\mathbb{N}\to \mathbb{N}$ such that, for every $r\in \mathbb{N}$, the graphs in the depth-$r$ shallow minor of $𝒞$ exclude $K_{s,t(r)}$, then $𝒞$ is uniformly almost-wide [33]. As second point supporting the conjecture, we also argue that there exist infinitely many $s\in \mathbb{N}$ such that, for every $r\in \mathbb{N}$, the $r$-subdivisions of $K_{s,N}$, for arbitrary large $N$, cannot be strongly flip-flat and we leave open the question of using them to characterise strongly flip-flat graph classes using shallow vertex-minors [9].

After completing our work, we became aware of independent results by Mählmann [31, Lemma 13.10], which establish a statement closely related to ours. In that work, Mählmann proves that weakly sparse and flip-flat classes of graphs are uniformly quasi-wide. Since flip-flatness characterizes monadic stability, and uniform quasi-wideness characterizes nowhere denseness, this result mirrors a corollary of [20, 35], which shows that monadically stable and weakly sparse classes of graphs are nowhere dense. While our main results differ, ours concern strong flip-flatness, whereas Mählmann focuses on flip-flatness, the proofs are similar in spirit. Our approach, however, introduces a novel point of view: an induction on the set of flips instead of the usual induction on the independence radius. We believe this perspective brings new insights and contributes meaningfully to the ongoing research in this area.

For two sets $A$ and $B$, we denote by $A\setminus B$ the set $\{x\in A\mid x\notin B\}$ and by $A\mathrm{\Delta }B$ the set $(A\setminus B)\cup (B\setminus A)$. The set of positive integers is denoted by $\mathbb{N}$.

We assume familiarity with standard graph theoretical notions, and refer to [8, 15], and deal only with undirected graphs¹¹1One can extend the results to directed graphs by using a coding of directed graphs, through an invertible FO-transduction, into bipartite undirected graphs.. The vertex set of a graph $G$ is denoted by $V(G)$ and its edge set by $E(G)$. An edge between $u$ and $v$ in a graph $G$ is denoted by $uv$ (equivalently $vu$). We recall that, in a graph $G$, a path between two vertices $u$ and $v$ in $V(G)$ is a sequence of vertices $u=w_1,\mathrm{\cdots },w_l=v$ such that $w_i\ne w_j$, for all , and, for all , we have that $w_i{w}_{i+1}\in E(G)$; we say that the length of this path is $l-1$; we often denote such a path by $v-u$ when we are not interested in the internal vertices of the path. The distance between a pair of vertices is the length of the shortest path between them. For a subset $S$ of $V(G)$, we denote by $G[S]$ the subgraph of $G$ induced by $S$, i.e., $V(G[S])=S$ and $E(G[S])=(S\times S)\cap E(G)$; by $G\setminus S$ we mean the subgraph of $G$ induced by $V(G)\setminus S$. We say that a set $B\subseteq V(G)$ is $r$-independent in $G$ if, for all pairs $u,v\in B$, the distance between $u$ and $v$ in $G$ is strictly greater than $r$. By $K_t$ and $K_{t,t}$, we denote the complete graph on $t$ vertices and the complete bipartite graph with $t$ vertices in each part, respectively. A half-graph of order $n$ is a bipartite graph with sides $\{a_1,\mathrm{\cdots },a_n\}$ and $\{b_1,\mathrm{\cdots },b_n\}$ such that, for all $1⩽i,j⩽n$, $a_i$ and $b_j$ are adjacent if and only if $i⩽j$. Half-graphs are graph theoretical representations of linear orders. For an integer $r$, the $r$-subdivision of a graph $G$ is the graph obtained from $G$ by replacing each edge $uv$ of $G$ by a path $u-v$ of length at most $r+1$ that intersects $V(G)$ only on its endpoints.

We are ready to state and prove the main result.

We start with the following lemma.

A corollary of our main theorem is the confirmation of Conjecture 2 on strongly flip-flat graph classes that have structurally bounded expansion, partly answering the characterisation question raised in [22]. It seems however that there is still a long way to completely characterise strongly flip-flat classes of graphs. A confirmation of our conjecture 2 will give a characterisation of strongly flip-flat graph classes as its reverse has been proved (Proposition 11).

In order to prove Conjecture 2, we must find a nowhere dense preimage for any class $𝒞$ of strongly flip-flat graph classes and then argue that this preimage itself is strongly flip-flat, i.e., equivalent of saying that it is almost-wide. This might be as hard as the sparsification conjecture [13], stated below.

A first step towards Conjecture 2 is probably assuming that the sparsification conjecture is true, and then prove the following, that we state as a conjecture.

Our conjecture may not be the easiest way to characterise strongly flip-flat graph classes. One can, for instance, look into forbidden induced subgraphs. In the following we give an example of a nowhere dense class of graphs that is not strongly flip-flat. We denote by $G^s$ the $s$-subdivision of a graph $G$.