Existential Positive Transductions of Sparse Graphs

Nikolas Mählmann, Sebastian Siebertz · 2026

Read Existential Positive Transductions of Sparse Graphs by Nikolas Mählmann, Sebastian Siebertz (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-15890.txt.

Introduction

Nikolas Mählmann and Sebastian Siebertz work on logical encodings of sparse graphs in a 2026 arXiv paper. Monadic stability is a tameness notion in structural graph theory. It generalizes planarity, bounded degree, bounded tree-width, and nowhere density. The sparsification conjecture makes a bold prediction. It says the tame, possibly dense graph classes are exactly those encodable by first-order transductions of sparse nowhere dense classes. The authors study existential positive transductions of sparse graphs.

Transductions are logic-driven ways to build one graph class from another. Existential positive ones use a restricted, monotone logic. Results here test the conjecture's edges. Structural graph theory feeds algorithm design for huge networks. Knowing which dense classes hide sparse codes helps transfer fast algorithms to them.

Catalog record

CREATORNikolas Mählmann, Sebastian Siebertz
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE123 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-15890

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Existential Positive Transductions of Sparse Graphs Thanks: NM received funding from the European Research Council (ERC) with grant agreement No. 101126229 – buka . Nikolas Mählmann, Sebastian Siebertz Abstract Monadic stability generalizes many tameness notions from structural graph theory such as planarity, bounded degree, bounded tree-width, and nowhere density. The sparsification conjecture predicts that the (possibly dense) monadically stable graph classes are exactly those that can be logically encoded by first-order (FO) transductions in the (always sparse) nowhere dense classes. So far this conjecture has been verified for several special cases, such as for classes of bounded shrub-depth, and for the monadically stable fragments of bounded (linear) clique-width, twin-width, and merge-width. In this work we propose the existential positive sparsification conjecture , predicting that the more restricted co-matching-free, monadically stable classes are exactly those that can be transduced from nowhere dense classes using only existential positive FO formulas. While the general conjecture remains open, we verify its truth for all known special cases of the original conjecture. Even stronger, we find the sparse preimages as subgraphs of the dense input graphs. As a key ingredient, we introduce a new combinatorial operation, called subflip , that arises as the natural co-matching-free analog of the flip operation, which is a central tool in the characterization of monadic stability. Using subflips, we characterize the co-matching-free fragment of monadic stability by appropriate strengthenings of the known flip-flatness and flipper game characterizations for monadic stability. In an attempt to generalize our results to the more expressive MSO logic, we discover (rediscover?) that on relational structures (existential) positive MSO has the same expressive power as (existential) positive FO. 1 Introduction First-order transductions have emerged as a fundamental tool in structural graph theory and finite model theory, providing a convenient way to encode one class of structures inside another using logic. Informally, a transduction \mathsf{T}_{\varphi} is an operation specified by a binary first-order formula \varphi(x,y) over the signature of colored graphs. It maps an input graph G to the set \mathsf{T}_{\varphi}(G) containing every graph H that can be obtained through the following three-step process. (See Fig. 1 for an example.) 1. G \rightarrow G^{\prime} : color G with vertex colors appearing in \varphi . 2. G^{\prime} \rightarrow H^{\prime} : let \varphi define a new edge relation: uv\in E(H^{\prime})\Leftrightarrow G^{\prime}\models\varphi(u,v) . 3. H^{\prime} \rightarrow H : choose H to be any induced subgraph of H^{\prime} and remove the vertex colors. Figure 1: Example of a transduction. On the very left: the graph G . On the very right: a graph H\in\mathsf{T}_{\varphi}(G) for the formula \varphi(x,y)=(\textnormal{dist}(x,y)=3)\vee(\textnormal{Red}(x)\wedge\textnormal{Red}(y)) . Further graph transformations that can be expressed by transductions include the complement and the square operation, specified by the formulas \neg E(x,y) , and E(x,y)\vee\exists z\,\big(E(x,z)\wedge E(z,y)\big) , respectively. This motivates the study of properties of graph classes that are preserved under transductions. A popular example of such a transduction-closed class property is bounded clique-width: for every graph class \mathscr{C} whose clique-width is bounded by a constant and every transduction \mathsf{T} , the clique-width of the class \mathsf{T}(\mathscr{C}):=\bigcup_{G\in\mathscr{C}}\mathsf{T}(G) is again bounded by a (possibly larger) constant. For every class \mathscr{D}\subseteq\mathsf{T}(\mathscr{C}) , we say that \mathscr{D} is a transduction of \mathscr{C} , and that \mathscr{C} transduces \mathscr{D} . Further examples of transduction-closed class properties include bounded shrub-depth, bounded linear clique-width, bounded twin-width, and bounded merge-width. Subsuming all previous examples, the most general non-trivial, transduction-closed class property is monadic dependence : a class is monadically dependent if it does not transduce the class of all graphs. In this paper we study the relationship between three fragments of monadic dependence: 1. the biclique-free ( weakly sparse ) fragment, 2. the semi-ladder-free fragment, and 3. the half-graph-free ( stable ) fragment. Definition 1.1 . We call a bipartite graph G on vertices a_{1},\ldots,a_{n} and b_{1},\ldots,b_{n} • the biclique K_{n,n} of order n , if a_{i}b_{j}\in E(G) for all i,j\in[n] , • the half-graph of order n , if a_{i}b_{j}\in E(G)\Leftrightarrow i\leqslant j for all i,j\in[n] , and • the co-matching of order n , if a_{i}b_{j}\in E(G)\Leftrightarrow i\neq j for all i,j\in[n] . A bipartite graph H is a semi-induced subgraph of a graph G , if there are A,B\subseteq V(G) such that the bipartite subgraph of G induced between the sides A and B is isomorphic to H . A graph class is biclique-free / half-graph-free / co-matching-free if it does not contain arbitrarily large bicliques / half-graphs / co-matchings as semi-induced subgraphs. The class is semi-ladder-free if it is both half-graph-free and co-matching-free. See Figure 2 for an illustration. Figure 2: A hierarchy of properties of graph classes. An arrow P_{1}\rightarrow P_{2} between two properties means that every graph class that has property P_{1} also has property P_{2} . The biclique-free fragment of monadic dependence (also called the weakly sparse fragment) consists exactly of the nowhere dense classes. The notion of nowhere density is the main object of study in sparsity theory initiated by Nešetřil and Ossona de Mendez [ 27 ] . It generalizes many tameness notions for sparse graphs such as planarity, bounded tree-width, excluded minors, bounded degree, and bounded expansion. The equivalence of the combinatorial notion of nowhere density and the logical notion of monadic dependence in the biclique-free setting is one of the key results that initially connected sparsity theory and model theory. It follows from the results of Podewski and Ziegler [ 34 ] , Adler and Adler [ 1 ] , and Dvořák [ 15 ] . Generalizing nowhere density, the half-graph-free fragment of monadic dependence consists exactly of the monadically stable classes [ 28 ] , which are those that do not transduce the class of all half-graphs [ 2 ] . While nowhere density is limited to sparse classes, monadic stability also includes dense classes like map graphs and every class of bounded shrub-depth. Monadic stability is transduction-closed and hence, every transduction of a nowhere dense class is monadically stable. The sparsification conjecture predicts an even stronger link between the biclique-free and the half-graph-free fragments of monadic dependence, asserting that the reverse should hold as well. Conjecture 1.2 (see [ 31 ] ) . For every graph class \mathscr{C} the following are equivalent. 1. \mathscr{C} is monadically stable. 2. \mathscr{C} is a transduction of a nowhere dense class. So far the sparsification conjecture has been confirmed for all half-graph-free classes \mathscr{C} that have bounded shrub-depth [ 21 , 20 ] , linear clique-width [ 30 ] , clique-width [ 28 ] , twin-width [ 19 ] , or merge-width [ 9 ] . In each of these cases actually something stronger holds. For example, every half-graph free class of bounded clique-width can be transduced from a class that is not only nowhere dense, but even has bounded tree-width [ 28 ] (which is the same as having both bounded clique-width and being biclique-free [ 6 , 22 ] ). This suggests the following refinement of 1.2 . Conjecture 1.3 . Let \mathcal{P} be a non-trivial and transduction-closed class property. For every graph class \mathscr{C} , the following are equivalent. 1. \mathscr{C} is a half-graph-free class with \mathcal{P} . 2. \mathscr{C} is a transduction of a biclique-free class with \mathcal{P} . Note that this conjecture implies the

Read the complete text