2
$\begingroup$

The answer to this question could be trivial !

Definition:

Let $G$ be a group and $S$ a symmetric subset of $G$ (i.e., $s \in S$ iff $s^{ −1} \in S$), the Cayley graph $Cay(G; S)$ of $G$ w.r.t. $S$ is the graph whose vertex set is $G$ and $a \in G$ is connected to $\{sa| s \in S\}$. This is a $k$-regular graph with $k = |S|$. It is connected iff $S$ generates $G$.

Connected Components:

A graph $Cay(G,S)$ can be constructed even if the set $S$ does not generate the group $G$. However, it is disconnected graph. In this case, each connected component of the graph represents a coset of the subgroup generated by $S$. Thus by Lagrange theorem the number of connected components is $$\frac{|G|}{|\left<S\right>|}$$

Minimal Generating Set Case:

Let $S=\{s_1,\ldots,s_k\}$ be minimal generating set of $G$, and let $S'=S\setminus\{s_k, s^{-1}_k\}$. It is easy to see that $Cay(G,S')$ is spanning subgraph of $Cay(G,S)$, and that the number of connected components of $Cay(G,S')$ and $Cay(G,S)$ is respectively $\frac{|G|}{|\left<S'\right>|}$ and 1.

Question?

Let $S$ and $S'$ be defined as in the previous part. Let $\left<S'\right>x$, and $\left<S'\right>y$ be the vertices of two connected components of $Cay(G,S')$. I'm pretty sure that in $Cay(G,S)$ there exists edge between certain vertex $x'\in \left<S'\right>x $ and another vertex $y'\in \left<S'\right>x$, but I do not know how to prove it. In other words, how can we prove that between any two connected components of $Cay(G,S')$ there exists edge in $Cay(G,S)$?

Any idea will be useful!

$\endgroup$
  • 1
    $\begingroup$ I think the answer is "no". For example, consider the cross product of the cyclic groups of order $2$ and $4$: $C_4\times C_2=\langle a, b; a^2, b^4, [a, b]\rangle$. Let $S=\{a, b\}$ and $S^{\prime}=\{a\}$. Then there are $4$ connected components corresponding to $S^{\prime}$, and the component containing the identity $1$ is of distance $2$ from the component containing $b^2$. (Think of the components lying at the vertices of a square.) $\endgroup$ – user1729 Mar 31 '16 at 10:24
  • $\begingroup$ @user1729 Could you please tell me what does $[a,b]$ mean? $\endgroup$ – M.Badaoui Mar 31 '16 at 10:34
  • $\begingroup$ I've addressed this in my answer, below. Short answer is: you can ignore it. Longer answer: it means $aba^{-1}b^{-1}$, so it implies $aba^{-1}b^{-1}=1$, and so $ab=ba$. So $a$ and $b$ commute ($[u, v]$ is called a "commutator"). $\endgroup$ – user1729 Mar 31 '16 at 10:39
3
$\begingroup$

The answer is "no".

For example, consider the cross product of the cyclic groups of order $2$ and $4$: $C_4\times C_2=\langle a, b; a^2, b^4, [a, b]\rangle$*. Let $S=\{a, b\}$ and $S^{\prime}=\{a\}$. Then there are $4$ connected components corresponding to $S^{\prime}$, and the component containing the identity $1$ is of distance $2$ from the component containing $b^2$. (Think of the components lying at the vertices of a square.)

I think this is made even clearer by considering the infinite group $H\times \mathbb{Z}$ with $S=\{X, b\}$ where $b$ is the generator of the $\mathbb{Z}$ factor. (Here $H$ is just any group.) Now look at the connected components associated to $H$. These components correspond to the cosets $Hb^i$, and the distance in the graph between the cosets $Hb^i$ and $Hb^j$ is simply $|i-j|$. These components lie in a "line", and we can loop the line round to give a homomorphism onto $H\times C_n$ where $C_n$ is the cyclic group of order $n$. This is what is going on in the first paragraph - $n=4$ is the minimum for the distance to be greater than $1$.

*(This $\langle -;-\rangle$ notation is called a presentation, and I am simply using it as a neat way of saying $a$ generates the $C_2$ factor and $b$ generated the $C_4$ factor. The notation $[a, b]$ means $aba^{-1}b^{-1}$, which implies that $a$ and $b$ commute (that is, $ab=ba$) so I have a cross product.)

$\endgroup$
  • $\begingroup$ See the bottom paragraph. Short answer is: you can ignore it. Longer answer: it means $aba^{-1}b^{-1}$, so it implies $aba^{-1}b^{-1}=1$, and so $ab=ba$. So $a$ and $b$ commute ($[u, v]$ is called a "commutator"). $\endgroup$ – user1729 Mar 31 '16 at 10:41

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.