Forbidden Induced Subgraphs for Bounded Shrub-Depth and the Expressive Power of MSO

Prelegent(ci)

Nikolas Mählmann

Afiliacja

University of Warsaw

Język referatu

angielski

Termin

22 października 2025 14:15

Pokój

p. 5440

Tytuł w języku polskim

Forbidden Induced Subgraphs for Bounded Shrub-Depth and the Expressive Power of MSO

Seminarium

Seminarium „Teoria automatów”

---

The graph parameter shrub-depth is a dense analog of tree-depth with strong ties to logic and combinatorics.
I will characterize graph classes of bounded shrub-depth by forbidden induced subgraphs.
As an application, I will show that on every hereditary class of unbounded shrub-depth, MSO is more expressive than FO.
This confirms a conjecture of [Gajarský and Hliněný; LMCS 2015] who proved that on classes of bounded shrub-depth FO and MSO have the same expressive power.
Combined, the two results fully characterize the hereditary graph classes on which FO and MSO coincide, answering an open question by [Elberfeld, Grohe, and Tantau; LICS 2012].
My work is inspired by the notion of stability from model theory.
A graph class C is MSO-stable, if no MSO-formula can define arbitrarily long linear orders in graphs from C.
We show that a hereditary graph class is MSO-stable if and only if it has bounded shrub-depth.
As a key ingredient, we prove that every hereditary class of unbounded shrub-depth FO-interprets the class of all paths.

---