Chapter 3. Cayley Graphs

Table of Contents

Cayley Graphs
The Higman-Sims Graph
The 600-Cell
Cubelike Graphs

Cayley Graphs

If $G$ is a group and $C\sbs G$ (i.e., a list of some elements of $G$), then we can produce the Cayley graph $X(G,C)$:

G = DihedralGroup(5)
C = [G.gen(0), G.gen(1)]
CG = G.cayley_graph( generators = C)
CG.show()  # not tested

The output is a directed graph, even if $C$ is inverse-closed; in the latter case we can convert $G$ to a graph by

CGU = CG.to_undirected()
CGU.show()  # not tested

Note that $C$ is not required to generate $G$. There are a number of keywords to this command (for example, side and simple) but I cannot follow their documentation and so I do not know what they do.

Note that the Graph() command makes it easy to construct Cayley graphs ourselves. For example, a cubelike graph is a Cayley graph for $GF(2)^d$. We can construct them using Graph().

def cubelike(d, vector_list):
    VS = VectorSpace(GF(2),d)
    vxs = range(2^d)
    return Graph([vxs, lambda i,j: VS[i]-VS[j] in vector_list])

Here vector_list is a list of 01-vectors of length $d$.

V = GF(2)^5
vl = [V([0,1,1,0,0]), V([1,1,0,1,1]), V([1,0,0,0,1])]         
T = cubelike(5, vl)                                   
show(T, layout='circular')  # not tested                      



For a general group, we can use the following construction to create an undirected Cayley graph.

G = DihedralGroup(5)
C = [G.gen(0), G.gen(0)^-1, G.gen(1), G.gen(1)^-1]
CG = Graph( [ G.list(), lambda g, h: h*g^(-1) in C])
CG.show()  # not tested



This will produce an incorrect result if $C$ is not inverse-closed.

Sage provides access to GAP, and hence access to any group that is in GAP or can be constructed in GAP. Be warned that the documentation for GAP probably outweighs that for Sage.