Fact-checked by Grok 2 weeks ago

Cayley graph

In group theory, a Cayley graph (or ) of a group G with respect to a generating set S \subseteq G (not containing the ) is a with set G, where there is a directed edge from g to gs labeled by s, for every g \in G and s \in S. 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. 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. The concept was introduced by the English mathematician 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. Cayley graphs are always regular graphs of degree |S|, and they are vertex-transitive, meaning the acts transitively on the vertices, reflecting the group's left-regular action on itself. These properties make Cayley graphs fundamental tools in , where the graph's (shortest distance) defines a word metric on the group, quantifying "distance" between elements in terms of generator lengths. Cayley graphs have wide-ranging applications across and . In and , they facilitate the study of group properties like Hamiltonicity and connectivity, with many well-known graphs (e.g., hypercubes, , and cube-connected cycles) arising as Cayley graphs of specific groups. In , they model interconnection networks for due to their and efficiency in , and serve as explicit constructions of expander graphs, which are crucial for derandomization, pseudorandom generators, and error-correcting codes. Additionally, Cayley graphs underpin algorithms for problems like the in and provide frameworks for analyzing word problems in groups.

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 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 with set G.[ [](https://math.osu.edu/sites/math.osu.edu/files/Cayley.pdf) When $S$ is symmetric ($S = S^{-1}$) and excludes the [identity element](/page/Identity_element) of $G$, the [graph](/page/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$).] This construction yields a without loops or multiple edges under these assumptions, as left multiplication by g is bijective and the is absent.[$$ If S is not symmetric, the Cayley graph is instead defined as directed, with a directed 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](/page/Vertex), while non-inverse-closed $S$ in an undirected context can lead to multiple edges if both directions are forcibly added without symmetry.\[ 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.\[$$ [](https://mathworld.wolfram.com/CayleyGraph.html) ### Examples The Cayley graph of the [cyclic group](/page/Cyclic_group) $\mathbb{Z}_n$ with generating set $S = \{1, n-1\}$ (where $n \geq 3$) is the [cycle graph](/page/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}$.[](https://faculty.etsu.edu/gardnerr/5340/notes-Godsil-Royle/Algebraic-GT-GR-1-5.pdf) This structure arises because multiplication by 1 or $n-1$ (equivalent to -1 [modulo](/page/Modulo) $n$) shifts vertices along the cycle, reflecting the group's additive structure without additional edges.[](https://faculty.etsu.edu/gardnerr/5340/notes-Godsil-Royle/Algebraic-GT-GR-1-5.pdf) 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](/page/Tree), where each [vertex](/page/Vertex) has exactly four edges corresponding to right multiplication by elements of $S$.[](https://www.math.columbia.edu/~alessandrini/Courses/Undergraduate_Seminars-s2020/Cayley%20Graphs%20of%20Free%20Groups_GSanchez.pdf) The absence of relations in $F_2$ ensures no cycles form in the graph, making it a [tree](/page/Tree) that extends indefinitely, with paths representing reduced words in the generators.[](https://www.math.columbia.edu/~alessandrini/Courses/Undergraduate_Seminars-s2020/Cayley%20Graphs%20of%20Free%20Groups_GSanchez.pdf) The [symmetric group](/page/Symmetric_group) $S_3$, which has six elements consisting of the identity and all [permutations](/page/Permutation) of three objects, has a Cayley graph with respect to the generating set $S$ of all three [transpositions](/page/Transposition) $\{(1\,2), (1\,3), (2\,3)\}$ that forms a 3-regular [graph](/page/Graph) on six vertices, the [complete bipartite graph](/page/Complete_bipartite_graph) $K_{3,3}$, with bipartition given by the sets of even and odd [permutations](/page/Permutation).[](https://arxiv.org/pdf/1205.5199.pdf) Each [vertex](/page/Vertex) represents a [permutation](/page/Permutation), and edges connect [permutations](/page/Permutation) differing by right multiplication by a [transposition](/page/Transposition), highlighting the group's non-abelian nature through the [graph](/page/Graph)'s connectivity.[](https://people.tamu.edu/~yvorobets/MATH415-2021C/Lect1-09web.pdf) 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.[](https://www.math.clemson.edu/~macaule/classes/m20_math4120/slides/math4120_lecture-2-02_h.pdf) For $n=3$, this specializes to the triangular prism graph, isomorphic to the Cayley graph of $S_3$ under the same presentation.[](https://www.math.clemson.edu/~macaule/classes/m20_math4120/slides/math4120_lecture-2-02_h.pdf) The [Klein four-group](/page/Klein_four-group) $V_4 \cong \mathbb{Z}_2 \times \mathbb{Z}_2$, an [abelian group](/page/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](/page/Hypercube_graph) $Q_2$, equivalently a 4-cycle $C_4$, where vertices connect via commuting generators to form a square.[](http://www.math.clemson.edu/~macaule/classes/s14_math4120/s14_math4120_lecture-02-handout.pdf) Using all three non-identity elements as generators yields a [complete graph](/page/Complete_graph) $K_4$, but the minimal generating set emphasizes the group's vector space-like structure over $\mathbb{F}_2$.[](http://www.math.clemson.edu/~macaule/classes/s14_math4120/s14_math4120_lecture-02-handout.pdf) | Group | Generating Set $S$ | Graph Type | Vertices | Degree | |-------------|-----------------------------------|-----------------------------|----------|--------| | $\mathbb{Z}_n$ | $\{1, n-1\}$ | Cycle $C_n$ | $n$ | 2 | | $F_2$ | $\{a, b, a^{-1}, b^{-1}\}$ | 4-regular tree | Infinite| 4 | | $S_3$ | Transpositions $\{(1\,2), (1\,3), (2\,3)\}$ | Complete bipartite $K_{3,3}$ | 6 | 3 | | $D_n$ | $\{r, r^{-1}, f\}$ | $n$-prism | $2n$ | 3 | | $V_4$ | $\{h, v\}$ | Hypercube $Q_2$ ($C_4$) | 4 | 2 ## Properties ### Elementary Properties Cayley graphs are [regular](/page/Regular) graphs of [degree](/page/Degree) equal to the [size](/page/Size) of the generating set $S$, assuming $S$ does not contain the [identity element](/page/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$.[](https://mathworld.wolfram.com/CayleyGraph.html)[](https://www.math.mcgill.ca/goren/667.2010/Cameron.pdf) 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](/page/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$.[](https://mathworld.wolfram.com/CayleyGraph.html)[](https://math.osu.edu/sites/math.osu.edu/files/Cayley.pdf)[](http://buzzard.ups.edu/courses/2019spring/projects/york-presentation-ups-434-2019.pdf) 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](/page/Automorphism_group) induced by the holomorph of $G$. More generally, edge-transitivity holds under conditions where the connection set allows transitive [action](/page/Action) on edges via group automorphisms.[](https://www.researchgate.net/profile/Cheryl-Praeger/publication/231888480_Finite_normal_edge-transitive_Cayley_graphs/links/58b11523aca2725b5413eb9c/Finite-normal-edge-transitive-Cayley-graphs.pdf) 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](/page/Subgroup) generated by $S$.[](https://mathworld.wolfram.com/CayleyGraph.html)[](https://www.math.mcgill.ca/goren/667.2010/Cameron.pdf) In terms of linear algebra, the [adjacency matrix](/page/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](/page/Regular_representation) of $G$ and provides a basis for [spectral analysis](/page/Spectral_analysis) without delving into full derivations.[](https://www.math.mcgill.ca/goren/667.2010/Cameron.pdf) Cayley graphs form a proper subclass of [vertex-transitive graphs](/page/Vertex-transitive_graph). For instance, the [Petersen graph](/page/Petersen_graph) is vertex-transitive but not isomorphic to any Cayley graph.[](https://mathworld.wolfram.com/CayleyGraph.html)[](https://users.cecs.anu.edu.au/~bdm/papers/cheryl1.pdf) ### Characterization A connected [vertex-transitive graph](/page/Vertex-transitive_graph) is a Cayley graph if and only if it admits a [regular](/page/Regular) group of automorphisms acting on its [vertices](/page/Vertex).[](https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/graphs-with-given-group-and-given-graphtheoretical-properties/11C54FCF88D5C860650808B200EA8727) This characterization, known as Sabidussi's theorem, identifies Cayley graphs algebraically through the existence of a subgroup of the [automorphism group](/page/Automorphism_group) that acts [regularly](/page/Regular)—meaning transitively and freely—on the [vertex set](/page/Set).[](https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/graphs-with-given-group-and-given-graphtheoretical-properties/11C54FCF88D5C860650808B200EA8727) In this context, the group is isomorphic to the [vertex set](/page/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.[](https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/graphs-with-given-group-and-given-graphtheoretical-properties/11C54FCF88D5C860650808B200EA8727) 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.[](https://arxiv.org/pdf/1609.08272) This adaptation preserves the regular action but accommodates directionality in the edge structure. However, not every connected [vertex-transitive graph](/page/Vertex-transitive_graph) is a Cayley graph, as the [automorphism group](/page/Automorphism_group) may lack a suitable [regular](/page/Regular) subgroup despite vertex-transitivity.[](https://www.cambridge.org/core/journals/journal-of-the-australian-mathematical-society/article/vertextransitive-graphs-which-are-not-cayley-graphs-i/7073AA5167AEACE2E449CAEAF09E50BB) The [Petersen graph](/page/Petersen_graph), with 10 vertices and degree 3, is the smallest such example.[](https://www.cambridge.org/core/journals/journal-of-the-australian-mathematical-society/article/vertextransitive-graphs-which-are-not-cayley-graphs-i/7073AA5167AEACE2E449CAEAF09E50BB) Praeger and McKay's work provides systematic constructions and enumerations of vertex-transitive non-Cayley graphs, highlighting algebraic obstructions in the [automorphism group](/page/Automorphism_group) structure.[](https://www.cambridge.org/core/journals/journal-of-the-australian-mathematical-society/article/vertextransitive-graphs-which-are-not-cayley-graphs-i/7073AA5167AEACE2E449CAEAF09E50BB) ## Variants ### Schreier Coset Graph The Schreier coset graph of a group $G$ with respect to a [subgroup](/page/Subgroup) $H$ and a generating set $S$ (typically finite, symmetric, and excluding the [identity](/page/Identity)) is a [graph](/page/Graph) whose [vertex](/page/Vertex) set consists of the right cosets $G/H = \{gH \mid g \in G\}$. For each [vertex](/page/Vertex) $gH$ and each generator $s \in S$, there is a directed [edge](/page/Edge) from $gH$ to $gsH$ labeled by $s$. If $S$ is symmetric (i.e., closed under inverses), the [graph](/page/Graph) is undirected. This construction arises from the transitive [action](/page/Action) of $G$ on the cosets of $H$ by right [multiplication](/page/Multiplication).[](https://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/0794-19.pdf)[](https://people.tamu.edu/~yvorobets//Research/Schreier.pdf)[](https://www.fields.utoronto.ca/talk-media/1/89/44/slides.pdf) The Schreier coset graph can be viewed as a [quotient](/page/Quotient) of the [Cayley graph](/page/Cayley_graph) $\mathrm{Cay}(G, S)$ under the right action of $[H](/page/H+)$, where vertices of the [Cayley graph](/page/Cayley_graph) in the same [coset](/page/Coset) are identified, and edges are projected accordingly to reflect the permutation representation of $[G](/page/Group)$ on $G/H$. This [quotient](/page/Quotient) preserves the generating relations but captures the structure of the [coset](/page/Coset) space rather than the full group.[](https://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/0794-19.pdf)[](https://people.tamu.edu/~yvorobets//Research/Schreier.pdf) The [graph](/page/Graph) is $|S|$-regular, with each [vertex](/page/Vertex) having out-degree (or [degree](/page/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](/page/Normal) in $G$, as the [stabilizer](/page/Stabilizer) action can cause overlaps in [coset](/page/Coset) transitions. Paths in the graph correspond to words in the generators $S$, and cycles based at the vertex $H$ (the [coset](/page/Coset) containing the [identity](/page/Identity)) represent elements of $H$. A [spanning tree](/page/Spanning_tree) from $H$ provides a Schreier transversal, whose complementary edges yield generators for $H$ via the Reidemeister-Schreier process.[](https://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/0794-19.pdf)[](https://people.tamu.edu/~yvorobets//Research/Schreier.pdf)[](https://www.fields.utoronto.ca/talk-media/1/89/44/slides.pdf) Schreier coset graphs are employed in coset enumeration algorithms, such as the Todd-Coxeter procedure, to compute the [index](/page/Index) $[G:H]$ by systematically building the graph through [breadth-first search](/page/Breadth-first_search) on cosets, applying group relations to identify coincidences and determine the finite or infinite nature of the [index](/page/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](/page/Subgroup)), the Schreier coset graph recovers the full Cayley graph $\mathrm{Cay}(G, S)$.[](https://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/0794-19.pdf)[](https://www.fields.utoronto.ca/talk-media/1/89/44/slides.pdf) ### Directed Cayley Graphs A directed Cayley graph, also known as a Cayley [digraph](/page/Digraph), is a [directed graph](/page/Directed_graph) $\Cay^\to(G, S)$ associated to a group $G$ and a [subset](/page/Subset) $S \subseteq G$ (typically excluding the [identity](/page/Identity) to avoid loops), where the [vertex](/page/Vertex) set is $G$ and there is a directed edge from $g$ to $gs$ for every $g \in G$ and $s \in S$.[](https://www.sciencedirect.com/science/article/pii/S0195669813000905) 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\}$.[](https://faculty.etsu.edu/gardnerr/4127/notes/I-7.pdf) 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](/page/Regular) digraph of degree $|S|$.[](https://www.sciencedirect.com/science/article/pii/S0195669813000905) 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$.[](https://www.sciencedirect.com/science/article/pii/S0195669813000905) Directed Cayley graphs are particularly useful for modeling one-way group actions, such as in the analysis of [semigroup](/page/Semigroup) structures or asymmetric relations in group theory, and they form the basis for Cayley digraphs in combinatorial studies.[](https://www.mdpi.com/2227-7390/12/17/2711) If $S = S^{-1}$, the underlying undirected graph obtained by ignoring edge directions coincides with the standard undirected Cayley graph $\Cay(G, S)$.[](https://faculty.etsu.edu/gardnerr/4127/notes/I-7.pdf) A simple example is the directed Cayley graph of the [cyclic group](/page/Cyclic_group) $\mathbb{Z}/n\mathbb{Z}$ with $S = \{1\}$, which forms a directed [cycle](/page/Cycle) of length $n$: vertices are integers [modulo](/page/Modulo) $n$, with edges $k \to k+1 \pmod{n}$. This graph is strongly connected since $\{1\}$ generates $\mathbb{Z}/n\mathbb{Z}$.[](https://faculty.etsu.edu/gardnerr/4127/notes/I-7.pdf) ## Group-Theoretic Applications ### Geometric Group Theory In [geometric group theory](/page/Geometric_group_theory), Cayley graphs provide a geometric realization of [finitely generated groups](/page/Finitely_generated_group), endowing them with a natural metric structure derived from the graph distance. For a [finitely generated group](/page/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](/page/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](/page/Geodesic) [metric space](/page/Metric_space), where geodesics correspond to shortest words, allowing the study of group elements via paths in the [graph](/page/Graph).[](https://www.ihes.fr/~gromov/wp-content/uploads/2018/08/657.pdf)[](https://press.uchicago.edu/ucp/books/book/chicago/T/bo3641370.html) 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.[](https://www.ams.org/journals/bull/2019-56-01/S0273-0979-2018-01608-X/S0273-0979-2018-01608-X.pdf)[](https://math.uchicago.edu/~may/REU2018/REUPapers/Manchester.pdf) 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.[](https://www.ihes.fr/~gromov/wp-content/uploads/2018/08/657.pdf)[](https://press.uchicago.edu/ucp/books/book/chicago/T/bo3641370.html) Cayley graphs facilitate solving the word problem through [breadth-first search](/page/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](/page/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.[](https://dec41.user.srcf.net/notes/IV_M/topics_in_geometric_group_theory.pdf)[](https://www.isibang.ac.in/~sury/tree.pdf) ### Expansion Properties Cayley graphs exhibit strong [expansion](/page/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](/page/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](/page/Inequality), $h(\Gamma) \geq (d - \lambda_2)/ (2d)$, where $\lambda_2$ is the second-largest eigenvalue of the [adjacency matrix](/page/Adjacency_matrix) of $\Gamma$, providing a lower bound on [expansion](/page/Expansion) in terms of the [spectral gap](/page/Spectral_gap). This relates discrete [expansion](/page/Expansion) to the graph's [spectral](/page/Spectral) properties, ensuring that small sets expand significantly under the neighborhood [operator](/page/Operator).[](https://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf) The [spectral gap](/page/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](/page/Connectivity). For families of Cayley graphs on growing groups, uniform bounds on the [spectral gap](/page/Spectral_gap) yield families of expanders. The Kazhdan constant $K(G, S)$ from [representation theory](/page/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.[](https://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf)[](https://www.math.utah.edu/pcmi12/lecture_notes/BreuillardPCMI.pdf) 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](/page/Phillips)–Sarnak (LPS) graphs, which are Cayley graphs on $\mathrm{[PSL](/page/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.[](https://link.springer.com/content/pdf/10.1007/BF02126799.pdf)[](https://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf) Random Cayley graphs also provably exhibit strong expansion properties. The Alon–Roichman theorem states that for a [finite group](/page/Finite_group) $G$ and $d = C \log |G|$ with sufficiently large [constant](/page/Constant) $C$, a random symmetric generating set $S \subset G$ of [size](/page/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.[](https://web.math.princeton.edu/~nalon/PDFS/exp1.pdf) Recent developments include explicit constructions of high-dimensional expanders from Cayley graphs over $\mathbb{F}_2^n$, advancing applications in [theoretical computer science](/page/Theoretical_computer_science) as of 2024.[](https://www.ias.edu/video/simple-high-dimensional-expanders-cayley-graphs) These expansion properties of Cayley graphs have significant applications in [pseudorandomness](/page/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.[](https://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf) ## Advanced Classifications ### Integral Classification A Cayley graph Cay(G, S) is [integral](/page/Integral) if all eigenvalues of its [adjacency matrix](/page/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](/page/Degree) χ(1) of χ.[](https://arxiv.org/pdf/1809.09829) Therefore, Cay(G, S) is [integral](/page/Integral) if and only if λ_χ is an integer for every irreducible character χ of G.[](https://arxiv.org/pdf/1809.09829) 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](/page/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](/page/Representation_theory) of G.[](https://arxiv.org/pdf/1809.09829) 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.[](https://www.combinatorics.org/ojs/index.php/eljc/article/download/v16i1r122/pdf/) 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](/page/Integral) Cayley graphs, but not all generating sets S yield integrality. For example, the [symmetric group](/page/Symmetric_group) S_3 admits [integral](/page/Integral) Cayley graphs for various S, including those generating the group, due to its small [character](/page/Character) table with integer-valued sums for appropriate subsets.[](https://www.combinatorics.org/ojs/index.php/eljc/article/download/v16i1r122/pdf/) In contrast, for the [alternating group](/page/Alternating_group) A_5, while the complete Cayley graph is [integral](/page/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.[](https://www.combinatorics.org/ojs/index.php/eljc/article/download/v16i1r122/pdf/) A finer classification considers Cayley integral groups, those for which every undirected Cayley graph (with S = S^{-1}, e ∉ S) is [integral](/page/Integral). The finite such groups are precisely the abelian groups of exponent dividing 4 or 6, the [symmetric group](/page/Symmetric_group) S_3, the [non-abelian group](/page/Non-abelian_group) of [order](/page/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](/page/Quaternion_group).[](https://arxiv.org/pdf/1307.5413) For these groups, the character values ensure that ∑_{s ∈ S} χ(s) ∈ ℤ for all possible symmetric S and all χ. A_5 is not Cayley [integral](/page/Integral), as it admits non-integral Cayley graphs for certain S.[](https://arxiv.org/pdf/1307.5413) ### Normal and Eulerian Generating Sets A generating set $S$ for a [finite group](/page/Finite_group) $G$ is called [normal](/page/Normal_subgroup) 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](/page/Union) of conjugacy classes of $G$.[](https://arxiv.org/pdf/2401.15306) For such a [normal](/page/Normal_subgroup) 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](/page/Normal_subgroup) Cayley graph, meaning that the [right regular representation](/page/Regular_representation) of $G$ is a [normal subgroup](/page/Normal_subgroup) of the [automorphism group](/page/Automorphism_group) $\mathrm{Aut}(\mathrm{Cay}(G, S))$.[](https://www.sciencedirect.com/science/article/abs/pii/S0012365X22000401) This normality enhances the symmetry of the graph, aligning left and right multiplications by group elements and often resulting in edge-transitivity.[](https://terrytao.wordpress.com/2010/07/10/cayley-graphs-and-the-geometry-of-groups/) 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.[](https://www.combinatorics.org/ojs/index.php/eljc/article/view/v31i3p27) 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](/page/Trail) traversing each edge exactly once). By standard [graph theory](/page/Graph_theory), an undirected connected graph is Eulerian if and only if every [vertex](/page/Vertex) has even [degree](/page/Degree). Since $\mathrm{Cay}(G, S)$ is $|S|$-[regular](/page/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](/page/Adjacency_matrix)). Specifically, if $S$ is a [normal](/page/Normal) [subset](/page/Subset) that is also power-closed—meaning $s \in S$ implies $s^k \in S$ for all [integers](/page/Integer) $k$ coprime to the order of $s$—then all eigenvalues of $\mathrm{Cay}(G, S)$ are [integers](/page/Integer).[](https://link.springer.com/article/10.1007/s10469-019-09550-2) This connection links [normal](/page/Normal) sets to [integral](/page/Integral) Cayley graphs. Moreover, in Cayley [integral](/page/Integral) groups (finite groups $G$ where every connected Cayley graph is [integral](/page/Integral)), every minimal generating set $S$ yields an [integral](/page/Integral) graph, and [normal](/page/Normal) subsets frequently align with this property due to their conjugation invariance facilitating [integer](/page/Integer) [character](/page/Character) sums in the eigenvalue [formula](/page/Formula) $\sum_{s \in S} \chi(s)$ for irreducible characters $\chi$. Finite abelian Cayley [integral](/page/Integral) groups are precisely those of exponent dividing 4 or 6, while non-abelian examples include $S_3$ and the [dihedral group](/page/Dihedral_group) of order 8.[](https://link.springer.com/article/10.1007/s10469-019-09550-2)[](https://www.combinatorics.org/ojs/index.php/eljc/article/view/v17i1r81)[](https://www.sciencedirect.com/science/article/pii/S019566981300276X) ## Applications in Other Fields ### Combinatorics and Graph Theory Cayley graphs play a significant role in [enumerative combinatorics](/page/Enumerative_combinatorics) through the study of their Hamiltonicity. It is a classical result that every connected Cayley graph on a finite [abelian group](/page/Abelian_group) admits a Hamiltonian cycle.[](https://www.math.ucla.edu/~pak/papers/hamcayley9.pdf) 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](/page/Vertex-transitive_graph) contains a [Hamiltonian path](/page/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.[](https://www.sciencedirect.com/science/article/pii/S0012365X09000776)[](https://arxiv.org/abs/2407.00646) Counterexamples to the cycle version known only for non-Cayley vertex-transitive graphs.[](https://www.sciencedirect.com/science/article/pii/S0012365X09000776) In [extremal graph theory](/page/Extremal_graph_theory), Cayley graphs are central to the degree-diameter problem, which seeks the maximum number of vertices in a [graph](/page/Graph) of given maximum degree $d$ and [diameter](/page/Diameter) $k$. The [Moore](/page/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](/page/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](/page/Diameter) relative to degree and order, with minimal [diameter](/page/Diameter) values for fixed degree and order frequently realized by Cayley graphs on specific groups like elementary abelian or dihedral groups.[](https://www.combinatorics.org/files/Surveys/ds14/ds14v2-2013.pdf) The isomorphism problem for Cayley graphs—determining whether two such graphs are isomorphic—ties into broader [computational complexity](/page/Computational_complexity) questions in [graph theory](/page/Graph_theory). In general, deciding isomorphism between two Cayley graphs is GI-complete, meaning it is as hard as the general [graph isomorphism problem](/page/Graph_isomorphism_problem), which is not known to be in [P](/page/P′′) but has quasi-polynomial time algorithms. This [complexity](/page/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](/page/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](/page/Isomorphism). The total count depends on the underlying group structure; for example, over cyclic groups of order $n$, the [enumeration](/page/Enumeration) involves summing over subsets closed under inversion. Asymptotically, almost all Cayley digraphs on a fixed group have the minimal possible [automorphism group](/page/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](/page/Enumerative_combinatorics), such as Polya [enumeration](/page/Enumeration) techniques applied to group actions on graphs.[](https://link.springer.com/article/10.1007/s10231-021-01163-w) A key structural theorem in this context states that connected Cayley graphs achieve optimal [connectivity](/page/Connectivity) among vertex-transitive graphs, with both vertex-[connectivity](/page/Connectivity) and edge-[connectivity](/page/Connectivity) equal to the [degree](/page/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](/page/Degree) itself, unlike general vertex-transitive graphs which may have [connectivity](/page/Connectivity) as low as $2(\delta + 1)/3$. This property underscores the robustness of Cayley graphs in extremal settings, where they maximize [connectivity](/page/Connectivity) for their [symmetry](/page/Symmetry) class.[](http://www.math.clemson.edu/~sgao/papers/Cayley.pdf) ### Computer Science and Networks Cayley graphs serve as models for interconnection networks in parallel and [distributed computing](/page/Distributed_computing) systems due to their vertex-transitivity, which ensures uniform routing properties and [fault tolerance](/page/Fault_tolerance). For instance, the [hypercube](/page/Hypercube) network, a prominent [topology](/page/Topology) in early parallel computers like the [Connection Machine](/page/Connection_Machine), is the Cayley graph of the [elementary abelian group](/page/Elementary_abelian_group) $\mathbb{Z}_2^n$ with generators corresponding to bit flips.[](https://arxiv.org/pdf/1703.08109) This structure provides logarithmic [diameter](/page/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.[](https://ieeexplore.ieee.org/document/737700/) In [parallel computing](/page/Parallel_computing), Cayley graphs facilitate [routing](/page/Routing) algorithms that exploit their [algebraic structure](/page/Algebraic_structure) for optimal path finding. Vertex-transitivity allows for simple, distributed [routing](/page/Routing) schemes where messages follow group operations to reach destinations in diameter steps, as demonstrated in general-purpose algorithms for Cayley-based architectures.[](https://www.sciencedirect.com/science/article/pii/0166218X9290005U) For [gossip](/page/Gossip) algorithms, which involve all-to-all communication for tasks like [matrix multiplication](/page/Matrix_multiplication) or [data aggregation](/page/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.[](https://link.springer.com/chapter/10.1007/3-540-61576-8_91) These properties make Cayley graphs suitable for fault-tolerant [routing](/page/Routing) in Borel Cayley graphs, where algorithms tolerate up to degree-minus-one faults while maintaining short paths.[](https://journals.sagepub.com/doi/10.1155/2012/124245) Cayley graphs underpin expander codes in modern [coding theory](/page/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](/page/Computation) with spectral guarantees from the graph's eigenvalues.[](https://arxiv.org/pdf/2508.10510) These codes, often built on Ramanujan Cayley graphs, connect to quantum low-density parity-check codes and provide interactive [oracle](/page/Oracle) proofs of proximity for verifiable [computation](/page/Computation).[](https://wp.math.berkeley.edu/drp/wp-content/uploads/sites/18/2025/05/2025_Spring_Dalal.pdf) The [Rubik's Cube](/page/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](/page/Diameter) of 20 in the quarter-turn [metric](/page/Metric), known as God's number, computed through exhaustive search and symmetry exploitation.[](https://mathworld.wolfram.com/RubiksGraph.html) A simplified model uses the Cayley graph of $S_8$ quotiented by its center to capture corner permutations, illustrating shortest paths for [subgroup](/page/Subgroup) resolutions.[](http://sporadic.stanford.edu/bump/match/morepolished.pdf) In [cryptography](/page/Cryptography), Cayley graphs of [elliptic curve](/page/Elliptic_curve) groups support [discrete](/page/Discrete) logarithm-based protocols by providing expander-like structures for secure [key exchange](/page/Key_exchange). Constructions from ray class groups yield Cayley expanders with GRH-conditional eigenvalue bounds, enhancing the hardness of [discrete](/page/Discrete) logs on [elliptic curves](/page/Elliptic_curve) used in standards like NIST curves.[](https://arxiv.org/abs/0811.0647) These graphs enable efficient hash functions and contribute to post-quantum schemes by modeling [isogeny](/page/Isogeny) walks on supersingular [elliptic curves](/page/Elliptic_curve).[](https://math.mit.edu/~drew/vantage/GalbraithSlides.pdf) Recent advances in [quantum computing](/page/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.[](https://link.springer.com/article/10.1007/s11128-024-04385-y) Post-2020 studies on extraspecial groups' Cayley graphs reveal fractional revivals in continuous-time walks, with applications to quantum search on non-abelian structures.[](https://ui.adsabs.harvard.edu/abs/2020arXiv201107566S/abstract) ## 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*.{{grok:render&&&type=render_inline_citation&&&citation_id=1&&&citation_type=wikipedia}} In this short note, Cayley described a method to represent finite groups using diagrams that illustrate the connections between group elements based on [multiplication](/page/Multiplication) by generators, providing a visual tool for exploring group [structure](/page/Structure). The primary motivation for this graphical approach was to visualize the symmetric nature of group [multiplication](/page/Multiplication) tables, transforming the tabular representation of [abstract](/page/Abstract) group operations into intuitive diagrams that highlight the regularity and [connectivity](/page/Connectivity) inherent in [group theory](/page/Theory). Cayley sought to make the algebraic relations more accessible by depicting how generators link elements, emphasizing the [symmetry](/page/Symmetry) and closure properties of the group. Cayley's early examples focused on symmetric groups and permutations, such as the [symmetric group](/page/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](/page/Subgroup) relations among permutation groups. A notable predecessor to Cayley's work is William Rowan Hamilton's [Icosian game](/page/Icosian_game) from the 1850s, a puzzle involving finding [Hamiltonian](/page/Hamiltonian) cycles on the dodecahedral graph. This game highlighted graph-theoretic explorations of symmetric structures akin to those later formalized in group diagrams.[](https://mathworld.wolfram.com/IcosianGame.html) Cayley himself did not use the term "Cayley graph"; this nomenclature was introduced later in the [20th century](/page/20th_century) by H. S. M. Coxeter in 1938.[](https://doi.org/10.1007/978-1-4613-0433-8_1) ### Modern Developments In the mid-20th century, advancements in [Cayley graph](/page/Cayley_graph) [theory](/page/Theory) focused on algorithmic applications, particularly through Schreier coset graphs derived from the Reidemeister-Schreier [theorem](/page/Theorem). This [theorem](/page/Theorem), originally established in the late 1920s, enabled the construction of presentations for [subgroups](/page/Subgroup) via coset enumerations, with Schreier coset graphs providing a graphical [representation](/page/Representation) of group actions on cosets. By the 1930s and 1940s, these graphs became essential for computational [group theory](/page/Group_theory), facilitating algorithms to determine [subgroup](/page/Subgroup) structures and normal forms in finitely presented groups.[](https://www.ams.org/journals/bull/2019-56-02/S0273-0979-2018-01610-8/S0273-0979-2018-01610-8.pdf) 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](/page/Geometric_group_theory), emphasizing asymptotic behavior and quasi-isometries of Cayley graphs. Concurrently, in 1988, Alexander Lubotzky, Ralph Phillips, and [Peter Sarnak](/page/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](/page/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](/page/Spectral_graph_theory) and connectivity. Progress in [integral](/page/Integral) classifications emerged in the late [1990s](/page/1990s) and [2000s](/page/2000s), with Walter Klotz and Torsten Sander classifying abelian Cayley [integral](/page/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](/page/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.[](https://iopscience.iop.org/article/10.1088/0305-4470/39/3/011) Random Cayley graphs, studied in 2002, demonstrated expander-like properties [almost surely](/page/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](/page/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.[](https://arxiv.org/abs/2410.03424)

References

  1. [1]
    [PDF] CAYLEY GRAPHS Definition 1.1. Let H be a finite group and let S ...
    In this short note we give an introduction to some elementary properties of Cayley graphs.The first section covers the definition and gives some basic ...
  2. [2]
    [PDF] Cayley graphs - OSU Math
    Cayley graphs give a way of encoding information about group in a graph. Given a group with a, typically finite, generating set, we can form a Cayley Graph ...
  3. [3]
    GraphTheory
    The Cayley graph of a group G with a given set of generators is a labeled directed graph. The vertices of this graph are the group elements, and for each g in G ...
  4. [4]
    Desiderata and Suggestions: No. 2. The Theory of Groups - jstor
    BY PROFESSOR CAYLEY, Cambridqe, Enqland. No. 2.-THE THEORY OF GROUPS: GRAPHICAL REPRESENTATION. IN regard to a substitution-group of the order n upon the ...
  5. [5]
    [PDF] the topology of cayley graphs - UChicago Math
    Sep 2, 2019 · The aim of this paper is to discuss the topological properties of. Cayley graphs as a means of demonstrating connections between group the- ory ...
  6. [6]
    [PDF] Some mathematical properties of Cayley digraphs with applications ...
    Many well-known interconnection networks are Cayley (di)graphs or coset graphs. For example, hypercube, butterfly, and cube-connected cycles networks are Cayley.
  7. [7]
    [PDF] Iterative construction of Cayley Expander graphs
    Expanders graphs have been used to solve many fundamental problems in computer science, in topics including network design (e.g. [40, 41, 1]), complexity theory ...
  8. [8]
    [PDF] APPLICATIONS OF CAYLEY GRAPHS, BILINEARITY, AND ...
    We discuss three main topics: the use of Cayley graphs to present an essentially optimal algorithm for the discrete logarithm problem, the extension of ...
  9. [9]
    [PDF] On undirected Cayley graphs
    For example, it is well known that the Cayley graph Cay(G, S) of a group G is symmetric or undirected if and only if S = S−1 . A graph D = (V, E) is said to be.
  10. [10]
    Cayley Graph -- from Wolfram MathWorld
    A directed graph Cayley graph has the same edge multiplicity for each node. A (directed or undirected) Cayley graph is always vertex-transitive, but the ...
  11. [11]
    [PDF] Section 1.5. Circulant Graphs
    Jul 20, 2020 · The graph X(Zn,C) is a circulant directed graph of order n and C is the connection set. Definition. Let Zn denote the additive group of integers ...Missing: Z_n | Show results with:Z_n
  12. [12]
    https://www.math.columbia.edu/~alessandrini/Courses/Undergraduate_Seminars-s2020/Cayley%20Graphs%20of%20Free%20Groups_GSanchez.pdf
  13. [13]
    [PDF] Cayley graph - MATH 415–501, Fall 2021 [3mm] Modern Algebra I
    A finitely generated group G can be visualized via the Cayley graph ... The symmetric group S3 consists of 6 permutations: (1 2 3. 1 2 3),(. 1 2 3. 1 3 ...Missing: S_3 | Show results with:S_3
  14. [14]
    [PDF] Lecture 2.2: Dihedral groups - Mathematical and Statistical Sciences
    Using this generating set, the Cayley diagrams for the dihedral groups all look similar. Here they are for D3 and D4, respectively.
  15. [15]
    [PDF] Chapter 2: Cayley graphs - Mathematical and Statistical Sciences
    Any group with the same Cayley diagram as the Rectangle Puzzle and the 2-Light. Switch Group is called the Klein 4-group, denoted by V4 for vierergruppe, ... What ...
  16. [16]
    [PDF] Finite normal edge-transitive Cayley graphs - ResearchGate
    It is shown that, for a nontrivial group G, each normal edge-transitive Cayley graph for G has at least one homomorphic image which is a normal edge-transitive ...
  17. [17]
    [PDF] Vertex-transitive graphs which are not Cayley graphs
    However, there are vertex-transitive graphs which are not Cayley graphs, the smallest example being the well-known Petersen graph. Such a graph will be called ...
  18. [18]
    Graphs with Given Group and Given Graph-Theoretical Properties
    Nov 20, 2018 · Graphs with Given Group and Given Graph-Theoretical Properties. Published online by Cambridge University Press: 20 November 2018. Gert Sabidussi.Missing: original | Show results with:original
  19. [19]
    [PDF] Structural characterization of Cayley graphs - arXiv
    Sep 27, 2016 · Sabidussi's theorem characterizes the undirected and unlabelled Cayley graphs as the con- nected graphs having a free transitive action by a ...
  20. [20]
    Vertex-transitive graphs which are not Cayley graphs, I
    The Petersen graph on 10 vertices is the smallest example of a vertex-transitive graph which is not a Cayley graph. We consider the problem of determining the ...
  21. [21]
    [PDF] SCHREIER COSET GRAPHS AND THEIR APPLICATIONS
    Abstract. Schreier coset graphs depict the standard permutationrepresentation of a finitely- generated group on the cosets of a subgroup, and accordingly ...
  22. [22]
    [PDF] Notes on the Schreier graphs of the Grigorchuk group
    It is called a Schreier coset graph. The marked Schreier coset graph Γ∗ coset(G, S;H) is the marked Schreier graph of the coset H under the action adjG,H.
  23. [23]
    [PDF] Lecture 3: Computational and group-theoretic methods
    The Schreier coset graph Σ(G, X, H) gives a diagrammatic representation of the natural action of G on cosets of H. This can also be given by a coset table, e.g. ...
  24. [24]
    Cayley digraphs and graphs - ScienceDirect.com
    The recipe to obtain vertex-transitive digraphs is the following, according to a natural extension of Sabidussi's theorem [4]. ... Graph Theory, 67 (2011) ...<|control11|><|separator|>
  25. [25]
    [PDF] Section I.7. Generating Sets and Cayley Digraphs
    Jul 6, 2023 · However, there are more groups than just the ones which are cyclic. Example 7.1. Recall the Klein 4-group, V : ∗ e a b c. e e a b c. a a e c b.Missing: four- | Show results with:four-
  26. [26]
    Study of Cayley Digraphs over Polygroups - MDPI
    Such a graph is called a directed Cayley graph or Cayley digraph of G. Once a Cayley digraph has been constructed for G, it is possible to obtain ...
  27. [27]
    [PDF] HYPERBOLIC GROUPS - M. Gromov - IHES
    Basic examples of hyperbolic spaces are simplicial trees (see 1.4.), where the "product" (x.y) equals the distance from the reference point to the edge joining ...
  28. [28]
    Topics in Geometric Group Theory - The University of Chicago Press
    In this book, Pierre de la Harpe provides a concise and engaging introduction to geometric group theory, a new method for studying infinite groups via their ...
  29. [29]
    Metric geometry of locally compact groups, by Yves Cornulier and ...
    Jan 8, 2018 · These geometric visualizations are precisely the Cayley graphs. The set of vertices of the Cayley graph is naturally a metric space: the ...
  30. [30]
    [PDF] Geometric Group Theory - UChicago Math
    Aug 28, 2018 · The (decorated) Cayley graph Γ(G, S) of a group G with generating set S is the directed graph with edges colored by elements of S and vertex set ...Missing: S_3 | Show results with:S_3
  31. [31]
    [PDF] Part IV - Topics in Geometric Group Theory - Dexter Chua
    We will introduce the basic notions of geometric group theory: Cayley graphs, quasiisometries, the Schwarz–Milnor Lemma, and the connection with algebraic.
  32. [32]
    [PDF] Groups Acting on Trees - Indian Statistical Institute, Bangalore
    The aim here is to give a self-contained presentation of what generally goes by the name of. Bass-Serre theory. This theory studies the structure of groups ...
  33. [33]
    [PDF] Expander graphs and their applications - CS - Huji
    Aug 7, 2006 · EXPANDER GRAPHS AND THEIR APPLICATIONS. 441. We are also grateful for ... SHLOMO HOORY, NATHAN LINIAL, AND AVI WIGDERSON. 3.46. 3.465 n ...
  34. [34]
    [PDF] Amenability and random walks 2 II. Lecture 2: The T
    The final aim of these lectures will be to prove spectral gaps for finite groups and to turn certain Cayley graphs into expander graphs. However in order to do ...
  35. [35]
    Ramanujan graphs
    A large family of explicit k-regular Cayley graphs X is presented. These graphs satisfy a number of extremal combinatorial properties.
  36. [36]
    [PDF] Random Cayley Graphs and Expanders - Math (Princeton)
    Feb 22, 2002 · ... Cayley graph X(Zn,S) of the cyclic group Zn with respect to a subset S of log2 n random elements satisfies. |µ∗. 1[X(A, S)]| ≤ 1 − δ almost ...Missing: Z_n | Show results with:Z_n
  37. [37]
    [PDF] Eigenvalues of Cayley graphs - arXiv
    Apr 22, 2022 · This paper surveys known results on eigenvalues of Cayley graphs, their applications, and related results on Cayley digraphs and ...Missing: Z_n, F_2, S_3,
  38. [38]
    [PDF] Which Cayley graphs are integral?
    Mar 7, 2009 · A Cayley graph is simple and vertex transitive. We denote the symmetric group and the alternating group on n letters by Sn and An, respectively.
  39. [39]
    [PDF] Groups all of whose undirected Cayley graphs are integral
    GROUPS ALL OF WHOSE UNDIRECTED CAYLEY GRAPHS ARE INTEGRAL. 3. Proof. Since S can be obtained by arbitrary finite intersections, unions, or complements of ...
  40. [40]
    [PDF] On 2-integral Cayley graphs - arXiv
    A graph Γ is called k-integral if the extension degree of the splitting field of the characteristic polynomial of Γ over rational field Q is equal to k.
  41. [41]
    Normal and non-normal Cayley graphs for symmetric groups
    A Cayley graph is said to be an NNN-graph if its automorphism group contains two isomorphic regular subgroups where one is normal and the other is non-normal.<|separator|>
  42. [42]
    Cayley graphs and the geometry of groups | What's new - Terry Tao
    Jul 10, 2010 · Cayley graphs have three distinguishing properties: (Regularity) For each colour {s \in S} , every vertex {x} has a single {s} -edge leading ...
  43. [43]
    Automorphism Groups of Cayley Graphs Generated by General ...
    Sep 6, 2024 · In this paper we study the Cayley graph Cay(Sn,T) C a y ( S n , T ) of the symmetric group Sn S n generated by a set of transpositions T T . We ...
  44. [44]
    [PDF] HAMILTONIAN AND EULERIAN CAYLEY GRAPHS OF CERTAIN ...
    2. Let Γ be a Cayley graph of the group G with set generator. Ω, and let |Ω| is even. Then Γ is Eulerian graph. Proof: Let Ω be a set of generators of a group ...
  45. [45]
    Integral Cayley Graphs | Algebra and Logic
    Nov 16, 2019 · Guo, W., Lytkina, D.V., Mazurov, V.D. et al. Integral Cayley Graphs. Algebra Logic 58, 297–305 (2019). https://doi.org/10.1007/s10469-019 ...
  46. [46]
    Integral Cayley Graphs over Abelian Groups
    May 25, 2010 · A finite group Γ Γ is called Cayley integral, if every undirected Cayley graph over Γ Γ is integral. We determine all abelian Cayley integral groups.
  47. [47]
    Groups all of whose undirected Cayley graphs are integral
    Following Klotz and Sander, we call a group G Cayley integral whenever all undirected Cayley graphs over G are integral. Finite abelian Cayley integral groups ...Missing: admit | Show results with:admit
  48. [48]
    [PDF] Hamiltonian Paths in Cayley Graphs
    Nov 9, 2008 · A Cayley graph Γ = Γ(G, S) is defined to be a graph with vertices g ∈ G, and edges (g, gs), (g, gs−1) ∈ G2, where s ∈ S. We shall ignore ...
  49. [49]
    Hamiltonian paths in Cayley graphs - ScienceDirect.com
    Sep 6, 2009 · Lovász conjecture claims that every (connected) Cayley graph contains a Hamiltonian path. Let G be a finite group, and ...
  50. [50]
    [PDF] Moore graphs and beyond: A survey of the degree/diameter problem
    The Moore bound represents not only an upper bound on the number n∆,D of vertices of a graph of maximum degree ∆ and diameter D, but it is also a lower bound on ...
  51. [51]
    On the asymptotic enumeration of Cayley graphs
    Oct 4, 2021 · In this paper, we are interested in the asymptotic enumeration of Cayley graphs. It has previously been shown that almost every Cayley digraph has the smallest ...<|separator|>
  52. [52]
    [PDF] FAULT TOLERANCE OF CAYLEY GRAPHS 1. Introduction Let G be ...
    The Cayley graph X = Cay(G; S) may not be strongly connected, but its strongly connected components are isomorphic. Let G0 be the subgroup generated by S. Then ...
  53. [53]
    [PDF] Cayley graphs and symmetric interconnection networks - arXiv
    Mar 22, 2017 · Since an edge-transitive graph has optimal vertex-connectivity, the opti- mal vertex-connectivity of FQn can also be deduced from Theorem 2.20.
  54. [54]
    Cyclic-cubes: a new family of interconnection networks of even fixed ...
    We introduce a new family of interconnection networks that are Cayley graphs with fixed degrees of any even number greater than or equal to four.
  55. [55]
    Processor interconnection networks from Cayley graphs
    This research can be regarded as a first attempt to find general purpose routing algorithms for interconnection networks.
  56. [56]
    Gossiping in cayley graphs by packets - SpringerLink
    Jun 2, 2005 · Gossiping (also called total exchange or all-to-all communication) is the process of information diffusion in which each node of a network ...
  57. [57]
    Distributed and Fault-Tolerant Routing for Borel Cayley Graphs
    Oct 22, 2012 · We propose a fault-tolerant routing algorithm for BCGs. Our algorithm exploits the vertex-transitivity property of Borel Cayley graphs and ...<|control11|><|separator|>
  58. [58]
    [PDF] Codes on any Cayley Graph have an Interactive Oracle Proof ... - arXiv
    Aug 14, 2025 · Abstract. Interactive Oracle Proofs of Proximity (IOPP) are at the heart of code-based SNARKs, a family of zeroknowledge protocols.
  59. [59]
    [PDF] Expander Codes and Their Construction via Cayley Graphs
    May 20, 2025 · Abstract. This paper takes a dive into expander codes, a fascinating class of error-correcting codes rooted in graph theory, with a focus on ...
  60. [60]
    Rubik's Graph -- from Wolfram MathWorld
    Rubik's graph is the Cayley graph of Rubik's group. The graph diameter of this graph is sometimes known as God's number, and was shown in Aug. 2010 to be equal ...
  61. [61]
    [PDF] Unravelling the (miniature) Rubik's Cube through its Cayley Graph
    Oct 13, 2006 · We assume that S is closed under inverses. Then the vertices of this Cayley graph are the elements of the group, and elements x and y will be ...
  62. [62]
    Expander graphs based on GRH with an application to elliptic curve ...
    Nov 5, 2008 · We present a construction of expander graphs obtained from Cayley graphs of narrow ray class groups, whose eigenvalue bounds follow from the Generalized ...
  63. [63]
    [PDF] Isogeny graphs of elliptic curves - MIT Mathematics
    ▷ A Cayley graph is the Schreier graph of G acting on itself. Steven Galbraith. Isogeny graphs of elliptic curves. Page 6. Expander graphs ...
  64. [64]
    Discrete-time quantum walks on Cayley graphs of Dihedral groups ...
    May 6, 2024 · In this paper, we study discrete-time quantum walks on Cayley graphs corresponding to Dihedral groups, which are graphs with both directed and undirected edges.Missing: post- | Show results with:post-
  65. [65]
    Continuous-time Quantum Walks on Cayley Graphs of Extraspecial ...
    We study continuous-time quantum walks on normal Cayley graphs of certain non-abelian groups, called extraspecial groups. By applying general results for ...Missing: post- | Show results with:post-<|control11|><|separator|>
  66. [66]
    Icosian Game -- from Wolfram MathWorld
    The Icosian Game was invented in 1857 by William Rowan Hamilton. Hamilton sold it to a London game dealer in 1859 for 25 pounds, and the game was subsequently ...Missing: proto- Z_5 Z_4
  67. [67]
    S0273-0979-2018-01610-8.pdf - American Mathematical Society
    Jan 25, 2018 · Recall that the Cayley graph of a group G with respect to a set of generators S is the graph with vertex set V = G and edges E = {{g, gs}|g ∈ G, ...
  68. [68]
    Quantum walks on Cayley graphs - IOPscience
    Dec 21, 2005 · We address the problem of the construction of quantum walks on Cayley graphs. Our main motivation is the relationship between quantum ...Missing: developments | Show results with:developments
  69. [69]
    Discrete-time quantum walk on the Cayley graph of the dihedral group
    Oct 24, 2018 · Cayley graphs are convenient means to study quantum walks exploiting the group-theoretical machinery. In addition, quantum walk on the hypercube ...Missing: developments | Show results with:developments<|control11|><|separator|>
  70. [70]
    [2410.03424] Cayley Graph Propagation - arXiv
    Oct 4, 2024 · We propose CGP, a method to propagate information over a complete Cayley graph structure, thereby ensuring it is bottleneck-free to better alleviate over- ...