2
$\begingroup$

I am trying to get through the proof of the following theorem:

Let $G = (V,E)$ be a locally finite, connected, infinite graph with linear growth and infinite motion. Then $G$ is 2-distinguishable.

In the proof of this theorem we claim that the stabilizer of every vertex $v\in V$ is finite and since the vertex set is countable, the stabilizer can only have countably many conjugacy classes and hence the automorphism group itself must be countable.

I don't quite understand that. Why can the stabilizer have only countably many conjugacy classes and how does that imply that the automorphism group must be countable?

Maybe I am missing some definitions here. The stabilizer of the element $s$ in the group $\Gamma$ is the set: $$\Gamma_s = \{ \gamma \in \Gamma : \gamma s = s \}$$ And the conjguacy class of an element $a$ in the group $G$ is a set, such that: $$Cl(a) = \{b \in G : \exists g \in G: b = gag^{-1}\}$$

We would like to get assumptions to use a following statement to prove our thesis.

Let $\Gamma$ be a group of permutations of a set $S$ and assume that $\Gamma$ has infinite motion. If $\Gamma$ is countable then there is $\Gamma$-distinguishing 2-colouring of $S$.

Could anyone explain that to me, please?

$\endgroup$
  • $\begingroup$ If ${\rm Stab}(v)$ is finite then of course it has countably many conjugacy classes. Perhaps the author instead meant to write ${\rm Aut}(G)$ contains countably many subgroups conjugate to ${\rm Stab}(v)$? (This would follow from $V$ being countable since $g{\rm Stab}(v)g^{-1}={\rm Stab}(gv)$.) $\endgroup$ – anon May 19 '18 at 1:44
  • $\begingroup$ Thank you for your reply and I am really sorry, but abstract algebra is not something what I am familiar with and it just turned out to be important. Still don't get that equation you've written. What happened with the $g^{-1}$, but I get that implies that $V$ is countable. Maybe it would be helpful if I said that we need to get following assumptions to use a theorem to get our thesis. Let $\Gamma$ be a group of permutations of a set $S$ and assume that $\Gamma$ has infinite motion. If $\Gamma$ is countable then there is $\Gamma$-distinguishing 2-colouring of $S$. $\endgroup$ – Dreeze May 19 '18 at 7:48
  • $\begingroup$ Well, $\sigma v=v$ is equivalent to $(g\sigma g^{-1})(gv)=gv$, so $\sigma\in{\rm Stab}(v)$ is equivalent to $g\sigma g^{-1}\in{\rm Stab}(gv)$. Therefore $$ {\rm Stab}(gv)=\{ g\sigma g^{-1}\mid \sigma\in{\rm Stab}(v)\}=g{\rm Stab}(v)g^{-1}. $$ Also, I never said "implies that $V$ is countable" in my comment, I used the fact that $V$ was countable to conclude ${\rm Stab}(v)$ has countably many conjugate subgroups $g{\rm Stab}(v)g^{-1}$ (since all of these conjugates will be of the form ${\rm Stab}(w)$ where $w$ is another vertex, and there are only countably many vertices). $\endgroup$ – anon May 19 '18 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.