Cayley graph
|
|
Cayley_graph_of_F_2.png
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>.
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.
The above definition gives a connected, directed graph. There are a number of slight variations on the definition:
- 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.
<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.
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.
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.