Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-17T12:15:35.843Z Has data issue: false hasContentIssue false

PEBBLE GAMES AND LINEAR EQUATIONS

Published online by Cambridge University Press:  22 July 2015

MARTIN GROHE
Affiliation:
DEPARTMENT OF COMPUTER SCIENCE RWTH AACHEN UNIVERSITYGERMANYE-mail: grohe@informatik.rwth-aachen.de
MARTIN OTTO
Affiliation:
DEPARTMENT OF MATHEMATICS TECHNISCHE UNIVERSITÄT DARMSTADTGERMANYE-mail: otto@mathematik.tu-darmstadt.de
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Articles
Copyright
Copyright © The Association for Symbolic Logic 2015