Definition 12.2.1 (Cayley graph). Given a group with generators , the Cayley graph of has:
Vertices: the elements of .
Edges: for each and generator , a directed edge from to , labeled .
Note. acts on its Cayley graph by left multiplication: sends vertex to and edge to . This action is transitive on vertices and preserves the graph structure (it is a graph automorphism). The graph is highly symmetric.
Example 12.2.1 (Cayley graph of ). With generator , the Cayley graph is the integer number line:
Example 12.2.2 (Cayley graph of ). With generators and : the 6 vertices form a hexagonal graph. The relation corresponds to the outer hexagonal cycle closing up.
Since any word in with reduces to an alternating sequence , we verify .
Example 12.2.3 (Cayley graph of ). With generators for : the 24 vertices form the edge graph of a truncated octahedron (a permutohedron). The faces correspond to the relations: hexagonal faces to and square faces to .
Definition 12.2.2 (Word length). The word length of (with respect to generators ) is the shortest distance from to in the Cayley graph, i.e., the minimal number of generators or their inverses needed to express .
Note. For with generators , the word length of a permutation equals the number of inversions . The longest element is with word length .
12.2.1 Growth Rate
For infinite groups, the Cayley graph encodes asymptotic information about the group.
Definition 12.2.3 (Growth rate). Given generators of an infinite group , the growth function counts . The group has polynomial growth if for some , and exponential growth if for some .
Note. The growth type (polynomial vs exponential) is independent of the choice of generators: changing generators changes word lengths by at most a bounded factor (each new generator is a bounded-length word in the old generators and vice versa). Finitely generated abelian groups have polynomial growth. Free groups have exponential growth. Gromov’s theorem (1981) characterizes polynomial growth: a finitely generated group has polynomial growth iff it is virtually nilpotent (has a nilpotent subgroup of finite index).