View PDF HTML (experimental)

Abstract:We study the expressive power of first-order logic with counting quantifiers, especially the $k$-variable and quantifier-rank-$q$ fragment, using homomorphism indistinguishability. Recently, Dawar, Jakl, and Reggio~(2021) proved that two graphs satisfy the same $k$-variable and quantifier-rank-$q$ sentences if and only if they are homomorphism indistinguishable over the class of graphs admitting a $k$-pebble forest cover of depth $q$. After reproving this result using elementary means, we provide a graph-theoretic analysis of this graph class. This allows us to separate it from the intersection of the class of all graphs of treewidth at most $k-1$ and the class of all graphs of treedepth at most $q$, provided that $q$ is sufficiently larger than $k$.
We are able to lift this separation to a (semantic) separation of the respective homomorphism indistinguishability relations. We do this by showing that the graph classes of all graphs of treedepth at most $q$ and of graphs admitting a $k$-pebble forest cover of depth $q$ are homomorphism distinguishing closed, as conjectured by Roberson~(2022).
In order to prove Roberson's conjecture for the class of graphs admitting a $k$-pebble forest cover of depth $q$ we characterise the class in terms of a monotone Cops-and-Robber this http URL crux is to prove that if Cop has a winning strategy then Cop also has a winning strategy that is this http URL that end, we show how to transform Cop's winning strategy into a pre-tree-decomposition, which is inspired by decompositions of matroids, and then applying an intricate breadth-first `cleaning up' procedure along the pre-tree-decomposition (which may temporarily lose the property of representing a strategy), in order to achieve monotonicity while controlling the number of rounds simultaneously across all branches of the decomposition via a vertex exchange argument.

Submission history

From: Eva Fluck [view email] [via Logical Methods In Computer Science as proxy]
[v1] Fri, 2 May 2025 11:32:01 UTC (97 KB)
[v2] Fri, 19 Dec 2025 15:17:35 UTC (66 KB)
[v3] Wed, 1 Apr 2026 13:36:21 UTC (86 KB)
[v4] Fri, 24 Apr 2026 14:07:36 UTC (89 KB)
[v5] Fri, 26 Jun 2026 08:34:47 UTC (91 KB)