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.