The Weisfeiler–Leman algorithm and the diameter of Schreier graphs

Abstract

We prove that the number of iterations taken by the Weisfeiler–Leman algorithm for configurations coming from Schreier graphs is closely linked to the diameter of the graphs themselves: an upper bound is found for general Schreier graphs, and a lower bound holds for particular cases, such as for Schreier graphs with $G=S{L}_n({\mathbb{F}}_q)(q>2)$ acting on $k$-tuples of vectors in ${\mathbb{F}}_q^n$; moreover, an exact expression is found in the case of Cayley graphs.