Monadically Stable Classes of Graphs

Prelegent(ci)

Nikolas Mählmann

Afiliacja

University of Bremen

Termin

10 maja 2023 14:15

Pokój

p. 5050

Seminarium

Seminarium „Teoria automatów”

---

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.

---