Cayley graph
From Free net encyclopedia
In mathematics, a Cayley graph, 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.
Let <math>G</math> be a group, and let <math>S</math> be a generating set for <math>G</math>. The Cayley graph of <math>G</math> with respect to <math>S</math> has a vertex for every element of <math>G</math>, with an edge from <math>g</math> to <math>gs</math> for all elements <math>g\in G</math> and <math>s\in S</math>.
Contents |
Example
For example, the Cayley graph of the free group on two generators <math>a</math> and <math>b</math> is depicted to the right. (Note that <math>e</math> represents the identity element.) Travelling right along an edge represents multiplying on the right by <math>a</math>, while travelling up corresponds to multiplying by <math>b</math>. Since the free group has no relations, the graph has no cycles.
Variations
The above definition gives a connected, directed graph. There are a number of slight variations on the definition:
- Usually <math>S</math> is not allowed to contain the identity element <math>e</math>.
- If the set <math>S</math> doesn't generate the whole group, the Cayley graph isn't connected.
- In some contexts, left multiplication is used instead of right. That is, edges go from <math>g</math> to <math>sg</math>.
- In many contexts, the generating set is assumed to be symmetric, meaning that <math>s^{-1}</math> is in <math>S</math> whenever <math>s</math> is. In this case, the graph is undirected.
The Sabidussi Theorem
<math>G</math> acts on itself by multiplication on the left. This action induces an action of <math>G</math> on its Cayley graph. Explicitly, an element <math>h</math> sends a vertex <math>g</math> to the vertex <math>hg</math>, and the edge <math>(g,gs)</math> to the edge <math>(hg,hgs)</math>. Since the action of <math>G</math> on itself is transitive, any Cayley graph is vertex-transitive. The Sabidussi theorem gives a characterization of Cayley graphs: Graph <math>X</math> is a Cayley graph if and only if the automorphism group of <math>X</math> contains a subgroup <math>G</math> acting regularly on the vertex set of <math>X</math>.
Schreier coset graph
If one takes the vertices to instead be right cosets of a fixed subgroup <math>H</math>, one obtains a related construction, the Schreier coset graph, which is at the basis of coset enumeration or the Todd-Coxeter process.
Connection to graph 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 <math>C_n</math> is a Cayley graph for the cyclic group <math>Z_n</math>. Therefore the cartesian product <math> C_n \square C_m </math>, (an n by m grid on torus) is a Cayley graph for the direct product <math> Z_n \times Z_m</math>.