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$
$\endgroup$
4
asked Mar 19, 2010 at 16:07
-
$\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 CaretteCommented Mar 19, 2010 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 quasi-isomorphism. Does this question have a context? $\endgroup$– HJRWCommented Mar 19, 2010 at 16:25
-
$\begingroup$ Yes, for some years, I have been trying to prove that the quasi-isometry 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 quasi-isometry relation for arbitrary connected degree 4 graphs is strictly harder than the isomorphism relation for f.g groups ... but the quasi-isometry 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 ThomasCommented Mar 19, 2010 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 YuanCommented Mar 19, 2010 at 16:46
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
-
$\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$ Commented Mar 23, 2010 at 19:56