Cayley graph

A Cayley graph turns multiplication in a group into travel: the chosen generators of a group are the allowed one-step moves, and a word over an alphabet becomes a route. This lets us study a finitely generated group using graph distances, closed balls, and geodesics, rather than only equations between products.

Let $G$ be a group with a finite generating set of a group $S$ satisfying $S=S^{-1}$ and $1\notin S$. Such a symmetric subset of a group includes the inverse element of every allowed move. The Cayley graph ${\mathrm{Cay}}_S(G)$ has vertex set $G$ and joins $g$ to $gs$ for each $s\in S$. We choose right multiplication for these moves. Reversing the move uses $s^{-1}$, so for graph distance we regard $g\to gs$ and $gs\to g$ as the two orientations of one undirected edge. An involution therefore gives one edge, not two parallel edges. Each edge has length one, regardless of its length in a drawing.^[ref]

A sequence $s_1,\dots ,s_n$ labels the walkIt ends at $h$ exactly when $g^{-1}h=s_1\cdots s_n$. Thus the Cayley graph is a connected graph precisely because $S$ generates $G$, and its graph distance on vertices is the word metric. Left multiplication by $a$ sends the edge from $g$ to $gs$ to the edge from $ag$ to $(ag)s$, preserving its generator label: this is a group action by graph automorphisms and isometries. Viewing groups as symmetries of geometric objects is the motivation of Clay and Margalit's introduction.^[ref]

The useful geometric object includes its allowed moves, not just its drawing. Cayley graphs of the integers show how changing the moves adds shortcuts; word metric balls in the integer lattice show how the same group can acquire visibly different closed balls. Meier's book develops this passage from group operations to graphs as its central motivation.^[ref]

For the additive infinite cyclic group $\mathbb{Z}$, the generating set of a group $S=\{-1,1\}$ produces the infinite line: each integer $n$ is adjacent to $n-1$ and $n+1$. Adding the moves $\pm 2$ gives $T=\{-2,-1,1,2\}$ and additional edges skipping one vertex. Each skip still costs one step in the word metric.

For integers $a,b$, these word metrics areThe absolute value counts unit moves, and the ceiling function counts pairs plus a possible leftover unit. Every $T$-move changes the integer by at most two, while moves of size two followed by at most one move of size one attain this bound. For example, the graph path $0,1,2,3,4,5$ has five steps for $S$, while $0,2,4,5$ has three for $T$. This calculation gives the concrete comparison

The picture shows only a finite window of each infinite Cayley graph. By contrast, $U=\{-2,2\}$ alone fails to be a generating set of a group for $\mathbb{Z}$: it generates the subgroup $2\mathbb{Z}$. Its move graph has two connected components of a graph, the even integers and the odd integers. Within either component the graph distance is $|a-b|/2$; between different components no finite graph path exists. Adding a shortcut is different from deleting the moves needed for connectivity.

For a group $G$, a subgroup $H$, and a generating set $S$, the Schreier graph has the left cosets $G/H$ as vertices and an edge from $gH$ to $sgH$ for each $s\in S$. Its radius-$m$ ball records the cosets met by $S^m$.

For a finite group $G$ with a symmetric generating set $S$, its diameter isEquivalently, it is the diameter of the Cayley graph ${\mathrm{Cay}}_S(G)$.

A connected Cayley graph on a finite group $G$ has $|G|$ vertices, and a shortest path repeats no vertex. Therefore

For every $\epsilon >0$ there is $\lambda (\epsilon )$ such that every non-abelian finite simple group $G$ and every finite symmetric generating set $S$ containing the identity satisfyThe proof applies the one-scale virtual nilpotence theorem below the diameter and then uses simplicity to eliminate both the bounded-index subgroup and the finite normal subgroup.

The word metric measures how many allowed moves are needed to change one group element into another. For a finite symmetric generating set of a group $S$ with $1\notin S$, it is the graph distance between vertices of the Cayley graph, equivalentlyHere word length counts letters in a shortest representative of $g^{-1}h$. The path metric on the entire Cayley graph also permits points inside edges; the word metric is its restriction to the group itself.^[ref]

The word metric is left invariant:This corresponds to the label-preserving group action on the Cayley graph. Symmetry follows by reversing a shortest graph path; concatenating routes gives the triangle inequality.^[ref]

Right invariance can fail in a non-abelian group, because right multiplication replaces $g^{-1}h$ by $a^{-1}{g}^{-1}ha$ through conjugation. In the free group $F(x,y)$ with $S=\{x,x^{-1},y,y^{-1}\}$, we have $d_S(1,y)=1$, whereas $d_S(x,yx)=|x^{-1}yx{|}_S=3$: the latter freely reduced word has three letters. In an abelian group, conjugation fixes each element, so right invariance does hold. Cayley graphs of the integers and word metric balls in the integer lattice give examples where the word metric can be calculated explicitly.

