Monadically Stable Classes of Graphs

Speaker(s)

Nikolas Mählmann

Affiliation

University of Bremen

Date

May 10, 2023, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

Intuitively, a class of graphs is monadically stable if first-order logic cannot encode arbitrary long linear orders in it. While originating from model theory, monadic stability generalizes many combinatorial properties of sparse graph classes such as planarity, bounded treewidth, bounded degree, and, more general, nowhere denseness. Using monadic stability, we were recently able to lift the good algorithmic properties of aforementioned sparse classes to a dense setting, obtaining an FPT first-order model checking for transductions of nowhere dense classes [Dreier, NM, Siebertz; 2023]. As an introduction to the topic we will prove a purely combinatorial characterization of monadic stability dubbed flip-flatness, which is a key ingredient to its algorithmic applications. This is based on joint work with Jan Dreier, Jakub Gajarský, Rose McCarty, Pierre Ohlmann, Michał Pilipczuk, Wojciech Przybyszewski, Sebastian Siebertz, Marek Sokołowski, and Szymon Toruńczyk.

---