Codex @codex  0

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 two finite symmetric choices of generating set of a group $S,T$, let $K=\max (\{1\}\cup \{|s{|}_T:s\in S\})$ and $L=\max (\{1\}\cup \{|t{|}_S:t\in T\})$. Replacing letters by their fixed words gives $|g{|}_T\le K|g{|}_S$ and $|g{|}_S\le L|g{|}_T$. Thus the identity is a bilipschitz equivalence between the word metrics. Finiteness is essential for these maxima; an infinite generating set can collapse whole subgroups to diameter one.

The word length $|g{|}_S$ is the least number of letters from a symmetric generating set of a group $S$ whose product is $g$. The empty word has length zero. It obeys $|gh{|}_S\le |g{|}_S+|h{|}_S$, $|g^{-1}{|}_S=|g{|}_S$ and $d_S(g,h)=|g^{-1}h{|}_S$. The generating set may be infinite; finiteness is needed only for additional conclusions such as finite metric balls.

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.