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?

$\begingroup$ That it is reflexive and symmetric is completely trivial. What is your doubt about transitivity? Maybe if you expanded on that point in your question, someone here could help with 'bridge the gap' between your understanding and a resolution. $\endgroup$ – Jacques Carette Mar 19 '10 at 16:21

$\begingroup$ I don't see any particular reason why it should be transitive. Of course, the 'usual' equivalence relation that looks a little bit like this is quasiisomorphism. Does this question have a context? $\endgroup$ – HJRW Mar 19 '10 at 16:25

$\begingroup$ Yes, for some years, I have been trying to prove that the quasiisometry relation for finitely generated groups is strictly harder than the isomorphism relation (in the sense of the theory of Borel equivalence relations). I can prove that the quasiisometry relation for arbitrary connected degree 4 graphs is strictly harder than the isomorphism relation for f.g groups ... but the quasiisometry relation for f.g. groups is much harder to work with. So it seems reasonable to consider the above "equivalence relation" as a first approximation ... except that I doubt that it is transitive! $\endgroup$ – Simon Thomas Mar 19 '10 at 16:36

4$\begingroup$ @Jacques: The point is that the generating set for H used to show that G \approx H and H \approx I need not be the same, so it is not obvious that G \approx I. $\endgroup$ – Qiaochu Yuan Mar 19 '10 at 16:46
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.

$\begingroup$ Very elegant! I had thought about these groups but was unable to make any progress on the problem of showing that $G \not \approx H$. $\endgroup$ – Simon Thomas Mar 23 '10 at 19:56