MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question is motivated by this one What is the relation between the number syntactic congruence classes, and the number of Nerode relation classes? where it essentially asks to compare the growth of the syntactic monoid with the growth of the minimal automaton. A special case is the following. Let G be an infinite finitely generated group and H a subgroup such that G acts faithfully on G/H. How different can the growth of G and the Schreier graph of G/H be?

I know the Grigrchuk group of intermediate growth has faithful Schreier graphs of polynomial growth.

Are there groups of exponential growth with faithful Schreier graphs of polynomial growth?

Schreier graphs of non-elementary hyperbolic groups with respect to infinite index quasi-convex subgroups have non-amenable Schreier graphs so ths should be avoided.

share|cite|improve this question
Every regular graph of even degree is a Schreier graph of a free group. Basically you can make any growth you like. Faithfulness of a Schreier graph is not a problem usually. If you want a particular example in the spirit of the Grigorchuk group, you can take the Basilica group: it has exponential growth, acts faithfully on its Schreier graphs corresponding to stabilizers of infinite sequences, and these Schreier graphs have polynomial growth. – Ievgen Bondarenko Nov 19 '11 at 12:50
I believed a free group was no problem but most of the examples I tried to draw in my head were not faithful. I was sure somebody new an example off the top of their head. Basilica is good because the polynomial growth is from contracting like in Grigorchuk group. – Benjamin Steinberg Nov 19 '11 at 18:27
up vote 4 down vote accepted

This holds true, for example, for free groups. Actually, take $G$ to be a free product of three copies of $Z/2Z$, which has an index two subgroup which is rank 2 free. The Cayley graph for this group (which has undirected edges) is just a trivalent tree, with edges colored 3 colors by the generators, so that every vertex has exactly 3 colors (this is known as a Tait coloring). Any cubic graph with a Tait coloring corresponds to a Schreier graph of a (torsion-free) subgroup $H$ of $G$, which is the quotient of the Cayley graph of $G$ by the subgroup $H$ (one may choose a root vertex to correspond to the trivial coset). Closed paths starting from the root vertex correspond to elements of the subgroup $H$.

Choose a cubic graph with a Tait coloring which has linear growth and corresponds to a subgroup $H$ satisfying your condition ($G$ acts faithfully on $G/H$). This is equivalent to $\cap_{g\in G} gHg^{-1}=\{1\}$. For example, take a bi-infinite ladder, labeling the two stringers with matching sequences of colors, which then determine the colors of the rungs. By making these stringer sequences aperiodic, you can guarantee that $\cap_{g\in G} gHg^{-1}=\{1\}$. Changing the root vertex corresponds to changing the conjugacy class. In fact, we may choose stringer sequences which contain any word in $G$. Then putting a root at the endpoint of such a word, we guarantee that it is not in the corresponding conjugate subgroup of $H$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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