# Infinitely many finitely generated groups having the same Cayley graph

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?

-

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.

-

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

-
Looks like it works. Any ideas how to make the resulting groups finitely presentable (of course there will be only countably many of them)? – Al Tal Mar 12 '14 at 19:14
This method does not provide finitely presented groups, I have to think about it. (A simple argument shows it's impossible with groups of polynomial growth.) – YCor Mar 12 '14 at 20:04