Going deep and going wide: Counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth

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 tree depth 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 tree depth 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 game. The crux is to prove that if Cop has a winning strategy then Cop also has a winning strategy that is monotone. To 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