How does a group strictly grows?

Question

I've been going through a paper by Warshall where he shows the presence of dead-ends of unbounded depth$^1$ (for any generating set) in the (discrete) Heisenberg group. This turns out to be the case for the lamplighter group [Cleary and Taback] (and perhaps for many amenable non-virtually-abelian groups?), and the lamplighter has also unbounded retreat depth$^2$ [Erschler]. The question is if one "chops off" the dead-ends, how fast does the group still grows?

More precisely, given an (finitely generated) amenable non-virtually-abelian group $G$, construct its Cayley graph for a (finite) generating set $S$. Take a function $f:G \to [0,\infty[$ with only one local minimum at $e_G$. Keep/orient the edges so that $f$ is strictly increasing by following the oriented edges. Take away all vertices $g$ so that there is no infinite oriented path starting at $e_G$ and passing through $g$.

$\textbf{Question 1}$: If $f(g) = |g|_S$, may it happen that the graph grows more slowly (i.e. little o) than the original Cayley graph?

$\textbf{Question 2}$: Does there exists an $f$ so that no (or few) vertices are removed in the process?

$^1$ if I'm quoting correctly, given a generating set $S$ of an infinite group $G$, the depth of an element $g \in G$ is $\inf \lbrace d_S(g,g') \mid g' \in B_{|g|_S} ^c \rbrace$, i.e. the distance to the closest element of strictly bigger word length.

$^2$ the retreat depth of $g \in G$ (w.r.to $S$) is the smallest $d$ such that $g$ belongs to an infinite component in the Cayley graph minus its ball of radius $B_{|g|_S-d}$. Actually, what are the (amenable non-virtually-abelian) groups with bounded retreat depth?

Answer 1

For Q2, the answer is yes. It suffices to enumerate the vertices of the Cayley graph by natural numbers so that each vertex (except the first one) is adjacent to at least one with a smaller number and at least one with a larger number.

This is possible for any locally finite connected graph $\Gamma=(V,E)$ which enjoys the following "no single-point boundary" property:

• for any finite set $X\subset V$ of vertices, there are at least two vertices in $V\setminus X$ adjacent to something in $X$.

It is easy to see that every Caley graph satisfies this. To enumerate such a graph, proceed by induction and keep the following condition satisfied at each step: If $X$ is the set of vertices enumerated so far, then $X$ is a connected graph and $V\setminus X$ does not have finite connected components. The first condition ensures that the last enumerated vertex is adjacent to at least one enumerated earlier. The second condition implies that $V\setminus X$ does not have isolated points, so the next enumerated vertex will be connected to something not yet enumerated.

Assume that these conditions are satisfied, and pick a vertex $a\in V\setminus X$, connected to $X$, that you would like to be numbered. If $V\setminus (X\cup a)$ does not have finite connected components, just assign the next available number to $a$. Otherwise let $Y\subset V$ be the union of these finite components and $a$. Clearly $Y$ is a connected graph. Let us first enumerate everything in $Y\setminus a$, then we will be able to assign the next number to $a$. It suffices to find a vertex $y\in Y\setminus a$ such that

(1) $y$ is adjacent to something in $X$; and

(2) $Y\setminus y$ is connected.

(Once such $y$ is found, assign it the next number and repeat the procedure until $Y\setminus a$ is exhausted.)

If $Y$ is biconnected (i.e. does not not lose connectedness after removal of any vertex), then any $y\in Y\setminus A$ which is adjacent to something in $X$ works. And such $y$ exists due to the "no single-point boundary" property applied to $Y\setminus a$.

If $Y$ is not biconnected, consider its biconnected components. They are arranged to a tree. Take a leaf node of this tree, i.e. a biconnected component which contains only one cut vertex. If a leaf component contains $a$, choose another one (there at least two leaf nodes in any nontrivial tree). Let $Z$ be this leaf component and $b$ its cut vertex. Now the same argument as above, applied to $Z$ and $b$ in place of $Y$ and $a$, yields that a desired vertex $y$ exists in $Z\setminus b$.

Thus any vertex $a$ adjacent to something in $X$ can be handled after finitely many steps. Since the graph is connected, this allows us to enumerate everything.