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

Speaker(s)

Nikolas Mählmann

Affiliation

University of Warsaw

Language of the talk

English

Date

Oct. 22, 2025, 2:15 p.m.

Room

room 5440

Title in Polish

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

Seminar

Seminar Automata Theory

---

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.

---