Universal covers, color refinement, and two-variable counting logic: Lower bounds for the depth

Original · EN

Given a connected graph G and its vertex x, let Uₓ(G) denote the universal cover of G obtained by unfolding G into a tree starting from x. Let T=T(n) be the minimum number such that, for graphs G and H with at most n vertices each, the isomorphism of Uₓ(G) and Uy(H) surely follows from the isomorphism of these rooted trees truncated at depth T. Motivated by applications in theory of distributed computing, Norris [Discrete Appl. Math. 1995] asks if T(n)≤ n. We answer this question in the negative by establishing that T(n)=(2-o(1))n. Our solution uses basic tools of finite model theory such as a bisimulation version of the Immerman-Lander 2-pebble counting game. The graphs Gₙ and Hₙ we construct to prove the lower bound for T(n) also show some other tight lower bounds. Both having n vertices, Gₙ and Hₙ can be distinguished in 2-variable counting logic only with quantifier depth (1-o(1))n. It follows that color refinement, the classical procedure used in isomorphism testing and other areas for computing the coarsest equitable partition of a graph, needs (1-o(1))n rounds to achieve color stabilization on each of Gₙ and Hₙ. Somewhat surprisingly, this number of rounds is not enough for color stabilization on the disjoint union of Gₙ and Hₙ, where (2-o(1))n rounds are needed.