5
$\begingroup$

I have come across two definitions of Cayley graphs, both very similar but one being more general.

I have been working with the more general definition which is:

A Cayley graph of a group 􏰎$X$ with a subset􏰐 $S \subset X$ 􏰏, is defined by taking X to be the vertex set of the Cayley graph, with directed edges $(g,h)$ whenever $gh^{-1} \in S$.

However in other texts i have read that $S$ needs to be a generating set of $X$, this stronger version implies that the Cayley graph will be connected.

I understand that the cayley graph depends on the choice of $S$ as this defines the edges and intuitively get why the graph would be connected if the set generates the group, however i am struggling to prove it formally. I want to be able to link the two definitions in my notes by proving the graph is connected.

any help on providing a proof as to why the graph would be connected would be much appreciated, thank you.

$\endgroup$
5
  • 1
    $\begingroup$ There are some characters in the question that I cannot read, but your observation is correct. If $S$ can be an arbitrary subset of $X$, then the resulting graph may not be connected. In the other case, the graph will always be connected. There are also (sometimes) definitions that require that if $g\in S$ then $g^{-1}\in S$. $\endgroup$
    – TravisJ
    Commented Apr 8, 2015 at 21:00
  • $\begingroup$ @TravisJ how can i formally show that it is also connected, as the text i have read it in just states it without proving $\endgroup$
    – Peter A
    Commented Apr 8, 2015 at 21:07
  • $\begingroup$ I agree with @TravisJ your observations seem very correct. Well done $\endgroup$
    – HBeel
    Commented Apr 8, 2015 at 21:12
  • $\begingroup$ I wrote up the details. A note, connected here means strongly connected (i.e. a directed path from any $u$ to any $v$). $\endgroup$
    – TravisJ
    Commented Apr 8, 2015 at 21:20
  • $\begingroup$ @TravisJ perfect, very clear thank you ! $\endgroup$
    – Peter A
    Commented Apr 8, 2015 at 21:50

3 Answers 3

5
$\begingroup$

To show that $\Gamma(G)$ is connected, you need to be able to generate a path from $v$ to $u$ for any $v, u\in G$. Think of a step from $v$ as a multiplication of $v$ by some element in $S$. If you end up at vertex $w_1$ then you multiplied $v$ by $v^{-1}w_{1}\in S$. A path that takes you from $v$ to $u$ will look like: $v, w_1, w_2, ..., w_k, u$ and the multiplications that you did, in sequence were $$(v^{-1}w_{1})(w_{1}^{-1}w_{2})...(w_{k}^{-1}u)=v^{-1}u$$ The question then is, can you write $v^{-1}u$ as a product of elements in $S$? If $S$ generates $G$ then you can (for any $v^{-1}u\in G$). If there is any pair for which you cannot write such a product, i.e. a $v, u\in G$ so that there is no finite product of elements in $S$ that make $v^{-1}u$ then $S$ cannot generate $G$ since it cannot generate the element $v^{-1}u$.

$\endgroup$
3
  • $\begingroup$ would the distinction of left and right multiplication by elements in S dictate the direction of the edge, as in this proof you have used right multiplication with an element in S, and in my definition used $gh^{−1} \in S$. which would imply that the directed edge (g,h) occurs if $g =sh $ $\endgroup$
    – Peter A
    Commented Apr 9, 2015 at 0:25
  • $\begingroup$ @PeterA, Left multiplying (as you suggest) just creates the edges pointed in the other direction, a path from $u$ to $v$ instead of from $v$ to $u$. $\endgroup$
    – TravisJ
    Commented Apr 9, 2015 at 1:26
  • $\begingroup$ Is it true that if $\Gamma(G)$ is not connected then each connected component corresponds to cosets of $\langle S \rangle$ in $G$? $\endgroup$
    – old
    Commented Aug 22, 2018 at 18:01
3
$\begingroup$

I believe that the consensus among graph theorists working with Cayley graphs is that the connection set is not required to be a generating set; thus a Cayley graph does not have to be connected. So we have Sabidussi's theorem that a graph $X$ is a Cayley graph if and only if there is a subgroup of its automorphism group that acts regularly on $V(X)$.

Note that this theorem is stated in this form on the wikipedia page, even though they offer the "wrong" definition of Cayley graph.

$\endgroup$
0
$\begingroup$

If you're trying to formally prove that the graph is connected if and only if $S$ forms a generating set for $G$, you should try to directly prove the following:

  • Two vertices $g,h$ are connected by a path if and only if $gh^{-1}$ is in the subgroup generated by elements of $S$.

Here I am interpreting a path as a finite chain of edges, not necessarily pointing in the same direction. (This may very well be nonstandard.)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .