Trees in groups of exponential growth

Question

Question: Let $G$ be a finitely generated group with exponential growth. Is there a finite generating set $S \subset G$, such that the associated Cayley graph $Cay(G,S)$ contains a binary tree?

Some background:

1. The existence of such a tree clearly implies exponential growth.

2. Kevin Whyte showed in Amenability, Bilipschitz Equivalence, and the Von Neumann Conjecture, Duke Journal of Mathematics 1999, p. 93-112, that such trees exist if $G$ is non-amenable. So the question is only open for amenable groups of exponential growth.

3. One good reason for such a binary tree to exist is the existence of a free semigroup inside $G$. In fact, if $G$ is solvable, then the existence of such a semigroup is known to be equivalent to exponential growth (and equivalent to being not virtually nilpotent). This is part of some version or extension of the Tits alternative. Grigorchuk constructed an amenable torsion group with exponential growth, which does not contain such a semigroup, but it contains a binary tree.

EDIT: Al Tal pointed out in an answer below that Benjamini and Schramm covered the non-amenable case (this is 2. from above) already in Benjamini and Schramm "Every Graph With A Positive Cheeger Constant Contains A Tree With A Positive Cheeger Constant", GAFA, 1997.

Answer 1

Look at Russell Lyons, Random walks and the growth of groups, C. R. Acad. Sci. Paris 320 (1995), 1361--1366 (you can find it on Lyons' Web page). Consider any generating set and for every vertex take the shortlex smallest path connecting the vertex and 1. Then take the union of all these paths. What you get is a (spanning) subtree which has exponential growth. I think that in the paper, Lyons proves that this tree contains a binary subtree if the growth function is exponential. The reason for this is that the degree of growth can be expressed in terms of the so-called "cuts". And if the spanning tree has too many vertices of degree 2, there would be too many cuts consisting of one vertex, and the growth rate would be 0. Of course this tree is not a full subgraph, just a subgraph, but the question asks for a subgraph only.

Answer 2

Some time ago I was interested in the same question, but for the strengthened, bi-Lipschitz case (mentioned above by Bill Johnson). For non-amenable groups it is true; Victor Guba told me how prove this, using Gromov's criteria of non-amenability. Also I was told that this result was obtained in a work of Benjamini and Shramm (I don't know the paper).

For amenable groups of exponential growth the answer is unknown to me, but I am very interested in it.

It is also interesting if the same hold for the following little more general case. Graph $\Gamma$ is non necessarily a Cayley graph, but a vertex-transitive graph that has exponential growth of balls cardinality (we consider balls centered in some fixed point).

Answer 3

This (so nice) question seems to be equivalent with the notorious and old problem of constructing a supraamenable (or superamenable) group of exponential growth. Recall that a supraamenable group is one such that every non-empty set is not G-paradoxical, or equivalently, given any non-empty subset of G, there exists a finitely additive invariant measure on G that assigns measure one to the set. All groups of sub-exponential growth are supraamenable, but no other example is known.

Basic defintions are here (before Exercise 8 and Remark 3) http://terrytao.wordpress.com/2009/01/08/245b-notes-2-amenability-the-ping-pong-lemma-and-the-banach-tarski-paradox-optional/

The question is stated eg. as Question 70 here but it is much older http://www.unige.ch/math/folks/delaharpe/articles/18-CGH.pdf

Non supraamenability seems to be equivalent with the existence of a generating set such that the Cayley graph contains the binary tree. Indeed, if such a generating set $S$ exists then the set $V$ containing the vertices of the tree is paradoxical using elements from $S^{-1}$: take the subset of the left sons and the one of the right sons, they will both cover their mothers. Conversely, if $X=X_1 \sqcup X_2$ is a paradoxical subset of $G$ and $S$ is the (finite) set of elements involved in the paradox, then $S^{-1}$ will do, as long as one gets sure identity is not in $S$ (which can be assumed). Start with any $x \in X$ as initial root. A paradox is nothing else than a $2$ to $1$ piecewise $G$- map $f:X \rightarrow X$ so one can choose the left son the counter image of $x$ in $X_1$ and for the right son the counter image in $X_2$ and continue by induction (there is a little problem, at exactly one point in the process there might be a cycle ocurring (due to the root trying to connect), but then one can delete the whole infected half...)

Answer 4

If G is a finitely generated solvable group with exponential growth, then G contains a quasi-isometrically embedded free semi-group (this is a result of Y. Cornulier and R. Tessera, Quasi-isometrically embedded free sub-semigroups; Geom. Topol. 12 461-473, 2008, improving on Rosenblatt)