MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

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.

share|cite|improve this question
Do you mean contains a tree isometrically? If only up to biLipschitz equivalence, it looks to me like the answer does not depend on the generating set. – Bill Johnson Mar 29 '11 at 19:26
If you can do it in a bi-Lipschitz way, then you can embed it as a graph with a larger generating set. In general, to find an isometric copy is a harder question, but of course related. For the moment, I am only interested in the question that I asked, i.e. contains means containment in the sense of subgraphs. – Andreas Thom Mar 29 '11 at 19:43

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.

share|cite|improve this answer
Thanks, I will check. In fact, I am in Bloomington right now. – Andreas Thom Mar 30 '11 at 1:45
So far, this is not a complete answer. Lyons showed that the branching number of this tree equals the growth rate. Also, the spanning tree is subperiodic, which makes it somewhat understandable. But it is not clear whether it contains a copy or Lipschitz copy of a binary tree. If someone has other ideas, I would be happy to hear them. – Andreas Thom Mar 30 '11 at 17:45
Yes, the answer only shows a possible direction. What needs to be proved (disproved) is whether a tree of exponential growth contains a Lipschitz copy of the binary tree. Lyons has several papers about various probabilistic properties of trees: percolation, random walks, etc. So you should ask him. If he does not know the answer, I do not think anybody else would know. – Mark Sapir Mar 30 '11 at 19:26
I think it is easy to construct examples of trees of exponential growth with no such copy. However, I do not not about subperiodic examples with positive branching number. Thanks a lot for pointing our Lyons' work. – Andreas Thom Mar 30 '11 at 19:31
Russell Lyons explained to me an example of a subperiodic tree with branching number bigger than 1, which (for any stretching constant) does not contain stretched copies of finite binary tree of arbitrary size. In particular, a positive answer to my question is not an easy consequence of his results. – Andreas Thom Mar 30 '11 at 23:49

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).

share|cite|improve this answer
This was proved by Kevin Whyte for non-amenable groups. – Andreas Thom Apr 3 '11 at 14:44
I've made a small search and found the paper by Benjamini and Schramm "Every Graph With A Positive Cheeger Constant Contains A Tree With A Positive Cheeger Constant", GAFA, 1997. The mentioned result is a consequence of their theorem 1.5, see also the Remark 1.9. – Al Tal Apr 3 '11 at 15:52
Thanks a lot! I did not know about this paper. Kevin Whyte's paper ("Amenability, bi-Lipschitz equivalence, and the von Neumann conjecture." Duke Math. J. 99 (1999), no. 1, 93–112) appeared two years later. – Andreas Thom Apr 3 '11 at 16:37

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)

share|cite|improve this answer
Thanks, Alain. It's a nice result, but I do not care about the metric. So, the existence of a free subsemigroup already gives the existence of a generating set so that a binary tree is embedded. – Andreas Thom Apr 19 '11 at 20:46

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)

The question is stated eg. as Question 70 here but it is much older

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...)

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.