Current browse context:
math.CO
Change to browse by:
References & Citations
Mathematics > Combinatorics
Title: Flip-Breakability: A Combinatorial Dichotomy for Monadically Dependent Graph Classes
(Submitted on 22 Mar 2024 (v1), last revised 27 Mar 2024 (this version, v2))
Abstract: A conjecture in algorithmic model theory predicts that the model-checking problem for first-order logic is fixed-parameter tractable on a hereditary graph class if and only if the class is monadically dependent. Originating in model theory, this notion is defined in terms of logic, and encompasses nowhere dense classes, monadically stable classes, and classes of bounded twin-width. Working towards this conjecture, we provide the first two combinatorial characterizations of monadically dependent graph classes. This yields the following dichotomy.
On the structure side, we characterize monadic dependence by a Ramsey-theoretic property called flip-breakability. This notion generalizes the notions of uniform quasi-wideness, flip-flatness, and bounded grid rank, which characterize nowhere denseness, monadic stability, and bounded twin-width, respectively, and played a key role in their respective model checking algorithms. Natural restrictions of flip-breakability additionally characterize bounded treewidth and cliquewidth and bounded treedepth and shrubdepth.
On the non-structure side, we characterize monadic dependence by explicitly listing few families of forbidden induced subgraphs. This result is analogous to the characterization of nowhere denseness via forbidden subdivided cliques, and allows us to resolve one half of the motivating conjecture: First-order model checking is AW[$*$]-hard on every hereditary graph class that is monadically independent. The result moreover implies that hereditary graph classes which are small, have almost bounded twin-width, or have almost bounded flip-width, are monadically dependent.
Lastly, we lift our result to also obtain a combinatorial dichotomy in the more general setting of monadically dependent classes of binary structures.
Submission history
From: Nikolas Mählmann [view email][v1] Fri, 22 Mar 2024 13:44:17 GMT (1030kb,D)
[v2] Wed, 27 Mar 2024 15:28:17 GMT (1068kb,D)
Link back to: arXiv, form interface, contact.