⭕Geometric Group Theory Unit 3 – Cayley Graphs and Word Metric

Definition and Basics

• Cayley graphs visually represent the structure of a group and how its elements relate to each other through generators
• Given a group $G$ and a generating set $S$, the Cayley graph $\Gamma(G,S)$ is a directed graph where vertices correspond to elements of $G$ and edges represent multiplication by generators from $S$
• The generating set $S$ is typically chosen to be symmetric, meaning if $s \in S$, then $s^{-1} \in S$ as well
• Cayley graphs are named after the mathematician Arthur Cayley who introduced the concept in the late 19th century
• The choice of generating set affects the structure and properties of the resulting Cayley graph
  • A smaller generating set leads to a sparser graph with fewer edges
  • A larger generating set results in a denser graph with more connections between vertices
• Cayley graphs are regular graphs, meaning every vertex has the same degree (number of incoming and outgoing edges)
• The degree of each vertex in a Cayley graph equals the cardinality of the generating set $|S|$

Group Actions and Cayley Graphs

• Group actions play a crucial role in the construction and analysis of Cayley graphs
• A group $G$ acts on its Cayley graph $\Gamma(G,S)$ by left multiplication, meaning for any $g \in G$ and vertex $v$ in the graph, $g \cdot v$ is the vertex reached by following the edge labeled $g$ from $v$
• The action of $G$ on its Cayley graph is regular, meaning it acts transitively (any vertex can be mapped to any other vertex) and freely (no non-identity element fixes a vertex)
• The regularity of the action implies that Cayley graphs are vertex-transitive, meaning they look the same from the perspective of any vertex
• The group action on the Cayley graph preserves the graph's structure and symmetries
• Studying the properties of the group action on the Cayley graph can reveal important characteristics of the underlying group, such as its subgroup structure and quotient groups
• The Cayley graph can be viewed as a geometric realization of the group action, providing a visual representation of how elements of the group interact with each other

Properties of Cayley Graphs

• Cayley graphs have several important properties that make them useful tools in geometric group theory
• Connectedness: Cayley graphs are always connected, meaning there is a path between any two vertices in the graph
  • This follows from the fact that the generating set $S$ generates the entire group $G$
• Vertex-transitivity: As mentioned earlier, Cayley graphs are vertex-transitive due to the regular action of $G$ on the graph
• Edge-coloring: Cayley graphs can be edge-colored according to the generators in $S$, with each generator assigned a distinct color
  • This coloring is useful for visualizing the structure of the group and studying paths in the graph
• Embedding into Cayley graphs: Subgroups of $G$ can be embedded into the Cayley graph as induced subgraphs
  • The Cayley graph of a subgroup $H \leq G$ with respect to the generating set $S \cap H$ is an induced subgraph of $\Gamma(G,S)$
• Cayley graphs are homogeneous spaces, meaning the graph looks the same around any vertex
• The automorphism group of a Cayley graph contains a subgroup isomorphic to the original group $G$, reflecting the symmetries of the graph

Word Metric and Distance

• The word metric on a group $G$ with respect to a generating set $S$ is a metric that measures the distance between elements of the group
• For any two elements $g, h \in G$, the word metric distance $d_S(g,h)$ is defined as the length of the shortest word in the generators $S$ that represents the element $g^{-1}h$
  • In other words, $d_S(g,h)$ is the minimum number of generators needed to express $g^{-1}h$
• The word metric can be visualized on the Cayley graph $\Gamma(G,S)$ as the shortest path distance between vertices corresponding to $g$ and $h$
• The word metric satisfies the axioms of a metric space:
  • Non-negativity: $d_S(g,h) \geq 0$ for all $g,h \in G$
  • Symmetry: $d_S(g,h) = d_S(h,g)$ for all $g,h \in G$
  • Triangle inequality: $d_S(g,h) \leq d_S(g,k) + d_S(k,h)$ for all $g,h,k \in G$
• The word metric depends on the choice of generating set $S$
  • Different generating sets may yield different word metric distances between the same pair of elements
• The diameter of a Cayley graph is the maximum word metric distance between any two vertices in the graph
• The word metric provides a way to study the large-scale geometry of the group and its Cayley graph, as it encodes information about the shortest paths and distances between elements

Geometric Features

• Cayley graphs exhibit various geometric features that reflect the properties of the underlying group
• Curvature: The curvature of a Cayley graph can be defined using combinatorial or coarse geometric notions
  • Positively curved Cayley graphs correspond to finite groups
  • Negatively curved Cayley graphs are associated with hyperbolic groups
  • Flat Cayley graphs arise from abelian groups or groups with a finite index abelian subgroup
• Hyperbolicity: A group is hyperbolic if its Cayley graph satisfies a thin triangles condition
  • Hyperbolic groups have Cayley graphs that resemble trees on a large scale
  • The word problem is solvable in linear time for hyperbolic groups using the word metric
