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=\mbox{SL}_{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.

17 pages, 1 figure; v2: improved result for Cayley graphs; v3: added reference