Which groups contain a comb?

Question

The comb is the undirected simple graph with nodes $\mathbb{N} \times \mathbb{N}$ where $\mathbb{N} \ni 0$ and edges $$ \{\{(m,n), (m,n+1)\}, \{(m,0), (m+1,0)\} \;|\; m \in \mathbb{N}, n \in \mathbb{N}\} $$

Let $G$ be a discrete group. Say that $G$ contains a comb if there exists a finite set $S \not\ni 1_G$ such that the comb is a subgraph of the (simple undirected) Cayley graph $\mathrm{Cay}(\langle S \rangle, S)$.

I don't require spanning or induced subgraphs, just plain subgraphs. I don't require anything involving "Lipschitz", the teeth $\{n\} \times \mathbb{N}$ may get close to each other whenever they like, just not intersect each other or themselves.

Suppose $G$ is not locally virtually cyclic. Does it necessarily contain a comb?

One can equivalently restrict to f.g. groups and require that $\mathrm{Cay}(G, S)$ directly contains the comb (and drop the "locally").

In case the answer is "no" (or is hard to solve), I also state a quantitative version of this below.

If $G$ is f.g. and not virtually cyclic then $\mathrm{Cay}(G,S)$ contains infinitely many vertex-disjoint paths for some finite generating set $S$. By joining these rays, we obtain that every group that is not locally virtually cyclic contains a comb with some co-infinite set of ``teeth'' removed. (This is more or less Halin's grid theorem, see discussion and follow references of http://www.dim.uchile.cl/~mstein/domin.pdf .)

Let $T \subset \mathbb{N}$ be an infinite set. The $T$-comb is the undirected simple graph with nodes $(T \times \mathbb{N}) \cup (\mathbb{N} \times \{0\})$ and edges $$ \{\{(t,n), (t,n+1)\}, \{(m,0), (m+1,0)\} \;|\; m \in \mathbb{N}, t \in T, n \in \mathbb{N}\} $$

Can something be said about the ``maximal density'' of $T \subset \mathbb{N}$ such that $G$ contains an $T$-comb? (E.g. can we pick $T$ to be the values of a fixed polynomial.)

Some thoughts of mine, not very polished:

• By compactness arguments and changing the generators, it is easy to see that the question stays equivalent if we assume that the comb has a two-sided spine or two-sided teeth, i.e. we can replace one or both of the $\mathbb{N}$ by $\mathbb{Z}$, and similarly containing a $T$-comb for syndetic $T \subset \mathbb{N}$ is equivalent to containing a comb.

• Any nonamenable group contains a comb, because it even contains a binary tree Trees in groups of exponential growth

• Any Cayley graph of an infinite f.g. group contains bi-infinite paths, so if $G$ has an infinite quotient $H$ whose kernel is not locally finite (i.e. $G$ is f.g. and ``(not locally finite)-by-infinite'') then it contains a comb. For this, pick an infinite path in both $H$ and $K$ w.r.t. some generators. Lift the path from $H$ arbitrarily to $G$ (include preimages for generators of $G$ in the generating set $S$ of $G$), and everywhere on this path, start another path in the kernel direction.

• For solvable groups, the answer is "yes": Among f.g. groups, solvable groups of exponential growth contain a binary tree (see the MO link above), solvable groups of subexponential growth are virtually nilpotent by Milnor-Wolf, and to a virtually nilpotent group you can e.g. apply the previous observation (if a group contains a subgroup containing a comb it contains a comb, and all subgroups of a virtually nilpotent group are finitely generated). I don't know if there's an easy argument for elementary amenable groups.

• One thing that seems obvious to try (but I don't have the chops) is to take a bi-infinite geodesic in $G$ (path where all finite subpaths of length $n$ join group elements at distance $n$ in the Cayley graph), and start random walks every $k$ steps for some $k$, which (I'm told) diverge almost surely on all groups with growth faster than $n^2$ (and in the unsolved case the growth is superpolynomial). Perhaps for large enough $k$ you can use Lovász local lemma or something to prove that these do not necessarily hit each other.

Answer 1

I checked the usual suspects and seems that [Chou, Ching. Elementary amenable groups. Illinois J. Math. 24 (1980), no. 3, 396--407. doi:10.1215/ijm/1256047608. https://projecteuclid.org/euclid.ijm/1256047608] solves the elementary amenable case. I don't know if I should just modify my question since this is not an answer, but here goes.

Theorem 3.2'. A finitely generated group in $EG$ is either almost nilpotent or it contains a free subsemigroup on two generators.

Here, $EG$ is the class of elementary amenable group, i.e. the smallest class of groups which contains all finite groups and all abelian groups and is closed under group extensions and direct unions. Almost nilpotent is what I called virtually nilpotent in my question, i.e. has a nilpotent subgroup of finite index (here necessarily f.g.). Then apply the third and fourth item from my question, details below though probably obvious to experts if correct.

Theorem. Let $G$ be an elementary amenable group which is not locally virtually cyclic. Then $G$ contains a comb.

Proof: W.l.o.g. $G$ is a finitely-generated group that is not virtually cyclic. If $G$ contains a free subsemigroup on two generators, we are done. Otherwise, by Chou's theorem it is virtually nilpotent. So we show that if $G$ is a virtually nilpotent group then either $G$ is virtually cyclic or it contains a comb.

For this, for a contradiction suppose $G$ is nilpotent of minimal nilpotency class among those nilpotent groups that are not virtually cyclic and do not contain a comb. It is well-known that the commutator subgroup $[G, G]$ is finitely generated (f.g. nilpotent $\implies$ polycyclic $\implies$ maximal condition on subgroups), and of course it is nilpotent of smaller nilpotency class. If it is not virtually cyclic, then it contains a comb by the inductive assumption, thus so does $G$, so we may assume $[G, G]$ is virtually cyclic.

If $[G, G]$ is finite, then the abelianization $G/[G, G]$ cannot be virtually cyclic or $G$ would also be virtually cyclic ($\mathbb{Z}$ is a free group, just pick a section), and thus by the fundamental theorem of abelian groups $G/[G, G]$ contains a copy of $\mathbb{Z}^2$, thus a comb. It follows that $[G, G]$ must be virtually $\mathbb{Z}$. If the abelianization $G/[G, G]$ is finite, then $G$ is virtually cyclic by definition. We conclude in particular $[G, G]$ and $G/[G, G]$ are both infinite f.g. groups.

We now do as in the third item in my question (I explain the general trick though of course here we could simplify a bit): Pick a bi-infinite injective path $p$ in some Cayley graph of $[G, G]$ with some finite set of generators $S \subset G$ and pick another one $q$ in the Cayley graph of $G/[G, G]$ with some finite set of generators $T$. Pick for each $t \in T$ a preimage in $G$, i.e. $s_t \in G$ such that $t = [G, G] s_t$. Now the path $s_q$ defined in the obvious way by lifting $q$ (if $q$ is a sequence over $\mathbb{Z}$ of generators $t \in T$, pick the corresponding path along generators $s_t$) is injective as a path in $G$, since even its projection to $G/[G, G]$ is by definition injective. Now, start the path $p$ from each vertex on the path $s_q$, and observe that these paths do not intersect themselves (since $p$ does not), and they do not intersect each other since their projections in $G/[G, G]$ stay inside distinct cosets.

That concludes the proof.