The Weisfeiler-Leman algorithm and the diameter of Schreier graphs (Q2286350)

Summary: 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 = \mathrm{SL}_n (\mathbb F_q)\) \((q > 2)\) acting on \(k\)-tuples of vectors in \(\mathbb F^n_q\); moreover, an exact expression is found in the case of Cayley graphs.