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 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.

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.