Cayley graph

Missing image
Cayley_graph_of_F_2.png
The Cayley graph of the free group on two generators a and b

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 [itex]G[itex] be a group, and let [itex]S[itex] be a generating set for [itex]G[itex]. The Cayley graph of [itex]G[itex] with respect to [itex]S[itex] has a vertex for every element of [itex]G[itex], with an edge from [itex]g[itex] to [itex]gs[itex] for all elements [itex]g\in G[itex] and [itex]s\in S[itex].

For example, the Cayley graph of the free group on two generators [itex]a[itex] and [itex]b[itex] is depicted to the right. (Note that [itex]e[itex] represents the identity element.) Travelling right along an edge represents multiplying on the right by [itex]a[itex], while travelling up corresponds to multiplying by [itex]b[itex]. 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:

1. If the set [itex]S[itex] doesn't generate the whole group, the Cayley graph isn't connected.
2. In some contexts, left multiplication is used instead of right. That is, edges go from [itex]g[itex] to [itex]sg[itex].
3. In many contexts, the generating set is assumed to be symmetric, meaning that [itex]s^{-1}[itex] is in [itex]S[itex] whenever [itex]s[itex] is. In this case, the graph is undirected.

[itex]G[itex] acts on itself by multiplication on the left. This action induces an action of [itex]G[itex] on its Cayley graph. Explicitly, an element [itex]h[itex] sends a vertex [itex]g[itex] to the vertex [itex]hg[itex], and the edge [itex](g,gs)[itex] to the edge [itex](hg,hgs)[itex]. Since the action of [itex]G[itex] on itself is transitive, any Cayley graph is vertex-transitive.

If one takes the vertices to instead be right cosets of a fixed subgroup [itex]H[itex], 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.

• Art and Cultures
• Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
• Space and Astronomy