Flipping and Forking
Wojciech Przybyszewski, Szymon Toruńczyk · 2025
Read Flipping and Forking by Wojciech Przybyszewski, Szymon Toruńczyk (2025) 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-2505-16745.txt.
Introduction
Wojciech Przybyszewski and Szymon Toruńczyk tie a graph act called flipping to a deep logic term: forking. Two tame traits, monadic stability and monadic dependence, come from Shelah's grand sort plan. They now sit at the heart of algorithm work. Checks of first-order claims run fast on stable graph sets. The same is thought to hold for the wider, dependent sets.
The pair set out flips and flip independence for all linked data forms, not just graphs. Known marks of stable graph sets lift to that broad stage. In stable forms, flip independence turns out to be the same as forking independence over models. That gives forking its first mark in pure graph terms. Sharp forms come next, for graphs and for forms whose Gaifman graph is sparse in a strong sense. Logic and algorithms gain a shared word list.
Catalog record
| CREATOR | Wojciech Przybyszewski, Szymon Toruńczyk |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 210 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-16745
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Flipping and Forking Wojciech Przybyszewski, Szymon Toruńczyk Abstract Monadic stability and the more general monadic dependence (or NIP) are tameness conditions for classes of logical structures, studied in the 80’s in Shelah’s classification program in model theory. They recently emerged in algorithmic and structural graph theory and finite model theory as central notions in relation with the model checking problem for first-order logic: the problem was shown to be fixed-parameter tractable for inputs which come from a fixed class of graphs which is monadically stable, and is conjectured to be tractable in all monadically dependent classes. Several combinatorial characterizations of such graph classes turned out to be essential in their algorithmic treatment; they are all based on the fundamental operation of “flipping” a graph. We introduce the notions of flips and flip independence in arbitrary relational structures. We lift prior combinatorial characterizations of monadically stable graph classes to monadically stable classes of relational structures. We show the equivalence of flip independence with forking independence (over models) – a logical notion of paramount importance in stability theory – in monadically stable structures, shedding new light on the relevance of flips, also characterizing forking independence (over models) combinatorially. We give more precise descriptions of forking independence in the case of monadically stable graphs, and relational structures with a nowhere dense Gaifman graph. University of Warsaw, Warsaw, Poland and https://www.mimuw.edu.pl/~przybyszewski/ [email protected]://orcid.org/0000-0003-1158-9925 University of Warsaw, Warsaw, Poland and https://www.mimuw.edu.pl/~szymtor/ [email protected]://orcid.org/0000-0002-1130-9033 We are grateful to Joanna Fijalkow for many valuable discussions on flips of relational structures. keywords structural graph theory, model theory, finite model theory, monadic stability, forking independence † † runningauthor: W. Przybyszewski and S. Toruńczyk † † copyright: Wojciech Przybyszewski and Szymon Toruńczyk † † funding: \flag [40px]logo-erc \flag [40px]logo-eu.pngWP was supported by project bobr that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant No 948057). ST was supported by ERC project buka (grant No 101126229). † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction Over the past two decades, the following problem has attracted significant attention in the areas of finite and algorithmic model theory, and algorithmic graph theory [ 24 , Section 8] : Characterize those classes of structures for which the model checking problem for first-order logic is fixed-parameter tractable. For a fixed class {\mathcal{C}} of structures, the model-checking problem for first-order logic is the problem of deciding whether a given structure \mathbf{A}\in{\mathcal{C}} satisfies a given first-order sentence \varphi . The problem is fixed-parameter tractable if it can be solved in time polynomial in the size of \mathbf{A} , where the degree of the polynomial does not depend on \varphi . If such an algorithm for the class {\mathcal{C}} exists, we call {\mathcal{C}} tractable for brevity. Most of the focus in the area has been on graph classes, allowing to leverage tools emerging from structural graph theory. Tractable graph classes include the class of planar graphs, graph classes of bounded treewidth or clique-width, proper minor-closed graph classes, the class of unit interval graphs, proper hereditary classes of permutation graphs, every nowhere dense graph class [ 25 ] , and others. From the perspective of structural graph theory, it is natural to consider hereditary classes of graphs, or other structures – classes, which are closed under taking induced substructures. It is conjectured [ 1 , 6 , 16 ] that for hereditary classes, tractability coincides with monadic dependence . Conjecture 1 . For a hereditary class {\mathcal{C}} of structures in a finite relational language, \textit{{${\mathcal{C}}$ is tractable}}\quad\iff\quad\textit{${\mathcal{C}}$ is monadically dependent}. Monadic dependence is a notion originating in model theory, as part of Shelah’s vast classification program [ 33 ] . Briefly, a class {\mathcal{C}} is not monadically dependent if there is a formula \varphi(x,y) in the language of {\mathcal{C}} expanded by unary predicates, such that for every finite graph G there is a unary expansion \widehat{\mathbf{A}} of some structure \mathbf{A}\in{\mathcal{C}} and a subset X\subseteq V(\mathbf{A}) , such that G is isomorphic to the graph with vertices X and edges \{u,v\} such that \widehat{\mathbf{A}}\models\varphi(u,v) (another, equivalent definition is given in \Cref sec:prelims). For hereditary graph classes [ 16 ] , the left-to-right implication in \Cref conj:mc has been recently established (under complexity-theoretic assumptions). For general hereditary classes of graphs, the right-to-left implication in \Cref conj:mc remains open, but has been confirmed in several important cases, including monotone graph classes and more generally, edge-stable graph classes (see below), and – in the twin-width framework – for classes of permutation graphs [ 6 ] , of ordered graphs [ 5 ] , or of tournaments [ 22 ] . In particular, the celebrated result of Grohe, Kreutzer, and Siebertz [ 25 ] , states that every nowhere dense graph class is tractable. This is a structural property introduced by Nešetřil and Ossona de Mendez [ 29 ] . Nowhere dense graph classes include many well-studied classes of sparse graphs, such as the class of planar graphs, any class excluding a fixed graph as a minor, and any graph class with bounded maximum degree. Figure 1: A half-graph of order 4 . Extending the result of Grohe, Kreutzer, and Siebertz, the following result characterizes all hereditary, tractable graph classes which are edge-stable : avoid a half-graph as a semi-induced 1 1 1 That is, for some n\in\mathbb{N} , no graph G in the class contains vertices a_{1},b_{1},\ldots,a_{n},b_{n} with (a_{i},b_{j})\in E(G)\iff i\leqslant j . bipartite subgraph (see \Cref fig:half-graph). Theorem 2 ( [ 28 , 14 , 13 ] ) . The following conditions are equivalent for a hereditary, edge-stable graph class {\mathcal{C}} : 1. {\mathcal{C}} is tractable 2 2 2 The first item implies the other ones under a complexity theoretic assumption, \mathrm{AW}[*]\neq\mathrm{FPT} , 2. {\mathcal{C}} is monadically stable, 3. {\mathcal{C}} is monadically dependent. Monadic stability is another notion originating in model theory, introduced by Baldwin and Shelah [ 3 ] . A class {\mathcal{C}} is not monadically stable if there is a formula \varphi(x,y) in the language of {\mathcal{C}} expanded by unary predicates, such that for every n\in\mathbb{N} there is a unary expansion \widehat{\mathbf{A}} of a structure \mathbf{A}\in{\mathcal{C}} and elements v_{1},\ldots,v_{n} of \mathbf{A} such that \widehat{\mathbf{A}}\models\varphi(v_{i},v_{j}) if and only if i\leqslant j , for i,j\in[n] . Thus, only constant-size sets of vertices can be totally ordered by a fixed first-order formula in unary expansions of structures from a monadically stable class {\mathcal{C}} . Monadically stable graph classes include all nowhere dense classes, and their (1-dimensional) interpretations , e.g. the class of map graphs. Classes of structures equipped with relations of arity three or more haven’t been explored much in the context of the model checking problem. In principle, \Cref conj:mc might also apply in this setting. As a first step, the following result extends a previous result known for monotone graph classes, to classes of relational structures. A class of relational structures is monotone if it is closed under taking weak substructures: removing tuples