Cayley Graphs

From CanisiusmathWiki

Definition

Let G be a group and take any function x from a set S to G (think of this as "selecting" some elements of G to give us arcs). We define a graph X by X0=G and X1=G x S and s(g,x)=g, t(g,x)=gx. So each arc looks like

Why are Cayley graphs important?

• Cayley graphs are kind of beautiful. Maybe because they have lots of symmetry. Lets make this precise?

symmetry

• you get to construct big graphs by putting in arcs "automatically" according to a pattern given by the group multiplication.

• each group gives a lot of different graphs, depending on which elements you select to give arcs.

• speculation: the Cayley graph comes with covering maps to many other graphs; and each of these covering maps tells some information about how the characteristic polynomial of the Cayley graph factors. This gives data about the spectrum of Cayley graphs.

covering maps

• For instance, the Cayley graph X comes with a covering map from from X to B,

where B0=1 and B1=S (B is called a bouquet of loops). This special covering map is called a regular covering.

regular coverings

To build Cayley graphs you need to know some groups. We could include some information about some of the best groups.

groups

Using Mathematica to Generate Cayley Graphs

These processes use the Combinatorica Package and work in Mathematica 6.0 - for Mathematica 5.0 (possibly lower, too), before running the following enter Boole[True] := 1; Boole[False] := 0.

For the Cayley Graph of A₅ generated by the permutation (in cyclic notation) (1 2 5 3 4), enter the following:

MT = Table[Permute[AlternatingGroup[5][[i]], {4, 1, 5, 3, 2}], {i, 1, 60}]
A = AlternatingGroup[5]
B = Table[Boole[MT[[i]] == A[[j]]], {i, 1, 60}, {j, 1, 60}]

ShowGraph[FromAdjacencyMatrix[B, Type->Directed]]

For the Cayley Graph of your favourite permutation on A_5:

MT = Table[Permute[AlternatingGroup[5][[i]], permutation in list form], {i, 1, 60}]
A = AlternatingGroup[5]
B = Table[Boole[MT[[i]] == A[[j]]], {i, 1, 60}, {j, 1, 60}]
ShowGraph[FromAdjacencyMatrix[B, Type->Directed]]

For The Cayley Graph of permutation (in list form) on , try this out:

MT = Table[Permute[G[[i]], permutation], {i, 1, |G|}]
A = G
B = Table[Boole[MT[[i]] == A[[j]]], {i, 1, |G|}, {j, 1, |G|}]
ShowGraph[FromAdjacencyMatrix[B, Type->Directed]]

The Cayley Graph of multiple elements on a group can be achieved by using the GraphSum function, where individual graphs once generated by the above can be saved like G=FromAdjacencyMatrix[B], running again with the second permutation, and H=FromAdjacencyMatrix[B]. To see the full graph, then enter ShowGraph[GraphSum[G, H]]

Here is Mathematica code for producing all the Cayley Graphs for a group with one generator alphabet, which is closed under inverses.

(*Defines the Group in Question*)
Group = CyclicGroup[5];
n     = Length[Group];

(*Makes <<RStone>>, a list of Alphabets closed under inverses*)
Bank   = Rest[Group];
RStone = {};
While[Length[Bank] > 1, Alpha = Take[Bank, 1];
 Alpha  = Append[Alpha, InversePermutation[Alpha[[1]]]];
 RStone = Append[RStone, Alpha];
 Bank   = Delete[Bank, Position[Bank, Alpha[[1]]]];
 Bank   = If[Alpha[[1]] == Alpha[[2]], Bank,Delete[Bank, Position[Bank, Alpha[[2]]]]];]

(*Defines a function that multiplies the element which is the inverse of <<i>> with the element <<j>>*)
gINVSh[i_, j_] :=   Permute[InversePermutation[Group[[i]]], Group[[j]]];

(*Produces the adjacency matrix for a given Alphabet, given by the index in RStone.  
There exists an edge between two vertices if their difference is in the alphabet*)
AdjMat[alphabet_] :=  Table[If[MemberQ[RStone[[alphabet]], gINVSh[i, j]], 1, 0], {i, 1, n}, {j, 1, n}]

(*Creates a table of Cayley Graphs*)
Table[ ShowGraph[FromAdjacencyMatrix[AdjMat[alphabet]]], {alphabet,Length[RStone]}]

Here is some code attempting to create one Cayley Graph. There are serious bugs in it. Sorry.

(*Inialize Stuff*)
Group = CyclicGroup[5];
alphabets = {{5, 1, 2, 3, 4}, {2, 3, 4, 5, 1}};
ClosedUnderInverses = True;

(*Some program constants*)
n = Length[Group];

(* Closes the Alphabet if nessasary*)
If[ClosedUnderInverses,
  RStone = alphabets
    While[Length[RStone] > 1,
     Alpha = Take[RStone, 1];
     Alpha = Append[Alpha, InversePermutation[Alpha[[1]]]];
     alphabets = Append[alphabets, Alpha];
     RStone = Delete[RStone, Position[RStone, Alpha[[1]]]]], 0];

(*Defines a function that multiplies the element <<j>> with the inverse of <<i>*)
gINVSh[i_, j_] := 
  Permute[InversePermutation[Group[[i]]], Group[[j]]];

(*Produces the adjacency matrix for a given Alphabet.  
There exists an edge between two vertices if their difference is in the alphabet*)
AdjMat[alphabet_] := 
 Table[If[MemberQ[alphabet, gINVSh[i, j, Group]], 1, 0], {i, 1,n}, {j, 1, n}]

(*Given some alphabets, this will compile their combined adjacency matrix*)
totalMat = Table[0, {i, 1, n}, {j, 1, n}];
For[i = 1, i < Length[alphabets], i++,
 totalMat = totalMat + AdjMat[alphabets[[i]]]]

(*Makes the Cayley Graph*)
ShowGraph[FromAdjacencyMatrix[totalMat]]