“…O, cursed spite,
that ever I was to set it right!”
Hamlet, Act 1, scene 5

In this post we introduce a graphical interpretation of a permutation group, the Cayley graph. This is then interpreted in the special case of a group arising from a permutation puzzle.
To begin, what’s a graph? A graph is a pair of countable sets (V,E), where

* V is a countable set of singleton elements called “vertices”,

* E is a subset of {{v1,v2} | v1,v2 in V} called “edges”.

If e={v1,v2} belongs to E then we say that e is an “edge from v1 to v2″ (or from v2 to v1). If v and w are vertices, a “path” from v to w is a finite sequence of edges beginning at v and ending at w:

            e0={v,v1}, e1={v1,v2}, ..., en={vn,w}.

If there s a path from v to w then we say v is connected to w. We say that a graph (V,E) is connected if each pair of vertices is connected. The number of edges eminating from a vertex v is called the degree (or valence) of v.

Example: If

              V = {a,b,c},   E={{a,b},{a,c},{b,c}},

then we may visualize (V,E) as

                       * c
                      / \
                     /   \
                  a * --- * b

Each vertex has valence 2.

Definition: If v and w are vertices connected to each other in a graph (V,E) then we define the “distance from v to w”, denoted d(v,w), by

          d(v,w) =   min   |{edges in a path from v to w}|
                   v,w in V
                   connected

By convention, if v and w are not connected then we set d(v,w) equal to infinity. The diameter of a graph is the largest possible distance:

               diam((V,E)) =   max   d(v,w)
                            v,w in V

In the above example, the diameter is 1.

Cayley graphs

Let G be a permutation group generated by elements K = {g1,…,gn}:

         G = <g1,g2,...,gn>   subgroup   S_X.

The Cayley graph (with respect to K) of G 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=gi*x or x=gi*y, for some i = 1,2,…,n.

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

Example: Let

G = <s1,s2> = S3,

where s1=(1 2), and s2=(2 3). Then the Cayley graph of G may be visualized as

                                  1  *
                                    /  \
                                   /    \
                               s1 *      * s2
                                 /        \
                                /          \
                         s2*s1 *            * s1*s2
                                \          /
                                 \        /
                                  \      /
                                   \    /
                                    \  /
                                     *  s1*s2*s1=s2*s1*s2

Example: Let

                   G = <R,L,U,D,F,B>  <  S54

be the group of the 3×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 (exercise: check this). 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.

Problem: Let G be the group of a permutation puzzle. Find the diameter of the Cayley graph of G.

This problem is unsolved for most puzzles (now solved for the 3×3 Rubik’s cube) and appears to be difficult computationally. The cases where it is known include (with no attempt at completeness) the following:

                     puzzle       |    diameter  
                     --------------------------
                   pyraminx       |      11 (not including tip moves)     
               2x2 Rubik's cube   |      14

Problem: Let G be the group of a permutation puzzle and let v be a vertex in the Cayley graph of G. Find an algorithm for determining a path from v to the vertex v0 associated to the identity having length equal to the distance from v to v0.

This problem is much harder. The algorithm, if it exists, is called “God’s algorithm“.

Exercise: Find the Cayley graph of the group

              G = <(1 2), (2 3), (3 4)> = S4.

Find the diameter of this graph.

There is a good discussion of God’s algorithm on the www page of Mark Longridge and on Tom Rokicki’s page.