Cayley graph

In group theory, a Cayley graph (or Cayley diagram) of a group $G$ with respect to a generating set $S \subseteq G$ (not containing the identity) is a directed graph with vertex set $G$, where there is a directed edge from vertex $g$ to vertex $gs$ labeled by $s$, for every $g \in G$ and $s \in S$.^[1] If $S$ is closed under inversion (i.e., $s^{-1} \in S$ whenever $s \in S$), the graph is often considered undirected, with edges connecting $g$ and $gs$ for each $s \in S$.^[2] This construction encodes the algebraic structure of the group into a graphical form, allowing paths in the graph to correspond to products of generators, which represent group elements.^[3] The concept was introduced by the English mathematician Arthur Cayley in 1878, in a short note on graphical representations of groups, where he illustrated finite substitution groups using diagrams that connect group elements via generators.^[4] Cayley graphs are always regular graphs of degree $|S|$, and they are vertex-transitive, meaning the automorphism group acts transitively on the vertices, reflecting the group's left-regular action on itself.^[1] These properties make Cayley graphs fundamental tools in geometric group theory, where the graph's metric (shortest path distance) defines a word metric on the group, quantifying "distance" between elements in terms of generator lengths.^[5] Cayley graphs have wide-ranging applications across mathematics and computer science. In combinatorics and algebra, they facilitate the study of group properties like Hamiltonicity and connectivity, with many well-known graphs (e.g., hypercubes, butterflies, and cube-connected cycles) arising as Cayley graphs of specific groups.^[6] In theoretical computer science, they model interconnection networks for parallel computing due to their symmetry and efficiency in routing, and serve as explicit constructions of expander graphs, which are crucial for derandomization, pseudorandom generators, and error-correcting codes.^[7] Additionally, Cayley graphs underpin algorithms for problems like the discrete logarithm in cryptography and provide frameworks for analyzing word problems in groups.^[8]

Fundamentals

Definition