The closed word metric ball of radius $r\ge 0$ centred at a group element $g$ isThis is a closed ball for the word metric. A finite generating set of a group gives a finite word metric ball, because at most ${\sum }_{k=0}^{\lfloor r\rfloor }|S{|}^k$ words over an alphabet can represent its elements. Different words over an alphabet may represent the same element, so this is an upper bound. Word metric balls in the integer lattice give exact counts for two choices of moves.

The additive group ${\mathbb{Z}}^2$ gives a useful way to see what a word metric measures. Let $e_1=(1,0)$ and $e_2=(0,1)$, and choose the four-move generating set of a group $S=\{\pm e_1,\pm e_2\}$. Its Cayley graph is the square lattice. Each move changes exactly one coordinate by one, so the word length is the L1 norm, and the word metric is Manhattan distance:At least this many moves are necessary, and moving horizontally then vertically attains the bound. Bridson gives this square lattice as a basic Cayley graph example.^[ref]

Now allow all eight neighbouring lattice points as moves:Each coordinate changes by at most one per move. Use diagonal moves until the smaller displacement is exhausted, then use axis moves: the resulting word length is the maximum norm, and the word metric is Chebyshev distance. From $(0,0)$ to $(2,3)$, an $S$-route has five steps, while the $T$-route $(0,0),(1,1),(2,2),(2,3)$ has three.

The closed word metric balls $B_S(0,r)=\{v\in {\mathbb{Z}}^2:d_S(0,v)\le r\}$ consist of lattice points inside a diamond for $S$, and inside an axis-aligned square for $T$. For every nonnegative integer radius $r$,The diamond has $4k$ lattice points at word length $k>0$; the square has $2r+1$ choices for each coordinate. At radius three the counts are $25$ and $49$. These are discrete closed balls for Manhattan distance and Chebyshev distance; an Euclidean distance bound would instead select lattice points inside a Euclidean disk.

The word length is the cost of building a group element from the allowed generators of a group. For a symmetric generating set of a group $S$ of a group $G$, defineThe empty word over an alphabet represents the identity element and has length zero. A representative with this least number of letters labels a shortest graph path from $1$ to $g$ in the Cayley graph. Thus word length minimizes over all representatives, rather than counting the letters in whichever expression we happened to write down.^[ref]

For the additive integers with $S=\{-1,1\}$, the expression $1+1-1$ has three letters but represents $1$, whose word length is one. With $T=\{-2,-1,1,2\}$, the integer $5$ has word length three, realized by $2+2+1$. The Cayley graphs of the integers visualize why these are minimal. A freely reduced word is always shortest in a free group with its free generators and their inverses; free reduction alone need not give a shortest representative in a general group.

Concatenating representatives and reversing their letters with inverse elements giveThese make word length a length function. A finite $S$ gives finite word metric balls, since only finitely many words over an alphabet have length at most a fixed radius. The definition itself also works for infinite symmetric generating sets of a group; the bounded-metric example in equivalence of finite word metrics shows what finiteness adds.

For a word metric from a finite generating set, the stable word length isSubadditivity and the Fekete lemma give the limit. Conjugating $g^n$ changes its length by at most a constant, so stable word length is conjugacy invariant. It satisfies ${\tau }_S(g^k)=|k|{\tau }_S(g)$. Finite-order elements have zero stable word length; in a hyperbolic group, every infinite-order element has positive stable word length.

Changing a finite generating set of a group changes individual distances, but it cannot introduce arbitrarily large relative distortion. For two finite symmetric generating sets of a group $S,T$ of the same group, setEach $S$-letter can be replaced by at most $K$ $T$-letters, and conversely each $T$-letter by at most $L$ $S$-letters. Applying these substitutions to shortest representatives of $g^{-1}h$ givesThus the identity map is a bilipschitz equivalence between the two word metrics, and hence a quasi-isometry. The constants depend on the chosen generating sets of a group.^[ref]

In the Cayley graphs of the integers example, $S=\{-1,1\}$ and $T=\{-2,-1,1,2\}$ give $K=1$ and $L=2$: a unit move costs one in either alphabet, and a move of size two costs two unit moves. This recovers $d_T\le d_S\le 2d_T$. The diamond and square in word metric balls in the integer lattice obey the same comparison, because $\max \{|m|,|n|\}\le |m|+|n|\le 2\max \{|m|,|n|\}$.

Finiteness cannot simply be dropped from this universal statement. For the additive integers, take the infinite symmetric generating set of a group $U=\mathbb{Z}\setminus \{0\}$. Every nonzero displacement is a single allowed move, so $d_U(a,b)=1$ whenever $a\ne b$, whereas $d_S(0,n)=|n|$ for $S=\{-1,1\}$. There is no finite $L$ with $d_S\le L{d}_U$: choosing an integer $n>L$ violates it. This is a counterexample to unrestricted equivalence, not a claim that every infinite generating set of a group fails; two such sets with uniformly bounded generator lengths can still satisfy the same substitution bounds.^[ref]

The undirected infinite line is both the Cayley graph of the infinite cyclic group $\mathbb{Z}$ with generating set $\{1\}$ and the Cayley graph of the infinite dihedral group $C_2\ast C_2$ with its two involutory generators. Thus an unlabelled Cayley graph need not determine its group.