Forbidden Induced Subgraphs for Bounded Shrub-Depth and the Expressive Power of MSO
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909464644288512 |
|---|---|
| author | Mählmann, Nikolas |
| author_facet | Mählmann, Nikolas |
| contents | The graph parameter shrub-depth is a dense analog of tree-depth. We characterize classes of bounded shrub-depth by forbidden induced subgraphs. The obstructions are well-controlled flips of large half-graphs and of disjoint unions of many long paths. Applying this characterization, we 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 classes on which FO and MSO coincide, answering an open question by [Elberfeld, Grohe, and Tantau; LICS 2012].
Our 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. This improves upon a result of [Ossona de Mendez, Pilipczuk, and Siebertz; Eur. J. Comb. 2025] who showed the same statement for FO-transductions instead of FO-interpretations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_13903 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Forbidden Induced Subgraphs for Bounded Shrub-Depth and the Expressive Power of MSO Mählmann, Nikolas Logic in Computer Science Discrete Mathematics Combinatorics Logic The graph parameter shrub-depth is a dense analog of tree-depth. We characterize classes of bounded shrub-depth by forbidden induced subgraphs. The obstructions are well-controlled flips of large half-graphs and of disjoint unions of many long paths. Applying this characterization, we 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 classes on which FO and MSO coincide, answering an open question by [Elberfeld, Grohe, and Tantau; LICS 2012]. Our 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. This improves upon a result of [Ossona de Mendez, Pilipczuk, and Siebertz; Eur. J. Comb. 2025] who showed the same statement for FO-transductions instead of FO-interpretations. |
| title | Forbidden Induced Subgraphs for Bounded Shrub-Depth and the Expressive Power of MSO |
| topic | Logic in Computer Science Discrete Mathematics Combinatorics Logic |
| url | https://arxiv.org/abs/2501.13903 |