Infinitely many finitely generated groups having the same Cayley graph

Question

Is there an unlabeled locally-finite graph which is a Cayley graph of an infinitely many non-isomorphic groups with respect to suitably chosen generating sets?

Answer 1

Here I answer your additional question about finitely presented groups. The answer is then no.

Affirmation. Only finitely many finitely presentable groups may have the same given Cayley graph.

This works as follows. Let $X_1$ be the Cayley graph of some f.p. group. By finite presentability, there exists $n_0$ such that gluing $k$-gons each time you have a $k$-cycle in $X_1$ with $k\le n_0$, the resulting polygonal complex $X$ is simply connected. Now consider the locally compact group $G=\mathrm{Aut}(X_1)=\mathrm{Aut}(X)$. A finitely generated group with Cayley graph $X_1$ is the same as a group with a simply transitive action on $X_1$, hence letting $K$ be the stabilizer in $G$ of some vertex $x_0$, it is the same as a subgroup of $G$ whose intersection with each coset $gK$ is a singleton; let $\mathcal{W}$ be the set of subgroups of $G$ with this property. Using the action on $X$, a standard argument shows the following: let $S_G$ be the set of elements of $G$ mapping $x_0$ to a neighbor of $x_0$; then for every $\Gamma\in\mathcal{W}$, the group $\Gamma$ admits a presentation using $\Gamma\cap S_G$ as set of generators and relators of length $\le\max(2,n_0)$ (2 is necessary because of the possible generators of order 2, unless these are represented by double edges). Since there are only finitely many such presentations, we are done.

Note that the proof even shows that there are finitely many marked groups $(\Gamma,S)$ with a given Cayley graph, in the finitely presentable case.

Answer 2

Yes. You can even have uncountably many. One recipe is as follows: consider a group $G$ with finite generating subset $S$ and an extension $1\to F\to G'\stackrel{\pi}\to G\to 1$, with $F$ finite. Endow $G'$ with the generating subset $S'=\pi^{-1}(S)$. Then the Cayley graph of $(G',S')$ only depends on the Cayley graph of $(G,S)$ and of the cardinal of $F$: indeed it is obtained by replacing any vertex by a complete graph on $|F|$ vertices and replacing any edge by the corresponding bipartite graph.

Therefore what you need is to find $G$ and infinitely many non-isomorphic $G'$ with $F$ of fixed size. One way to do so is when $G$ admits a finitely generated central extension $\tilde{G}$ with center an infinite-dimensional vector space $Z$ over $\mathbf{Z}/p\mathbf{Z}$ for some prime $p$: then $Z$ admits continuum many hyperplanes $H$ and there are still (*) continuum many non-isomorphic groups among the $G'=\tilde{G}/H$.

(*) I use that if $G$ is a finitely generated group and $\mathcal{N}(G)$ is the set of its normal subgroups, and if we write $N\sim N'$ if $G/N$ and $G/N'$ are isomorphic groups, then the equivalence relation $\sim$ on $\mathcal{N}(G)$ has countable classes. (Standard exercise)

Edit: an application of this is that having a solvable word problem is not invariant under quasi-isometry (QI) among finitely generated groups, and also having a recursive presentation on finitely many generators is not a QI-invariant . Indeed if we choose $G$ to be the first Grigorchuk group, which has a solvable word problem, then among the uncountably many groups $G'$ obtained, only countably many have a solvable word problem (and more generally only countably many are recursively presented). In contrast, being finitely presented is a QI invariant, and being finitely presented with solvable word problem is a QI invariant as well, because it is equivalent to having the Dehn function bounded above by a recursive function (and the equivalence class of Dehn function is a QI invariant).

Answer 3

Here is a related construction, but which I find more elementary. The idea is to start from the lamplighter group $$L_2 := \langle a,t \mid a^2=1, [t^nat^{-n},a]=1 \ (n \in \mathbb{N}) \rangle,$$ to fix an arbitrary subset $I \subset \mathbb{N}$, and to define the new group $$G_I:= \left\langle a,t,z \mid a^2=z^2=[z,a]=[z,t]=1, [t^nat^{-n},a] = \left\{ \begin{array}{cl} 1 & \text{if } n \in I \\ z & \text{if } n \notin I \end{array} \right. \right\rangle.$$ In other word, we add a central element of order two and we use it to "twist" the commutator relations of $L_2$. By killing $z$, we recover $L_2$ as a quotient, and the corresponding kernel is $\langle z \rangle$. Observe that $z$ has order two in $G_I$ since, by killing $a$ and $t$, it is sent to a non-trivial element in the quotient $\mathbb{Z}/2 \mathbb{Z}$. In other word, we have a central extension $$1 \to \mathbb{Z}/2\mathbb{Z} \to G_I \to L_2 \to 1.$$ As explained by Yves in his answer, this implies that all the $G_I$ share a common Cayley graph. It remains to show that there exist uncountably many distinct groups among the $G_I$.

Lemma: The groups $G_I$ and $G_J$ are isomorphic iff $I=J$.

Sketch of proof. First, we need to know that the automorphism group of $L_2$ is generated by the inner automorphisms, the inversion of $t$, and the "transvections" induced by $$\left\{ \begin{array}{ccc} a \mapsto a \\ t \mapsto gt \end{array} \right., \ g \in \langle \langle a \rangle \rangle.$$ Next, we observe that they all extend to automorphisms of $G_I$. This implies that, if there exists an isomorphism $\varphi : G_J \to G_I$, then, up to post-composing with an automorphism of $G_I$, we can suppose without loss of generality that $\varphi$ induces the identity $L_2 \to L_2$ when we quotient by the centers of $G_I,G_J$. Consequently, there exist $\epsilon,\eta \in \{0,1\}$ such that $$\varphi : \left\{ \begin{array}{ccc} z_J & \mapsto & z_I \\ a_J & \mapsto & z_I^\epsilon a_I \\ t_J & \mapsto & z_I^\eta t_I \end{array} \right..$$ It follows that $\varphi \left( [t_J^na_Jt_J^{-n},a_J] \right) = [t_I^na_It_I^{-n},a_I]$ for every $n \in \mathbb{N}$, hence $I=J$. $\square$

Remark: Following Yves' edition of his answer, we deduce that the lamplighter group $L_2$, which has solvable word problem, is quasi-isometric a group with unsolvable word problem. More explicitly, if $I \subset \mathbb{N}$ is not a computable subset, then $G_I$ is a finitely generated group that is quasi-isometric to $L_2$ but whose word problem is unsolvable.