• Amenability: A group is amenable if it admits a finitely additive, left-invariant probability measure
  • The Følner condition characterizes amenability in terms of the existence of sets in the Cayley graph with small boundary compared to their size
• Growth: The growth function of a group measures how the number of elements in the group grows with respect to the word metric
  • Polynomial growth corresponds to virtually nilpotent groups (Gromov's theorem)
  • Exponential growth is associated with non-amenable groups and implies the group contains a free subgroup (Tits alternative)
• Ends: The ends of a Cayley graph describe its connectivity at infinity
  • The number of ends is a quasi-isometry invariant of the group
  • Groups with more than one end are characterized by Stallings' theorem

Applications in Group Theory

• Cayley graphs and the word metric have numerous applications in group theory and related areas
• Solving the word problem: The word problem asks whether two words in the generators represent the same group element
  • The word metric provides a way to solve the word problem by comparing the distances between words
• Studying subgroups and quotients: Cayley graphs can be used to study the subgroup structure of a group and visualize quotient groups
  • Normal subgroups correspond to regular coverings of the Cayley graph
  • Quotient groups can be realized as Cayley graphs with respect to the image of the generating set under the quotient map
• Quasi-isometry classification: Cayley graphs can be used to define a quasi-isometry equivalence relation on groups
  • Quasi-isometric groups have Cayley graphs that look similar on a large scale
  • Quasi-isometry invariants, such as growth, ends, and hyperbolicity, can be used to classify groups
• Geometric methods in group theory: Cayley graphs provide a bridge between group theory and geometry
  • Geometric techniques, such as the study of geodesics, boundaries, and actions on metric spaces, can be applied to Cayley graphs to prove results about groups
• Connections to other areas: Cayley graphs and the word metric have applications in other areas, such as
  • Computer science (e.g., expander graphs, error-correcting codes)
  • Topology (e.g., covering spaces, fundamental groups)
  • Representation theory (e.g., Kazhdan's property (T))

Examples and Exercises

• Example 1: The Cayley graph of the cyclic group $\mathbb{Z}_n$ with generating set $S = \{1, -1\}$ is a cycle graph on $n$ vertices
• Example 2: The Cayley graph of the free group $F_2 = \langle a, b \rangle$ with generating set $S = \{a, a^{-1}, b, b^{-1}\}$ is an infinite 4-regular tree
• Example 3: The Cayley graph of the dihedral group $D_{2n}$ with generating set $S = \{r, s\}$, where $r$ is rotation and $s$ is reflection, is an $n$-sided polygon with diagonals
• Exercise 1: Prove that the Cayley graph of a group $G$ with respect to a generating set $S$ is connected if and only if $S$ generates $G$
• Exercise 2: Show that the word metric on a group $G$ with respect to a generating set $S$ is left-invariant, i.e., $d_S(g,h) = d_S(kg, kh)$ for all $g,h,k \in G$
• Exercise 3: Construct the Cayley graph of the quaternion group $Q_8$ with respect to the generating set $S = \{i, j\}$
• Exercise 4: Prove that a group $G$ is finite if and only if its Cayley graph with respect to any generating set is a finite graph
• Exercise 5: Show that the Cayley graph of the free abelian group $\mathbb{Z}^n$ with respect to the standard generating set is the integer lattice in $\mathbb{R}^n$

Advanced Concepts and Extensions

• Cayley complexes: Cayley complexes are higher-dimensional analogues of Cayley graphs that encode the structure of a group and its relations
  • They are constructed by attaching higher-dimensional cells to the Cayley graph according to the relators in a group presentation
• Dehn functions: The Dehn function of a group measures the complexity of the word problem by quantifying the area of minimal disk diagrams filling loops in the Cayley complex
  • The Dehn function is a quasi-isometry invariant and is connected to the geometry and complexity of the group
• Automatic groups: A group is automatic if it admits a rational language of normal forms that satisfy certain fellow traveler properties with respect to the word metric
  • Automatic groups have efficiently solvable word problem and exhibit nice geometric properties
• Asymptotic cones: The asymptotic cone of a group is a limit object obtained by rescaling the Cayley graph by larger and larger distances
  • Asymptotic cones capture the large-scale geometry of the group and are quasi-isometry invariants
• Random walks on Cayley graphs: The study of random walks on Cayley graphs provides insights into the geometry and spectral properties of the group
  • Properties such as the speed of escape, return probabilities, and harmonic functions can be analyzed using random walk techniques
• Cayley graphs of semigroups: The concept of Cayley graphs can be extended to semigroups, which are sets with an associative binary operation but not necessarily an identity or inverses
  • Cayley graphs of semigroups have directed edges and may not be regular or connected
• Generalizations to other structures: The idea of Cayley graphs can be generalized to other algebraic structures, such as monoids, rings, and algebras
  • These generalizations lead to the study of Cayley digraphs, Cayley-Abels graphs, and Schreier coset graphs