Question

Let $\approx$ be the binary relation on the class of finitely generated groups such that $G \approx H$ iff $G$ and $H$ have isomorphic (unlabeled nondirected) Cayley graphs with respect to suitably chosen finite generating sets. Is $\approx$ an equivalence relation?

Answer 1

The answer is no, as expected. The following proof is "joint work" with L. Scheele. Consider $G=\mathbb{Z}$, $K=D_\infty$ and $H:=\mathbb{Z}\times \mathbb{Z}/2\mathbb{Z}$. Then $G \approx K$ and $K\approx H$, but $G \not\approx H.$

Indeed, the Cayley graph associated to $\{-1,1\}$ for G and the Cayley graph associated to $\{s,t\}$ where $D_\infty=\langle s,t: s^2=t^2=1 \rangle$ are clearly isometric.

Similarly, the Cayley graph associated to $\{s,st,ts\}$ for $K$ and the graph associated to $\{(0,1),(-1,0),(1,0)\}$ for $H$ are isometric.

However, let $S$ be some symmetric generating set for $G$. Then $S_k$, the set of vertices which have distance precisely $k\geq 1$ from the identity, has even cardinality because $S_k$ is invariant under the mapping $x \mapsto -x$ and doesn't contain 0.

Now let $T$ be some symmetric generating set for $H$. Let $k_0$ be the distance of $(0,1)$ from the identity in the associated graph. Then $T_{k_0}$, the set of vertices which have distance precisely $k_0$ from the identity, has odd cardinality. Indeed, it is invariant under the mapping $(x,y) \mapsto (-x,-y)$ since $T$ is assumed to be symmetric. But $(0,1)$ is a fixed point.