Cayley graphs

Let $G$ be a permutation group,

$$G = <g_1,g_2,...,g_n> < S_X.$$

The Cayley graph of $G$ with respect to $X=\{g_1,g_2,...,g_n\}$ is the graph $(V,E)$ whose vertices $V$ are the elements of $G$ and whose edges are determined by the following condition: if $x$ and $y$ belong to $V=G$ then there is an edge from $x$ to $y$ (or from $y$ to $x$ ) if and only if $y=g_i*x$ or $x=g_i*y$ , for some $i=1,2,...,n$ .

Cayley graphs are named for Arthur Cayley (August 1821-January 1895), who though starting out as a laywer, eventually published over 900 papers and notes covering nearly every aspect of modern mathematics. The most important of his work is in developing the algebra of matrices, work in non-euclidean geometry and n-dimensional geometry.

The Cayley digraph of $G$ with respect to $X=\{g_1,g_2,...,g_n\}$ is the digraph $(V,E)$ whose vertices $V$ are the elements of $G$ and whose edges are determined by the following condition: if $x$ and $y$ belong to $V=G$ then there is an edge from $x$ to $y$ if and only if $y=x*g_i$ , for some $i=1,2,...,n$ .

Lemma 5.16.3   Let $\Gamma_G=(V,E)$ denote the Cayley graph associated to the permutation group $G = <g_1,g_2,...,g_n>$ . Let $N=\vert\{g_1,g_1^{-1},g_2,g_2^{-1},...,g_n,g_n^{-1}\}\vert$ . Then, for all $v\in V$ , ${\rm degree}(v)=N$ .

proof: Assume not. Then there is a $v\in V=G$ with either

(i) ${\rm degree}(v)<N$ , or

(ii) ${\rm degree}(v)>N$ .

First, we note that, for each $h\in \{g_1,g_1^{-1},g_2,g_2^{-1},...,g_n,g_n^{-1}\}$ , the set $\{v,h*v\}$ is an edge of $\Gamma_G$ . This follows from the definition of the Cayley graph.

If $r={\rm degree}(v)>N$ then, by definition of the Cayley graph, there are distinct $v_1,...,v_r\in V$ with $v=h_i*v_i$ , for all $1 \leq i \leq r$ , where the $h_1,...,h_r$ are distinct elements of $\{g_1,g_1^{-1},g_2,g_2^{-1},...,g_n,g_n^{-1}\}$ . This contradicts the definition of $N$ .

If $r={\rm degree}(v)<N$ then, by definition of the Cayley graph, there are distinct $h_i,h_j$ in $\{g_1,g_1^{-1},g_2,g_2^{-1},...,g_n,g_n^{-1}\}$ such that $h_i*v=h_j*v$ . Since $G$ is a group and $V=G$ (as sets), we may cancel the $v$ 's from both sides of the equation $h_i*v=h_j*v$ , contradicting the assumption that $h_i$ is distinct from $h_j$ . $\Box$

Example 5.16.4   : Let

$$G = \langle s_1,s_2\rangle = S_3,$$

where $s_1=(1, 2)$ , and $s_2=(2, 3)$ . Then the Cayley graph of $G$ with respect to $X=\{s_1,s_2\}$ may be visualized as

Example 5.16.5   : Let

$$G = \langle R,L,U,D,F,B\rangle < S_{54}$$

be the group of the $3\times 3$ Rubik's cube. Each position of the cube corresponds to an element of the group $G$ (i.e., the move you had to make to get to that position). In other words, each position of the cube corresponds to a vertex of the Cayley graph. Each vertex of this graph has valence 12.

Moreover, a solution of the Rubik's cube is simply a path in the graph from the vertex associated to the present position of the cube to the vertex associated to the identity element. The number of moves in the shortest possible solution is simply the distance from the vertex associated to the present position of the cube to the vertex associated to the identity element. The diameter of the Cayley graph of $G$ is the number of moves in the best possible solution in the worst possible case.

Exercise 5.16.6   Construct the Cayley graph of $C_4$ , the cyclic group, with respect to the generator $s=(1, 2,3,4)$ .

Exercise 5.16.7   Check that each vertex of the Cayley graph of $G = \langle R,L,U,D,F,B\rangle$ has valence 12.

Exercise 5.16.8   Construct the Cayley graph of $S_4$ , the symmetric group on four letters, with respect to the generators $s_1=(1 2)$ , $s_2=(2 3)$ and $s_3=(3 4)$ .

Exercise 5.16.9   Construct the Cayley digraph of $S_3$ with respect to the generators $f=(1, 3)$ , $r=(1,2,3)$ . (Show, in particular, that $f,r$ do indeed generate $S_3$ .)

Exercise 5.16.10   Show that the Cayley graph of a permutation group is connected.

Exercise 5.16.11   Construct the Cayley graph of $C_4$ , the cyclic group, with respect to the generator $s=(1, 2,3,4)$ .

Exercise 5.16.12   Construct the Cayley graph of $S_4$ , the symmetric group on four letters, with respect to the generators $s_1=(1 2)$ , $s_2=(2 3)$ and $s_3=(3 4)$ .

Exercise 5.16.13   Construct the Cayley digraph of $S_3$ with respect to the generators $f=(1, 3)$ , $r=(1,2,3)$ . (Show, in particular, that $f,r$ do indeed generate $S_3$ .)