2026-07-22T16:58:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3679 2024-03-06T10:34:22Z ddc:004 open_access

Pebble Games and Linear Equations Grohe, Martin Otto, Martin Finite model theory finite variable logics graph isomorphism Weisfeiler- Lehman algorithm linear programming Sherali–Adams hierarchy 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Martin Grohe and Martin Otto 2012 Is Part Of LIPIcs, Volume 16, Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL (2012) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2012.289 urn:nbn:de:0030-drops-36790 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2012.289 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode