The Weisfeiler–Leman algorithm and the diameter of Schreier graphs

  • Daniele Dona

    Georg-August-Universität Göttingen, Germany
The Weisfeiler–Leman algorithm and the diameter of Schreier graphs cover

A subscription is required to access this article.

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 acting on -tuples of vectors in ; moreover, an exact expression is found in the case of Cayley graphs.

Cite this article

Daniele Dona, The Weisfeiler–Leman algorithm and the diameter of Schreier graphs. Groups Geom. Dyn. 13 (2019), no. 4, pp. 1235–1253

DOI 10.4171/GGD/521