Combinatorial Characterizations of Monadically Dependent Graph Classes

Speaker(s)

Szymon Toruńczyk

Affiliation

MIMUW

Date

March 6, 2024, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

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 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 cliquewidth and bounded treewidth. 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 subdivisions of cliques, and allows us to resolve one half of the main conjecture in the area: The first-order model checking problem is AW[*]-hard on every hereditary graph class that is not monadically dependent. Joint work with Jan Dreier and Nikolas Mählmann.

---