PEBBLE GAMES AND LINEAR EQUATIONS

Martin Grohe, Martin Otto

Journal of Symbolic Logic · 2015 · 54 citations · 16 references

Concepts

TL;DR

Prior work linked basic colour refinement to fractional isomorphism and showed that these concepts correspond to the base level of the Sherali–Adams hierarchy, with higher levels interleaving as proved by Atserias–Maneva and Malkin. This study aims to give a precise characterization of the k‑level Sherali–Adams relaxation via a modified counting pebble game, to construct a variant that matches the k‑pebble counting game exactly, to prove that the two hierarchies interleave strictly, and to explore analogous results for a boolean‑arithmetic version of the game. The authors analyze the Sherali–Adams relaxation and its correspondence to pebble‑game equivalence using combinatorial and linear‑algebraic techniques, extending the framework to a boolean‑arithmetic variant and deriving matching hierarchies. They prove that the Sherali–Adams and pebble‑game hierarchies interleave strictly, provide simplified combinatorial and linear‑.

Abstract

Abstract We give a new, simplified and detailed account of the correspondence between levels of the Sherali–Adams relaxation of graph isomorphism and levels of pebble-game equivalence with counting (higher-dimensional Weisfeiler–Lehman colour refinement). The correspondence between basic colour refinement and fractional isomorphism, due to Tinhofer [22; 23] and Ramana, Scheinerman and Ullman [17], is re-interpreted as the base level of Sherali–Adams and generalised to higher levels in this sense by Atserias and Maneva [1] and Malkin [14], who prove that the two resulting hierarchies interleave. In carrying this analysis further, we here give (a) a precise characterisation of the level k Sherali–Adams relaxation in terms of a modified counting pebble game; (b) a variant of the Sherali–Adams levels that precisely match the k -pebble counting game; (c) a proof that the interleaving between these two hierarchies is strict. We also investigate the variation based on boolean arithmetic instead of real/rational arithmetic and obtain analogous correspondences and separations for plain k -pebble equivalence (without counting). Our results are driven by considerably simplified accounts of the underlying combinatorics and linear algebra.

References

16