## Cayley graphs

Let be a permutation group,

The Cayley graph of with respect to is the graph whose vertices are the elements of and whose edges are determined by the following condition: if and belong to then there is an edge from to (or from to ) if and only if or , for some .

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 with respect to is the digraph whose vertices are the elements of and whose edges are determined by the following condition: if and belong to then there is an edge from to if and only if , for some .

Lemma 5.16.3   Let denote the Cayley graph associated to the permutation group . Let . Then, for all , .

proof: Assume not. Then there is a with either

(i) , or

(ii) .

First, we note that, for each , the set is an edge of . This follows from the definition of the Cayley graph.

If then, by definition of the Cayley graph, there are distinct with , for all , where the are distinct elements of . This contradicts the definition of .

If then, by definition of the Cayley graph, there are distinct in such that . Since is a group and (as sets), we may cancel the 's from both sides of the equation , contradicting the assumption that is distinct from .

Example 5.16.4   : Let

where , and . Then the Cayley graph of with respect to may be visualized as

Example 5.16.5   : Let

be the group of the Rubik's cube. Each position of the cube corresponds to an element of the group (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 is the number of moves in the best possible solution in the worst possible case.

Exercise 5.16.6   Construct the Cayley graph of , the cyclic group, with respect to the generator .

Exercise 5.16.7   Check that each vertex of the Cayley graph of has valence 12.

Exercise 5.16.8   Construct the Cayley graph of , the symmetric group on four letters, with respect to the generators , and .

Exercise 5.16.9   Construct the Cayley digraph of with respect to the generators , . (Show, in particular, that do indeed generate .)

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

Exercise 5.16.11   Construct the Cayley graph of , the cyclic group, with respect to the generator .

Exercise 5.16.12   Construct the Cayley graph of , the symmetric group on four letters, with respect to the generators , and .

Exercise 5.16.13   Construct the Cayley digraph of with respect to the generators , . (Show, in particular, that do indeed generate .)

david joyner 2008-04-20