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

CREATORIsolde Adler, Eva Fluck, Tim Seppelt, Gian Luca Spitzer
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE155 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-01193

Browse the full library · About the Tower of Babel