We give a new, simplified and detailed account of the correspondence#R##N#between levels of the Sherali-Adams relaxation of graph isomorphism#R##N#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 Ramana, Scheinerman and Ullman, is re-interpreted as the base level of Sherali-Adams and generalised to higher levels in this sense by Atserias and Maneva, who prove that the two resulting hierarchies interleave.#R##N##R##N#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.#R##N##R##N#We also investigate the variation based on boolean arithmetic instead#R##N#of real/rational arithmetic and obtain analogous correspondences and#R##N#separations for plain k-pebble equivalence (without counting). Our#R##N#results are driven by considerably simplified accounts of the#R##N#underlying combinatorics and linear algebra.
['Martin Grohe', 'Martin Otto']
Pebble Games and Linear Equations