Growth of groups versus Schreier graphs 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. 
 A: 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$.
