When is a Schreier Coset graph on a group $G$ with subgroup $H$ and symmetric generating set $S$(without identity) vertex transitive?

It is well known that when $H$ is normal, the Schreier coset graph corresponding is isomorphic to a Cayley graph and hence vertex-transitive. But, what is the characterization of $H$ and $S$ so that the graph be vertex-transitive. Typically, when is the Schreier coset graph is not vertex-transitive? Note that we neglect the self loops that may occur because of having elements in $S$ that also belong to $H$. Any hints? Thanks beforehand.

  • $\begingroup$ as the action on (right, say) cosets is transitive, I would expect any such graph to be vertex-transitive. $\endgroup$ Commented Mar 14, 2022 at 9:49
  • 1
    $\begingroup$ @DimaPasechnik [almost] any regular graph is a Schreier graph, but not every regular graph is vertex-transitive; see e.g. this question for more references. $\endgroup$
    – ARG
    Commented Mar 14, 2022 at 9:53
  • $\begingroup$ You should specify whether you consider the graph as labeled, whether you include self-loops, and whether (assuming the graph unlabeled), you identify multiples edges. $\endgroup$
    – YCor
    Commented Mar 14, 2022 at 10:01
  • 2
    $\begingroup$ OK, I see. If I am not mistaken, one example of a vertex-transitive Schreier graph comes from S being a conjugacy class (or a union of such classes) in G, and H not containing any element of S. $\endgroup$ Commented Mar 14, 2022 at 10:14
  • $\begingroup$ @DimaPasechnik: Transitivity of the right action on right cosets tells you exactly that the Schreier graph is connected. It tells you nothing about the symmetries of the graph, because the right action on cosets (i.e. vertices) does not a priori extend to the edges. $\endgroup$
    – HJRW
    Commented Mar 14, 2022 at 11:44

1 Answer 1


Preliminaries: in the following, $G$ will always be a finitely generated group and $\mathrm{Schr}(G,H;S)$ will be the Schreier graph corresponding to the symmetric generating set $S^{\pm1}$. Schreier graphs will be unlabelled non-oriented graphs, with possibly self-loops and multiple edges. Before going further, observe that if we look at labelled Schreier graphs, the graphs is transitive (by labelled automorphisms) if and only if the subgroup is normal; so this is not really interesting.

Transitive Schreier graphs

This question was somehow solved in https://arxiv.org/pdf/1505.03433.pdf

Proposition A Schreier graph $\mathrm{Schr}(G,H;S)$ is transitive if and only if H is length-isomorphic to all of its conjugate. That is: for every $g\in G$ there exists a group isomorphisms $\alpha_G\colon H\to g^{-1}Hg$ that preserves length: $|\alpha_G(h)|_S=|h|_S$ for every $h\in H$.

Observe that $\alpha_g$ is defined on $H$ only, not on $G$.

The above characterisation might seem silly and just an easy rewriting of what transitivity means for a Schreier graph. In some sense it is, however it can still be used to obtain some informations. A few words about that below.

Dependence to the generating set

It is well-known (and easy to prove) that if $H$ is a normal subgroup of $G$, then all of its Schreier graphs are transitive. The converse is true and is in fact witnessed by small symmetric generating sets:

Proposition If $\mathrm{Schr}(G,H;S)$ is transitive for all generating sets of size no more than $\mathrm{rank}$, then $H$ is a normal subgroup of $G$.

The above result shows that for non-normal subgroups, transitivity of the Schreier graph depends highly on the generating set. This is easily seen on finite groups, where every subgroup $H$ will have a transitive Schreier graph for $S=G\setminus\{1\}$. (In fact this is true for a general $G$, with the caveat that $S$ won't be finite in general)

A strengthening of normality

In view of the above, let us say that a subgroup $H$ of $G$ is length-transitive if there exists a generating set of size no more than $\mathrm{rank}(G)+1$ such that $\mathrm{Schr}(G,H;S)$ is transitive. One can show that the intersection of two length-transitive subgroups is itself length-transitive. This naturally lead to

Definition A non-trivial group $G$ is strongly simple if its only length transitive subgroups are $\{1\}$ and $G$ itself.

It follows from the definition that cyclic groups of prime order are strongly simple and that strongly simple groups are simple. These implications are stricts as demonstrated by

Proposition For odd $n\geq 7$, the alternating group $A_n$ is simple but not strongly simple.

Proposition Tarski monsters are strongly simple (in fact, their Schreier graphs are not even quasi-transitive, and this for every finite symmetric generating set).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.