Vol. 9, No. 3, 2020

Download this article
Download this article For screen
For printing
Recent Issues
Volume 9, Issue 3
Volume 9, Issue 2
Volume 9, Issue 1
Volume 8, Issue 4
Volume 8, Issue 3
Volume 8, Issue 2
Volume 8, Issue 1
The Journal
About the Journal
Editorial Board
Subscriptions
 
Submission Guidelines
Submission Form
Policies for Authors
Ethics Statement
 
founded and published with the
scientific support and advice of the
Moscow Institute of
Physics and Technology
 
ISSN (electronic): 2640-7361
ISSN (print): 2220-5438
Previously Published
Author Index
To Appear
 
Other MSP Journals
Generalizations of $k$-dimensional Weisfeiler–Leman stabilization

Anuj Dawar and Danny Vagnozzi

Vol. 9 (2020), No. 3, 229–252
Abstract

The family of Weisfeiler–Leman equivalences on graphs is a widely studied approximation of graph isomorphism with many different characterizations. We study these and other approximations of isomorphism defined in terms of refinement operators and Schurian polynomial approximation schemes (SPAS). The general framework of SPAS allows us to study a number of parameters of the refinement operators based on Weisfeiler–Leman refinement, logic with counting, lifts of Weisfeiler–Leman as defined by Evdokimov and Ponomarenko, the invertible map test introduced by Dawar and Holm, and variations of these, as well as to establish relationships between them.

Keywords
Weisfeiler–Leman, combinatorics, invertible map, graph isomorphism, complexity theory, coherent configuration
Mathematical Subject Classification 2010
Primary: 05E15, 05E30, 05E99
Secondary: 03D15
Milestones
Received: 3 August 2019
Revised: 14 May 2020
Accepted: 29 May 2020
Published: 15 October 2020
Authors
Anuj Dawar
Department of Computer Science and Technology
University of Cambridge
Cambridge
United Kingdom
Danny Vagnozzi
Department of Computer Science and Technology
University of Cambridge
Cambridge
United Kingdom