Cayley graph

- group, ∞-group
- group object, group object in an (∞,1)-category
- abelian group, spectrum
- group action, ∞-action
- representation, ∞-representation
- progroup
- homogeneous space

The *Cayley graph* (also called the *Cayley quiver*) of a group, $G$ with a given set of generators, $X$, encodes how the chosen generating elements operate (by multiplication) on the elements of the group.

Given a group, $G$, and a set of generators, $X$, which we regard as a subset of the underlying set $|G|$ of $G$, we can form a directed graph with the elements of $G$ as the vertices and with its edges labelled (some people say ‘coloured’) by the elements of $X$ with an edge joining a vertex, $g$, to the vertex $g x$ labelled by $x$

$g \overset{x}{\longrightarrow} g x$

This graph is called the *Cayley graph* of the group, $G$, relative to the set of generators.

Consider one of the standard presentations of $S_3$, $(a,b : a^3, b^2, (a b)^2)$. Write $r = a^3$, $s = b^2$, $t = (ab)^2$.

The Cayley graph is easy to draw. There are two triangles corresponding to $1 \to a \to a^2$ and to its translate by $b$, $b \to a b \to a^2 b$, flipping the orientation of the second, and three 2-cycles, $1\to b\to 1$, $a\to a b\to a$ and $a^2\to a^2b\to a^2$.

To understand the geometric significance of this graph we compare the algebraic information in the presentation with the homotopical information in the graph (considered as a CW-complex).

Looking at the presentation it leads to a free group, $F$, on the generators, $a$ and $b$, so $F$ is free of rank 2, but the normal closure of the relations $N(R)$ is a subgroup of $F$, so it must be free as well, by the Nielsen-Schreier theorem. Its rank will be 7, given by the Schreier index formula.

Looked at geometrically, this will be the fundamental group of the Cayley graph, of the presentation. This group is free on generators corresponding to edges outside a maximal tree, and, of course, there are 7 of these.

See also:

- Wikipedia,
*Cayley graph*

On distances in Cayley graphs:

For symmetric groups (permutations):

- Mohammad Hossein Ghaffri, Zohreh Mostaghim,
*Distance in Cayley graphs on permutations generated by $k m$ cycles*, Transactions on Combinatorics, Vol 6 No. 3 (2017) (pdf)

Last revised on February 9, 2020 at 06:29:27. See the history of this page for a list of all contributions to it.