From mschoene@math.rwth-aachen.de  Wed Dec  7 19:36:43 1994
Return-Path: <mschoene@math.rwth-aachen.de>
Received: from samson.math.rwth-aachen.de by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA17629; Wed, 7 Dec 94 19:36:43 EST
Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp
	(Smail3.1.28.1 #11) id m0rFSJi-000MPVC; Wed, 7 Dec 94 20:46 MET
Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19)
	id m0rFSJi-0000PsC; Wed, 7 Dec 94 20:46 PST
Message-Id: <m0rFSJi-0000PsC@hobbes.math.rwth-aachen.de>
Date: Wed, 7 Dec 94 20:46 PST
From: "Martin Schoenert" <Martin.Schoenert@math.rwth-aachen.de>
To: cube-lovers@life.ai.mit.edu
Subject: Cayley Graphs

I wrote in my e-mail message of 1994/11/08

            Note that the elements of M are also a autmorphisms of the Cayley
    graph.  That means that elements of M respects the length of operations.
    That is if g_1 and g_2 are elements of G that are in one conjugacy class
    under M, then the lenght of the shortest process effecting them is equal.
    This follows from the fact that M fixes the set of the generators of G
    and their inverses.  M is fact the largest subgroup of the outer
    autmorphism group with this property, which makes it rather important.

Jerry Bryan answered in his e-mail message of 1994/11/08

    This of course is the basis for the large searches I have been able
    to perform using M-conjugate classes.  The only trouble is, I don't
    even know what a Cayley graph is (but I am working on it), the last
    course I took in group theory being 25 years ago.

The Cayley graph Gamma for a group G generated by a certain system of
generators < g_1, g_2, ... > is defined as follows.

The vertices of Gamma correspond to the elements of G.  From vertex v_1
draw an edge to v_2 labelled with g_i, if and only if v_1 g_i = v_2.
Also draw an edge from v_2 to v_2 labelled g_i^-1 (or g_i').

So the Cayley graph depends on the group *and* on the generating system.
Simple, isn't it.

In this terminology God's number for the cube is simply the diameter of
the Cayley graph of the cube group generated by the quarter face turns
(or quarter face turns and half face turns).

In general an autmorphism alpha of G maps the Cayley graph of G w.r.t.
the generating system < g_1, g_2, ... > to a new Cayley graph of G w.r.t.
the generating system < g_1^alpha, g_2^alpha, ... >.

But in this case, i.e., for the autmorphism of G induced by elements of
M, the sets { g_1, g_2, ... } and { g_1^alpha, g_2^alpha, ... } are
equal.  So the elements of M induce autmorphism of the unlabelled Cayley
graph.

And as I said, M is the largest subgroup of the outer autmorphism group
of G with this property.

Have a nice day.

Martin.

-- .- .-. - .. -.  .-.. --- ...- . ...  .- -. -. .. -.- .-
Martin Sch"onert,   Martin.Schoenert@Math.RWTH-Aachen.DE,   +49 241 804551
Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany