Cayley graph
From Wikipedia, the free encyclopedia
In mathematics, a Cayley graph (also known as a Cayley colour graph and named after Arthur Cayley), is a graph that encodes the structure of a group. It is a central tool in combinatorial and geometric group theory.
Given a group G, with a generating set S, then the Cayley colour graph is constructed as follows.
- Each element gi of G is assigned a vertex vi
- Each element si of S is assigned a colour ci
- Then there is a directed edge of colour ci from v1 to v2 if g2 = g1 * si
Alternatively, the lines can be distinguished by the direction they are drawn in, rather than their colour. (This is not always geometrically possible on a plane). In some contexts, left multiplication is used instead of right. That is, edges go from g to sg.
Contents |
[edit] Properties
- As the generating set of a group is in general not unique, so the structure of the Cayley graph is not unique.
- If the generating set has n elements, then each vertex will have n directed edges leading in, and n leading out. (This is a consequence of the group's operation having an inverse, and the operation being closed, respectively).
- Closed walks within the graph indicate relations defined on the generating set.
- If a member of the generating set is symmetric, (s − 1 is in S whenever s is), then the directed edges corresponding to s and s − 1 are generally replaced by a single undirected edge.
- Usually S is not allowed to contain the identity element, e. If it does, then each vertex has an edge that just goes from itself to itself.
- If the set S doesn't generate the whole group, the Cayley graph isn't connected.
[edit] Examples
The Cayley graph of the dihedral group D4 on two generators α and β is depicted to the right. Red arrows represent left-multiplication by element α. Since element β is self-inverse, the blue lines which represent left-multiplication by element β are undirected. Therefore the graph is mixed: it has eight vertices, eight arrows, and four edges.
The Cayley table of the group D4 can be derived from the group presentation 
.
The Cayley graph of the free group on two generators a and b is depicted at the top of the article. (Note that e represents the identity element.) Travelling along an edge to the right represents multiplying on the right by a; while travelling up along an edge corresponds to multiplying by b. Since the free group has no relations, the graph has no cycles.
[edit] The Sabidussi Theorem
G acts on itself by multiplication on the left. This action induces an action of G on its Cayley graph. Explicitly, an element h sends a vertex g to the vertex hg, and the edge (g,gs) to the edge (hg,hgs). Since the action of G on itself is transitive, any Cayley graph is vertex-transitive. The Sabidussi theorem gives a characterization of Cayley graphs: Graph X is a Cayley graph if and only if the automorphism group of X contains a subgroup G acting regularly on the vertex set of X.
[edit] Schreier coset graph
If one, instead, takes the vertices to be right cosets of a fixed subgroup H, one obtains a related construction, the Schreier coset graph, which is at the basis of coset enumeration or the Todd-Coxeter process.
[edit] Connection to group theory
Insights into the structure of the group can be obtained by studying the adjacency matrix of the graph and in particular applying the theorems of spectral graph theory.
A standard Cayley graph for the direct product of groups is the cartesian product of the corresponding Cayley graphs. For instance, a cycle Cn is a Cayley graph for the cyclic group Zn. Therefore the cartesian product Cn ◻ Cm, (an n by m grid graph on a torus) is a Cayley graph for the direct product Zn × Zm.
