Going deep and going wide: Counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth This work extends articles [ 17 , 6 ] which were presented at CSL and MFCS 2024. It is also part of second author’s PhD thesis [ 16 ] .
Isolde Adler, Eva Fluck, Tim Seppelt, Gian Luca Spitzer · 2025
Read Going deep and going wide: Counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth This work extends articles [ 17 , 6 ] which were presented at CSL and MFCS 2024. It is also part of second author’s PhD thesis [ 16 ] . by Isolde Adler, Eva Fluck, Tim Seppelt, Gian Luca Spitzer (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-01193.txt.
Introduction
Isolde Adler and co-authors study how much a counting logic can say about graphs whose depth or width stays small. The key tool is a notion of two graphs looking the same through homomorphisms into a class of test graphs. The team first re-proves a known link between logic sentences and one such test class using basic means.
They then show the test class differs from the overlap of bounded width and bounded depth classes once depth grows past width. Both classes are closed under the test, which settles a conjecture. A cops-and-robber game gives the main proof, with a cleanup step that makes the cop plan monotone.
Catalog record
| CREATOR | Isolde Adler, Eva Fluck, Tim Seppelt, Gian Luca Spitzer |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 155 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-01193