Growth of groups versus Schreier graphs - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T19:37:43Z http://mathoverflow.net/feeds/question/81321 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/81321/growth-of-groups-versus-schreier-graphs Growth of groups versus Schreier graphs Benjamin Steinberg 2011-11-19T06:32:10Z 2011-11-19T08:15:50Z <p>This question is motivated by this one <a href="http://mathoverflow.net/questions/32899/what-is-the-relation-between-the-number-syntactic-congruence-classes-and-the-num" rel="nofollow">http://mathoverflow.net/questions/32899/what-is-the-relation-between-the-number-syntactic-congruence-classes-and-the-num</a> 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?</p> <p>I know the Grigrchuk group of intermediate growth has faithful Schreier graphs of polynomial growth.</p> <blockquote> <blockquote> <p>Are there groups of exponential growth with faithful Schreier graphs of polynomial growth?</p> </blockquote> </blockquote> <p>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. </p> http://mathoverflow.net/questions/81321/growth-of-groups-versus-schreier-graphs/81323#81323 Answer by Agol for Growth of groups versus Schreier graphs Agol 2011-11-19T08:15:50Z 2011-11-19T08:15:50Z <p>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 <a href="http://en.wikipedia.org/wiki/Tait_coloring" rel="nofollow">Tait coloring</a>). 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$. </p> <p>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$.</p>