"...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/