"...O, cursed spite, that ever I was to set it right!" Hamlet, Act 1, scene 5 CAYLEY GRAPHS AND GOD'S ALGORITHM In this chapter 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, G = subgroup S_X. The "Cayley graph" 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 permuation group is connected. Example: Let G = = 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 = < S54 be the group of the 3x3 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 (including the 3x3 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: http://admin.dis.on.ca:80/~cubeman/