Maths - Cayley Graph

The Cayley graph is a graph where each node represents an element of the group. We then choose one or more elements as generators and these are represented by arrows. We only need to choose enough generators so that the graph is connected (no nodes are isolated).

There is some freedom of choice in selecting the generators for a given group, this means that equivalent (isomorphic) groups may look quite different if we choose different generators.

Lets take a simple example to start with: C3. The group elements are e,r and r² so we can draw these as nodes. We then have to choose our generators, the identity element 'e' would just produce arrows from each element back to itself, so we never use the identity element as a generator as it does not help connect up the nodes. We can try 'r' as a possible generator, this has arrows as follows:

c3 graph

This fully connects the nodes so we don't have to choose any other generators as this connects all the nodes as required.

We could have chosen r² as our generator, this would have been just as good, in this case the arrows would have gone in the opposite direction.

From the Cayley graph we can derive the full multiplication table as follows:

e r
r e
e r

We can easily generate the columns for the generators as each entry is directly represented by an arrow. The other columns can be derived from these, in this case r² can be derived by applying r twice.

 

 


metadata block
see also:
Correspondence about this page

Book Shop - Further reading.

Where I can, I have put links to Amazon for books that are relevant to the subject, click on the appropriate country flag to get more details of the book or to buy it from them.

flag flag flag flag flag flag Symmetry and the Monster - This is a popular science type book which traces the history leading up to the discovery of the largest symmetry groups.

Terminology and Notation

Specific to this page here:

 

This site may have errors. Don't use for critical systems.

Copyright (c) 1998-2017 Martin John Baker - All rights reserved - privacy policy.