A group $G$ is an algebraic structure consisting of a set equipped with a binary operation that satisfies closure, associativity, identity, and invertibility axioms. A generating set $S$ for $G$ is a subset such that every element of $G$ can be written as a finite product of elements from $S$ and their inverses. $$] The Cayley graph of a group $G$ with respect to a finite generating set $S \subseteq G$, denoted $\mathrm{Cay}(G, S)$ or $\Gamma(G, S)$, is the graph with vertex set $G$.[$$ ^[2] When $S$ is symmetric ($S = S^{-1}$) and excludes the identity element of $G$, the graph is undirected, with an edge between distinct vertices $g, h \in G$ if and only if $h = gs$ for some $s \in S$ (equivalently, undirected edges $\{g, gs\}$ for all $g \in G$ and $s \in S$).

\] [](https://ajc.maths.uq.edu.au/pdf/25/ajc-v25-p73.pdf) This construction yields a simple graph without loops or multiple edges under these assumptions, as left multiplication by $g$ is bijective and the identity is absent.\[

^[2] If $S$ is not symmetric, the Cayley graph is instead defined as directed, with a directed edge from $g$ to $gs$ for each $g \in G$ and $s \in S$; the underlying undirected graph may then exhibit asymmetries not captured by the standard undirected form.

\] [](https://mathworld.wolfram.com/CayleyGraph.html) Including the identity in $S$ introduces loops at every vertex, while non-inverse-closed $S$ in an undirected context can lead to multiple edges if both directions are forcibly added without symmetry.\[

^[9] The Cayley graph $\mathrm{Cay}(G, S)$ is $|S|$-regular, with every vertex having degree exactly $|S|$:

$$\deg(v) = |S| \quad \forall \, v \in G.$$

\] [](https://math.osu.edu/sites/math.osu.edu/files/Cayley.pdf) This regularity follows directly from the [group action](/page/Group_action), and the graph is vertex-transitive.\[

^[10]

Examples

The Cayley graph of the cyclic group $\mathbb{Z}_n$ with generating set $S = \{1, n-1\}$ (where $n \geq 3$) is the cycle graph $C_n$, a 2-regular graph with $n$ vertices arranged in a single cycle, where each vertex $k$ (for $k \in \{0, 1, \dots, n-1\}$) connects to $k+1 \pmod{n}$ and $k-1 \pmod{n}$.^[11] This structure arises because multiplication by 1 or $n-1$ (equivalent to -1 modulo $n$) shifts vertices along the cycle, reflecting the group's additive structure without additional edges.^[11] For the free group $F_2$ on two generators $a$ and $b$, the Cayley graph with respect to the symmetric generating set $S = \{a, b, a^{-1}, b^{-1}\}$ is an infinite 4-regular tree, where each vertex has exactly four edges corresponding to right multiplication by elements of $S$.^[12] The absence of relations in $F_2$ ensures no cycles form in the graph, making it a tree that extends indefinitely, with paths representing reduced words in the generators.^[12] The symmetric group $S_3$, which has six elements consisting of the identity and all permutations of three objects, has a Cayley graph with respect to the generating set $S$ of all three transpositions $\{(1\,2), (1\,3), (2\,3)\}$ that forms a 3-regular graph on six vertices, the complete bipartite graph $K_{3,3}$, with bipartition given by the sets of even and odd permutations.^[13] Each vertex represents a permutation, and edges connect permutations differing by right multiplication by a transposition, highlighting the group's non-abelian nature through the graph's connectivity.^[14] The dihedral group $D_n$ (symmetries of a regular $n$-gon, for $n \geq 3$), generated by a rotation $r$ (of order $n$) and a reflection $f$ (of order 2), yields a Cayley graph with respect to $S = \{r, r^{-1}, f\}$ that is the $n$-prism graph, a 3-regular graph with $2n$ vertices divided into two $n$-cycles (rotations and reflections) connected by matching edges for the reflection generator.^[15] For $n=3$, this specializes to the triangular prism graph, isomorphic to the Cayley graph of $S_3$ under the same presentation.^[15] The Klein four-group $V_4 \cong \mathbb{Z}_2 \times \mathbb{Z}_2$, an abelian group of order 4 with elements $\{e, h, v, r\}$ (identity, horizontal flip, vertical flip, 180° rotation), has a Cayley graph with respect to the generating set $S = \{h, v\}$ (both of order 2) that is the 2-dimensional hypercube graph $Q_2$, equivalently a 4-cycle $C_4$, where vertices connect via commuting generators to form a square.^[16] Using all three non-identity elements as generators yields a complete graph $K_4$, but the minimal generating set emphasizes the group's vector space-like structure over $\mathbb{F}_2$.^[16]

Properties

Elementary Properties

Cayley graphs are regular graphs of degree equal to the size of the generating set $S$, assuming $S$ does not contain the identity element and has no repetitions. This regularity follows directly from the construction: each vertex $g \in G$ is connected to exactly $|S|$ neighbors $gs$ for $s \in S$.^[10][1] Every Cayley graph is vertex-transitive. The group $G$ acts on the vertex set by left multiplication, which is transitive because for any vertices $g, h \in G$, the map $\phi(x) = k x$ with $k = g h^{-1}$ sends $h$ to $g$ and preserves adjacency: if $h$ connects to $hs$, then $\phi(hs) = k (h s) = g s$, so $\phi(h)$ connects to $g s$.^[10][2][17] A Cayley graph is edge-transitive if the generating set $S$ is a normal subset of $G$, meaning $g S g^{-1} = S$ for all $g \in G$. In this case, the graph admits an edge-transitive automorphism group induced by the holomorph of $G$. More generally, edge-transitivity holds under conditions where the connection set allows transitive action on edges via group automorphisms.^[18] The Cayley graph is connected if and only if $S$ generates $G$; otherwise, it consists of disconnected components corresponding to the cosets of the subgroup generated by $S$.^[10][1] In terms of linear algebra, the adjacency matrix $A$ of the Cayley graph acts on functions $f: G \to \mathbb{C}$ by

$$(A f)(g) = \sum_{s \in S} f(g s).$$

This representation highlights connections to the regular representation of $G$ and provides a basis for spectral analysis without delving into full derivations.^[1] Cayley graphs form a proper subclass of vertex-transitive graphs. For instance, the Petersen graph is vertex-transitive but not isomorphic to any Cayley graph.^[10][19]

Characterization

A connected vertex-transitive graph is a Cayley graph if and only if it admits a regular group of automorphisms acting on its vertices.^[20] This characterization, known as Sabidussi's theorem, identifies Cayley graphs algebraically through the existence of a subgroup of the automorphism group that acts regularly—meaning transitively and freely—on the vertex set.^[20] In this context, the group is isomorphic to the vertex set, and the edges correspond to right (or left) multiplication by elements of a generating set. More precisely, an undirected graph $\Gamma$ with vertex set $V(\Gamma)$ is a Cayley graph for a group $G$ if and only if there exists an isomorphism $\phi: G \to V(\Gamma)$ and a generating set $S \subseteq G \setminus \{e\}$ such that $S = S^{-1}$ (ensuring undirected edges) and the edges of $\Gamma$ are exactly $\{\phi(g), \phi(gs)\}$ for all $g \in G$ and $s \in S$, with the action of $G$ on $V(\Gamma)$ via $\phi$ being regular and preserving the edge relation.^[20] For directed Cayley graphs (digraphs), the characterization extends analogously: a digraph $\Gamma$ is a Cayley digraph for $G$ if and only if its automorphism group contains a regular subgroup isomorphic to $G$, but the generating set $S$ need not be symmetric, allowing arcs $\{\phi(g), \phi(gs)\}$ without requiring inverse relations.^[21] This adaptation preserves the regular action but accommodates directionality in the edge structure. However, not every connected vertex-transitive graph is a Cayley graph, as the automorphism group may lack a suitable regular subgroup despite vertex-transitivity.^[22] The Petersen graph, with 10 vertices and degree 3, is the smallest such example.^[22] Praeger and McKay's work provides systematic constructions and enumerations of vertex-transitive non-Cayley graphs, highlighting algebraic obstructions in the automorphism group structure.^[22]

Variants

Schreier Coset Graph

The Schreier coset graph of a group $G$ with respect to a subgroup $H$ and a generating set $S$ (typically finite, symmetric, and excluding the identity) is a graph whose vertex set consists of the right cosets $G/H = \{gH \mid g \in G\}$. For each vertex $gH$ and each generator $s \in S$, there is a directed edge from $gH$ to $gsH$ labeled by $s$. If $S$ is symmetric (i.e., closed under inverses), the graph is undirected. This construction arises from the transitive action of $G$ on the cosets of $H$ by right multiplication.^[23][24][25] The Schreier coset graph can be viewed as a quotient of the Cayley graph $\mathrm{Cay}(G, S)$ under the right action of $H$, where vertices of the Cayley graph in the same coset are identified, and edges are projected accordingly to reflect the permutation representation of $G$ on $G/H$. This quotient preserves the generating relations but captures the structure of the coset space rather than the full group.^[23][24] The graph is $|S|$-regular, with each vertex having out-degree (or degree, if undirected) equal to $|S|$, but it may contain multiple edges between the same pair of vertices or loops if $H$ is not normal in $G$, as the stabilizer action can cause overlaps in coset transitions. Paths in the graph correspond to words in the generators $S$, and cycles based at the vertex $H$ (the coset containing the identity) represent elements of $H$. A spanning tree from $H$ provides a Schreier transversal, whose complementary edges yield generators for $H$ via the Reidemeister-Schreier process.^[23][24][25] Schreier coset graphs are employed in coset enumeration algorithms, such as the Todd-Coxeter procedure, to compute the index $[G:H]$ by systematically building the graph through breadth-first search on cosets, applying group relations to identify coincidences and determine the finite or infinite nature of the index. For example, if $H = G$, the graph consists of a single vertex with no edges (or self-loops if $S$ allows); conversely, if $H = \{e\}$ (the trivial subgroup), the Schreier coset graph recovers the full Cayley graph $\mathrm{Cay}(G, S)$.^[23][25]

Directed Cayley Graphs

A directed Cayley graph, also known as a Cayley digraph, is a directed graph $\Cay^\to(G, S)$ associated to a group $G$ and a subset $S \subseteq G$ (typically excluding the identity to avoid loops), where the vertex set is $G$ and there is a directed edge from $g$ to $gs$ for every $g \in G$ and $s \in S$.^[26] This construction generalizes the undirected Cayley graph by allowing $S$ to be non-symmetric, meaning $S$ need not equal its set of inverses $S^{-1} = \{s^{-1} \mid s \in S\}$.^[27] In a directed Cayley graph, every vertex has out-degree equal to $|S|$, as there is exactly one outgoing edge labeled by each $s \in S$. Due to the vertex-transitive action of $G$ on itself by right multiplication, the in-degree is also $|S|$ for every vertex, making $\Cay^\to(G, S)$ a regular digraph of degree $|S|$.^[26] The graph is strongly connected—that is, there is a directed path from any vertex to any other—if and only if $S$ generates $G$.^[26] Directed Cayley graphs are particularly useful for modeling one-way group actions, such as in the analysis of semigroup structures or asymmetric relations in group theory, and they form the basis for Cayley digraphs in combinatorial studies.^[28] If $S = S^{-1}$, the underlying undirected graph obtained by ignoring edge directions coincides with the standard undirected Cayley graph $\Cay(G, S)$.^[27] A simple example is the directed Cayley graph of the cyclic group $\mathbb{Z}/n\mathbb{Z}$ with $S = \{1\}$, which forms a directed cycle of length $n$: vertices are integers modulo $n$, with edges $k \to k+1 \pmod{n}$. This graph is strongly connected since $\{1\}$ generates $\mathbb{Z}/n\mathbb{Z}$.^[27]

Group-Theoretic Applications

Geometric Group Theory

In geometric group theory, Cayley graphs provide a geometric realization of finitely generated groups, endowing them with a natural metric structure derived from the graph distance. For a finitely generated group $G$ with finite symmetric generating set $S$, the Cayley graph $\Gamma(G, S)$ is equipped with the word metric $d_S(g, h)$, defined as the length of the shortest path from $g$ to $h$ in the graph, or equivalently, the minimal number of generators needed to express $g^{-1}h$ as a word in $S$. This metric turns $G$ into a proper geodesic metric space, where geodesics correspond to shortest words, allowing the study of group elements via paths in the graph.^[29][30] The growth rate of a group, measured by the cardinality of balls $B(e, n) = \{ g \in G : d_S(e, g) \leq n \}$ in the Cayley graph, distinguishes fundamental algebraic classes: groups like $\mathbb{Z}^d$ exhibit polynomial growth of degree $d$, reflecting their solvable nature and lattice-like structure in the graph, while free groups display exponential growth due to the tree-like branching of paths without cycles. This dichotomy, invariant under quasi-isometry, highlights how Cayley graphs encode asymptotic behavior, with intermediate growth cases like the Grigorchuk group illustrating more subtle geometric phenomena. For free groups $F_r$ on $r \geq 2$ generators, the Cayley graph is precisely a regular tree of degree $2r$, embodying pure exponential expansion with no relations imposing cycles.^[31][32] A key coarse geometric property is hyperbolicity: a group $G$ is hyperbolic if its Cayley graph $\Gamma(G, S)$ is $\delta$-hyperbolic for some $\delta \geq 0$, meaning all geodesic triangles are $\delta$-thin, with side geodesics staying within $\delta$ of each other, as introduced by Gromov. This thin triangle condition captures negatively curved behavior at large scales, enabling algorithmic decidability and boundary compactness. Different finite generating sets $S$ and $S'$ yield quasi-isometric Cayley graphs, with a $(K, C)$-quasi-isometry $f: \Gamma(G, S) \to \Gamma(G, S')$ satisfying $\frac{1}{K} d_S(x, y) - C \leq d_{S'}(f(x), f(y)) \leq K d_S(x, y) + C$, ensuring that geometric invariants like hyperbolicity and growth type are preserved across choices of generators.^[29][30] Cayley graphs facilitate solving the word problem through breadth-first search in the graph, starting from the identity to find the minimal path to a given element, decidable for finitely presented groups where relations bound the search depth. In Bass-Serre theory, for amalgamated free products like $A *_C B$, the associated Bass-Serre tree serves as a geometric model on which the group acts without edge inversions, with the quotient by the group action being the fundamental domain (the Bass-Serre graph), thereby revealing the splittings and classifying groups like virtually free groups through their tree actions. These tools underscore how Cayley graphs bridge algebraic structure with metric geometry, enabling quasi-isometric classification of groups.^[33][34]

Expansion Properties

Cayley graphs exhibit strong expansion properties, making them a cornerstone in the study of expander graphs. For a Cayley graph $\Gamma = \mathrm{Cay}(G, S)$ that is $d = |S|$-regular, the vertex expansion can be quantified through the Cheeger constant $h(\Gamma)$, defined as the minimum over subsets $U \subset G$ with $|U| \leq |G|/2$ of $|E(U, G \setminus U)| / (|U| d)$, where $E(U, G \setminus U)$ denotes the number of edges crossing the cut. By the Cheeger inequality, $h(\Gamma) \geq (d - \lambda_2)/ (2d)$, where $\lambda_2$ is the second-largest eigenvalue of the adjacency matrix of $\Gamma$, providing a lower bound on expansion in terms of the spectral gap. This relates discrete expansion to the graph's spectral properties, ensuring that small sets expand significantly under the neighborhood operator.^[35] The spectral gap of Cayley graphs is central to their expander behavior, with expansion occurring when $\lambda_2$ is bounded away from $d$. Specifically, $\Gamma$ is an $\varepsilon$-expander if $|\lambda_2| / d \leq 1 - \varepsilon$ for some fixed $\varepsilon > 0$ independent of $|G|$, implying rapid mixing of random walks and robust connectivity. For families of Cayley graphs on growing groups, uniform bounds on the spectral gap yield families of expanders. The Kazhdan constant $K(G, S)$ from representation theory provides a group-theoretic lower bound on the gap: $g(G, S) \geq K(G, S)^2 / (2d)$, where $g(G, S) = d - \lambda_2$ is the unnormalized gap.^[35][36] Ramanujan Cayley graphs achieve the optimal spectral expansion possible for regular graphs. These are $d$-regular graphs where all nontrivial eigenvalues $\lambda$ satisfy $|\lambda| \leq 2\sqrt{d-1}$, saturating the Alon-Boppana bound up to lower-order terms. Explicit constructions include the Lubotzky–Phillips–Sarnak (LPS) graphs, which are Cayley graphs on $\mathrm{PSL}(2, q)$ for prime powers $q \equiv 1 \pmod{d-1}$, using generators from quadratic residues and non-residues in $\mathbb{F}_q$. Independently, Margulis constructed Ramanujan graphs as Cayley graphs on $\mathrm{SL}(2, q)$ with similar generating sets, leveraging Deligne's proof of the Ramanujan conjecture to bound eigenvalues via character sums. These graphs provide the best-known explicit expanders for certain degrees.^[37][35] Random Cayley graphs also provably exhibit strong expansion properties. The Alon–Roichman theorem states that for a finite group $G$ and $d = C \log |G|$ with sufficiently large constant $C$, a random symmetric generating set $S \subset G$ of size $d$ yields a Cayley graph $\mathrm{Cay}(G, S)$ that is an expander with high probability, specifically with $|\lambda_2| \leq (1 - \varepsilon) d$ for fixed $\varepsilon > 0$. This probabilistic result demonstrates that most Cayley graphs on a fixed group are expanders when the degree grows logarithmically with the group order, simplifying constructions via sampling rather than explicit algebraic choices.^[38] Recent developments include explicit constructions of high-dimensional expanders from Cayley graphs over $\mathbb{F}_2^n$, advancing applications in theoretical computer science as of 2024.^[39] These expansion properties of Cayley graphs have significant applications in pseudorandomness and derandomization. Expander walks on Cayley graphs generate pseudorandom permutations and subsets, enabling efficient derandomization of algorithms like primality testing and space-bounded computation, where the spectral gap ensures small bias in output distributions. For instance, LPS Ramanujan graphs have been used to construct explicit pseudorandom generators with optimal seed length.^[35]

Advanced Classifications

Integral Classification

A Cayley graph Cay(G, S) is integral if all eigenvalues of its adjacency matrix are integers. The eigenvalues of such a graph are determined via the irreducible characters of the group G. For each irreducible character χ of G, there is an eigenvalue given by

$$\lambda_\chi = \sum_{s \in S} \chi(s),$$

with algebraic multiplicity equal to the degree χ(1) of χ.^[40] Therefore, Cay(G, S) is integral if and only if λ_χ is an integer for every irreducible character χ of G.^[40] This spectral characterization connects the integrality of Cay(G, S) directly to the character table of G and the distribution of values of χ over the generating set S. For the trivial character χ_1, λ_{χ_1} = |S|, which is always an integer. For non-trivial characters, integrality requires that the sum ∑_{s ∈ S} χ(s) lies in ℤ. Since characters take values in algebraic integers, the condition imposes restrictions on S relative to the representation theory of G.^[40] All finite abelian groups admit integral Cayley graphs. For instance, taking S = G \ {e} yields the complete graph K_{|G|}, whose spectrum consists of the eigenvalue |G| - 1 (simple) and -1 (multiplicity |G| - 1), both integers; this construction works for any finite group, confirming that every finite group admits at least one integral Cayley graph.^[41] In the abelian case, the 1-dimensional characters simplify the sums: each λ_χ = ∑_{s ∈ S} χ(s), where χ ranges over the dual group, and suitable S (such as unions of cosets or specific subsets) ensure integrality. Non-abelian groups also admit integral Cayley graphs, but not all generating sets S yield integrality. For example, the symmetric group S_3 admits integral Cayley graphs for various S, including those generating the group, due to its small character table with integer-valued sums for appropriate subsets.^[41] In contrast, for the alternating group A_5, while the complete Cayley graph is integral, many generating sets S produce non-integer eigenvalues, as the sums over its five conjugacy classes often yield non-integers unless S is specially chosen.^[41] A finer classification considers Cayley integral groups, those for which every undirected Cayley graph (with S = S^{-1}, e ∉ S) is integral. The finite such groups are precisely the abelian groups of exponent dividing 4 or 6, the symmetric group S_3, the non-abelian group of order 12 given by C_3 ⋊ C_4, and the direct products Q_8 × C_{2^n} for n ≥ 0, where Q_8 is the quaternion group.^[42] For these groups, the character values ensure that ∑_{s ∈ S} χ(s) ∈ ℤ for all possible symmetric S and all χ. A_5 is not Cayley integral, as it admits non-integral Cayley graphs for certain S.^[42]

Normal and Eulerian Generating Sets

A generating set $S$ for a finite group $G$ is called normal if it is invariant under conjugation by elements of $G$, that is, $g^{-1}Sg = S$ for all $g \in G$. This condition implies that $S$ is a union of conjugacy classes of $G$.^[43] For such a normal generating set $S$ (assuming $S = S^{-1}$ and $1 \notin S$ to ensure the Cayley graph is undirected and loop-free), the corresponding Cayley graph $\mathrm{Cay}(G, S)$ is a normal Cayley graph, meaning that the right regular representation of $G$ is a normal subgroup of the automorphism group $\mathrm{Aut}(\mathrm{Cay}(G, S))$.^[44] This normality enhances the symmetry of the graph, aligning left and right multiplications by group elements and often resulting in edge-transitivity.^[45] In abelian groups, every subset is normal, since conjugation acts trivially. Thus, every symmetric generating set $S$ for an abelian $G$ yields a normal Cayley graph. For the symmetric group $S_n$ ($n \geq 2$), the full set of all transpositions forms a normal generating set, as transpositions constitute a single conjugacy class. However, minimal generating sets consisting of fewer transpositions are generally not normal, unless they coincide with the full class or satisfy additional conjugation invariance, which is rare for proper subsets.^[46] An Eulerian generating set $S$ for $G$ is a symmetric generating set ($S = S^{-1}$, $1 \notin S$) such that the Cayley graph $\mathrm{Cay}(G, S)$ is Eulerian, meaning it admits an Eulerian circuit (a closed trail traversing each edge exactly once). By standard graph theory, an undirected connected graph is Eulerian if and only if every vertex has even degree. Since $\mathrm{Cay}(G, S)$ is $|S|$-regular and connected (as $S$ generates $G$), it is Eulerian precisely when $|S|$ is even. Normal generating sets often produce Cayley graphs with additional desirable properties, such as integrality (integer eigenvalues of the adjacency matrix). Specifically, if $S$ is a normal subset that is also power-closed—meaning $s \in S$ implies $s^k \in S$ for all integers $k$ coprime to the order of $s$—then all eigenvalues of $\mathrm{Cay}(G, S)$ are integers.^[47] This connection links normal sets to integral Cayley graphs. Moreover, in Cayley integral groups (finite groups $G$ where every connected Cayley graph is integral), every minimal generating set $S$ yields an integral graph, and normal subsets frequently align with this property due to their conjugation invariance facilitating integer character sums in the eigenvalue formula $\sum_{s \in S} \chi(s)$ for irreducible characters $\chi$. Finite abelian Cayley integral groups are precisely those of exponent dividing 4 or 6, while non-abelian examples include $S_3$ and the dihedral group of order 8.^[47][48][49]

Applications in Other Fields

Combinatorics and Graph Theory

Cayley graphs play a significant role in enumerative combinatorics through the study of their Hamiltonicity. It is a classical result that every connected Cayley graph on a finite abelian group admits a Hamiltonian cycle.^[50] This follows from the structure of abelian groups, where the generating set allows for a systematic traversal of all vertices via group operations. More broadly, the Lovász conjecture posits that every connected finite vertex-transitive graph contains a Hamiltonian path, and since Cayley graphs are vertex-transitive, the conjecture applies directly to them. While the full conjecture remains open, it has been affirmatively resolved for all Cayley graphs on abelian groups, p-groups, and several other classes, with a 2024 proof establishing it for all connected vertex-transitive graphs of odd order.^[51][52] Counterexamples to the cycle version known only for non-Cayley vertex-transitive graphs.^[51] In extremal graph theory, Cayley graphs are central to the degree-diameter problem, which seeks the maximum number of vertices in a graph of given maximum degree $d$ and diameter $k$. The Moore bound provides an upper limit on this order, given by $M(d,k) = 1 + d \sum_{i=0}^{k-1} (d-1)^i$, and Cayley graphs often come close to achieving it, particularly for small diameters. For instance, for diameter 2, certain Cayley graphs asymptotically approach the Moore bound for infinitely many degrees, demonstrating their extremal potential. These constructions highlight how the algebraic symmetry of Cayley graphs enables tight bounds on diameter relative to degree and order, with minimal diameter values for fixed degree and order frequently realized by Cayley graphs on specific groups like elementary abelian or dihedral groups.^[53] The isomorphism problem for Cayley graphs—determining whether two such graphs are isomorphic—ties into broader computational complexity questions in graph theory. In general, deciding isomorphism between two Cayley graphs is GI-complete, meaning it is as hard as the general graph isomorphism problem, which is not known to be in P but has quasi-polynomial time algorithms. This complexity arises even for restricted classes, though for fixed groups like cyclic or abelian ones, the problem reduces to checking group automorphisms and connection set equivalences under conjugation. Surveys on Cayley graph isomorphisms emphasize that while polynomial-time solvable cases exist for certain groups (e.g., CI-groups where isomorphisms are induced solely by group automorphisms), the general case remains challenging and complete for the isomorphism hierarchy. Enumerative aspects of Cayley graphs involve counting the number of distinct such graphs on $n$ vertices, which relates to labeling the vertices with group elements and selecting connection sets up to isomorphism. The total count depends on the underlying group structure; for example, over cyclic groups of order $n$, the enumeration involves summing over subsets closed under inversion. Asymptotically, almost all Cayley digraphs on a fixed group have the minimal possible automorphism group, leading to precise asymptotic formulas for the number of non-isomorphic Cayley graphs as the connection set size grows. These counts connect to broader enumerative combinatorics, such as Polya enumeration techniques applied to group actions on graphs.^[54] A key structural theorem in this context states that connected Cayley graphs achieve optimal connectivity among vertex-transitive graphs, with both vertex-connectivity and edge-connectivity equal to the degree. This optimality stems from the regular action of the group on itself, ensuring no smaller vertex or edge cut disconnects the graph than the degree itself, unlike general vertex-transitive graphs which may have connectivity as low as $2(\delta + 1)/3$. This property underscores the robustness of Cayley graphs in extremal settings, where they maximize connectivity for their symmetry class.^[55]

Computer Science and Networks

Cayley graphs serve as models for interconnection networks in parallel and distributed computing systems due to their vertex-transitivity, which ensures uniform routing properties and fault tolerance. For instance, the hypercube network, a prominent topology in early parallel computers like the Connection Machine, is the Cayley graph of the elementary abelian group $\mathbb{Z}_2^n$ with generators corresponding to bit flips.^[56] This structure provides logarithmic diameter and high connectivity, enabling efficient communication in systems with up to $2^n$ processors. Other Cayley graphs, such as those derived from cyclic groups or symmetric groups, offer alternatives with fixed degrees greater than three, improving scalability over hypercubes for certain applications like the cyclic-cube networks.^[57] In parallel computing, Cayley graphs facilitate routing algorithms that exploit their algebraic structure for optimal path finding. Vertex-transitivity allows for simple, distributed routing schemes where messages follow group operations to reach destinations in diameter steps, as demonstrated in general-purpose algorithms for Cayley-based architectures.^[58] For gossip algorithms, which involve all-to-all communication for tasks like matrix multiplication or data aggregation, Cayley graphs enable efficient packet-based dissemination; for example, in star graphs (Cayley graphs of symmetric groups), optimal gossiping completes in $O(n)$ rounds for $n!$ nodes.^[59] These properties make Cayley graphs suitable for fault-tolerant routing in Borel Cayley graphs, where algorithms tolerate up to degree-minus-one faults while maintaining short paths.^[60] Cayley graphs underpin expander codes in modern coding theory, leveraging their expansion properties to construct high-rate error-correcting codes resilient to erasures. Post-2020 developments include explicit constructions of expander codes from Cayley graphs of finite groups, achieving near-optimal rates for storage and computation with spectral guarantees from the graph's eigenvalues.^[61] These codes, often built on Ramanujan Cayley graphs, connect to quantum low-density parity-check codes and provide interactive oracle proofs of proximity for verifiable computation.^[62] The Rubik's Cube puzzle is modeled via the Cayley graph of its configuration group, where vertices represent cube states and edges correspond to legal moves (face rotations), allowing analysis of optimal solving sequences. This graph, with 43 quintillion vertices, has a diameter of 20 in the quarter-turn metric, known as God's number, computed through exhaustive search and symmetry exploitation.^[63] A simplified model uses the Cayley graph of $S_8$ quotiented by its center to capture corner permutations, illustrating shortest paths for subgroup resolutions.^[64] In cryptography, Cayley graphs of elliptic curve groups support discrete logarithm-based protocols by providing expander-like structures for secure key exchange. Constructions from ray class groups yield Cayley expanders with GRH-conditional eigenvalue bounds, enhancing the hardness of discrete logs on elliptic curves used in standards like NIST curves.^[65] These graphs enable efficient hash functions and contribute to post-quantum schemes by modeling isogeny walks on supersingular elliptic curves.^[66] Recent advances in quantum computing feature quantum walks on Cayley graphs for search and simulation algorithms. Discrete-time quantum walks on dihedral group Cayley graphs exhibit perfect state transfer and periodicity, outperforming classical walks in hitting times for marked vertices.^[67] Post-2020 studies on extraspecial groups' Cayley graphs reveal fractional revivals in continuous-time walks, with applications to quantum search on non-abelian structures.^[68]

Historical Development

Origins

Arthur Cayley introduced the concept of what would later be known as Cayley graphs in his 1878 paper "The Theory of Groups: Graphical Representation," published in the American Journal of Mathematics.^[1] In this short note, Cayley described a method to represent finite groups using diagrams that illustrate the connections between group elements based on multiplication by generators, providing a visual tool for exploring group structure. The primary motivation for this graphical approach was to visualize the symmetric nature of group multiplication tables, transforming the tabular representation of abstract group operations into intuitive diagrams that highlight the regularity and connectivity inherent in group theory. Cayley sought to make the algebraic relations more accessible by depicting how generators link elements, emphasizing the symmetry and closure properties of the group. Cayley's early examples focused on symmetric groups and permutations, such as the symmetric group on three letters (of order 6), where he illustrated the group's structure through connected vertices representing permutations and edges showing compositions. He also applied the method to groups of order 8, demonstrating how the diagrams reveal isomorphism classes and subgroup relations among permutation groups. A notable predecessor to Cayley's work is William Rowan Hamilton's Icosian game from the 1850s, a puzzle involving finding Hamiltonian cycles on the dodecahedral graph. This game highlighted graph-theoretic explorations of symmetric structures akin to those later formalized in group diagrams.^[69] Cayley himself did not use the term "Cayley graph"; this nomenclature was introduced later in the 20th century by H. S. M. Coxeter in 1938.^[70]

Modern Developments

In the mid-20th century, advancements in Cayley graph theory focused on algorithmic applications, particularly through Schreier coset graphs derived from the Reidemeister-Schreier theorem. This theorem, originally established in the late 1920s, enabled the construction of presentations for subgroups via coset enumerations, with Schreier coset graphs providing a graphical representation of group actions on cosets. By the 1930s and 1940s, these graphs became essential for computational group theory, facilitating algorithms to determine subgroup structures and normal forms in finitely presented groups.^[71] The 1970s and 1980s marked a pivotal shift toward geometric interpretations, culminating in Mikhail Gromov's introduction of hyperbolic groups in 1987. Gromov's framework treated Cayley graphs of finitely generated groups as metric spaces, defining hyperbolicity via thin triangles in these graphs, which unified combinatorial and geometric properties of groups like free groups and surface groups. This development laid the foundation for geometric group theory, emphasizing asymptotic behavior and quasi-isometries of Cayley graphs. Concurrently, in 1988, Alexander Lubotzky, Ralph Phillips, and Peter Sarnak constructed explicit families of expander graphs as Cayley graphs on SL(2, p) using Ramanujan bounds on eigenvalues, achieving optimal expansion properties for regular graphs. The 1990s saw further refinements, including Norman Biggs's comprehensive historical and algebraic analysis of Cayley graphs in his 1993 book, which synthesized their role in spectral graph theory and connectivity. Progress in integral classifications emerged in the late 1990s and 2000s, with Walter Klotz and Torsten Sander classifying abelian Cayley integral groups—those where all undirected Cayley graphs have integer eigenvalues—as finite abelian groups of exponent dividing 4 or 6. Their work extended to non-abelian cases, highlighting connections to representation theory. From the 2000s onward, research diversified into quantum and probabilistic settings. Quantum walks on Cayley graphs, introduced in 2005, modeled coherent propagation on group structures, revealing enhanced mixing times compared to classical random walks and applications in quantum algorithms.^[72] Random Cayley graphs, studied in 2002, demonstrated expander-like properties almost surely for symmetric groups, bridging probability and explicit constructions. Recent work has explored conditions for Eulerian properties in Cayley graphs, linking to Hamiltonicity. Post-2020, Cayley structures have informed AI, particularly graph neural networks; for instance, 2024 research proposed Cayley graph propagation to mitigate oversquashing in GNNs by leveraging complete Cayley graphs for efficient information flow.^[73]