The Cayley graph — geometry of a group

A group is an abstract algebraic object, but we can give it a face — draw each element as a node, each generator s as an edge. The result is the Cayley graph, turning an abstract group into a concrete geometric object. Words like "diameter," "geodesic," "ball of radius r," and "neighbourhood" all gain literal meaning. Arthur Cayley introduced it in 1878, a century before the Rubik's cube — but the cube is its most tactile visualisation.

14.1 Warm-up — first two layers of ⟨R, U⟩

The full cube Cayley graph has 4.3 × 10¹⁹ nodes and ≈ 3.9 × 10²⁰ edges — impossible to render. But we can plot a small subgroup. Below: the first two BFS layers of ⟨R, U⟩ from e. Red edges = R, blue = U. The "asymmetric fan" of a non-Abelian group is already visible — R·U ≠ U·R, so the two-step neighbours bifurcate:

14.2 Interactive — walk it yourself

You are standing at node e. Click any of the 18 generators to traverse that coloured edge to a neighbour. The path is the sequence of edges walked. Wandered back to e? You just closed a loop — the product of the path is the identity, and its length is the order of that element.

14.3 Spheres |S_d| — counting states at radius d

For $e\in G$, the set of states at distance exactly d is $S_d=\{g:d(e,g)=d\}$ — the "sphere of radius d" in Cay(G). The sizes $|S_d|$ come from BFS. For the cube, all 21 values are known exactly (a byproduct of Rokicki et al. 2010):

Sphere sizes grow at a steady factor of about 17.97× (the branching factor — close to 18 but slightly less, due to reductions like "don't immediately undo R"). They reach ~5 × 10¹⁴ around d = 13, then sharply saturate at the peak d = 18, and collapse. By d = 20 only 490 million states remain (including superflip). This is the classic "sphere packing in a finite graph" phenomenon — the outer boundary must shrink.

14.4 Geodesics, shortcuts and algorithms

The shortest path from e to g is a geodesic, of length d(e, g) = |g|_S (the optimal solution length for g). Any alg is a walk on Cay(G); it is a geodesic iff it is optimal. Solvers, in graph-theoretic language, search for geodesics.

A nice contrast: Korf's 1997 algorithm does IDA* directly on Cay(G), using max(corner-PDB, edge-PDB) as a heuristic; Kociemba's two-phase (§10) walks G → G_1, then G_1 → e, sacrificing optimality for speed and bounded length (≤ 24); Rokicki's 2010 proof did a "block-BFS" of Cay(G) using symmetry-quotient classes, costing 35 CPU-years. Three different ways to traverse the same graph.

14.5 Expander properties

The cube's Cayley graph is a "fat" graph — every node has 18 neighbours, diameter only 20, with 4.3 × 10¹⁹ nodes. The "expansion" is near-maximal: for any subset A ⊆ G with |A| ≤ |G|/2, the boundary |∂A| / |A| does not shrink. Mathematically this connects to the spectral gap of the graph Laplacian; practically, it makes random walks "rapidly mix" through G.

14.6 Cayley graph depends on the generating set

The same G, with a different generating set S, gives a different Cayley graph. Distance, diameter, sphere sizes, mixing time — all change. The cube under various metrics:

Note: "⟨R, U⟩ has diameter 26" refers to the subgroup it generates (the 73 million-element subgroup). Within G itself, R and U alone do not generate G, so most states are unreachable — at "distance infinity." This is why "more generators = better": more edges → smaller diameter → easier to solve.

14.7 Visualising the Cayley graph

Forty-three quintillion nodes is unrenderable. But the local structure of a Cayley graph can always be drawn — every node looks like the neighbourhood of e (vertex-transitive). Common visualisation tricks:

• BFS tree — root at e, layers by depth. The "sphere packing in a finite graph" effect shows up directly: a wide middle and thin tips at both ends.
• Quotient graphs — fold G by a subgroup H: nodes = cosets gH, same generators on edges. For example G/G_1 has 2048 nodes — small enough to draw, large enough to be revealing. Thistlethwaite's algorithm essentially walks the chain of quotient graphs G/G_i.
• Symmetry reduction — quotient out the 48 outer cube symmetries; node count drops to ~9 × 10¹⁷. Rokicki's solver uses this to make the BFS tractable.
• Radial layout — on a 2D plane, put e at the centre and every node at distance d on the d-th concentric circle. Counts come from the CAYLEY_SPHERE table above. The shape is unmistakably "olive-like" — fat middle, sharp tips.

14.8 Cayley graphs of other groups

• $\mathbb{Z}$ with $\{+1\}$: an infinite line.
• $\mathbb{Z}\times \mathbb{Z}$ with $\{(1,0),(0,1)\}$: the integer lattice.
• $\mathbb{Z}/n$ with $\{+1\}$: a regular n-gon cycle.
• $F_2=⟨a,b⟩$ (free group): an infinite 4-regular tree — no cycles, you never return to e (because it's free).
• The cube G: sphere sizes from §14.3. Diameter 20, |G| = 4.3 × 10¹⁹. Vertex-transitive, near-regular, highly expanding — a "beautiful finite non-Abelian graph."

14.9 Interactive § sphere sizes on a log scale

The same 21 numbers from §14.3, laid on log paper — the "17.97× branching factor" appears as a constant slope. Hover any bar to see d, |S_d|, percentage of |G|, and the instantaneous branching |S_d| / |S__d-1|. The middle (d = 3 → 13) is almost linear (slope ≈ log₁₀ 17.97 ≈ 1.255); growth visibly slows from d = 16 → 18 (saturation), then collapses by d = 19 → 20 (the sphere-packing tail).

14.10 Interactive § small-group Cayley laboratory

The full 4.3 × 10¹⁹-node graph cannot be drawn — but small Cayley graphs can, and they encode the same geometric intuition. The eight below span Abelian/non-Abelian, one/many generators, cyclic/grid/permutation. Switch between them to see how the same G changes diameter / girth / |E| under different generating sets. Numbers on nodes = d(e, g); click a node → lock + display shortest path coloured by generator.

14.11 Spectral gap and the Cheeger inequality

The Cayley graph Γ is k-regular (k = |S|), so its adjacency matrix A is a symmetric N × N matrix (N = |G|). The spectral theorem gives real eigenvalues $k={\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_N\ge -k$. The spectral gap is $\Delta =k-{\lambda }_2$ (or normalized as $1-{\lambda }_2/k$). Large spectral gap ⇔ graph is "well-connected" ⇔ random walks mix quickly.

For the cube G with HTM, numerical experiments give ${\lambda }_2/k\approx 0.95$, i.e. $\Delta /k\approx 0.05$ ("small" but not zero). This is why a 25-move WCA scramble is nearly uniform but not exactly so — by Cheeger, τ_mix = Θ(log |G| / Δ) ≈ log(4.3 × 10¹⁹) / 0.05 ≈ 905. Tighter random-walk analysis (using spectral gap of the lazy walk + dominant eigenfunctions) gives much smaller bounds; experimentally ~70-100 random moves are visually indistinguishable from uniform.

14.12 Interactive § random walks and mixing time

The lazy random walk on G with generating set S: from e, at each step stay put with probability 1/2 or else left-multiply by a uniformly chosen element of S ∪ S⁻¹. The distribution after t steps is p_t. "Lazy" matters: when G is bipartite under S (e.g. S_n with transpositions — every step flips parity), the non-lazy walk never converges. The lazy version always converges: $p_t\stackrel{t\to \infty }{\to }U=1/|G|$. The mixing time τ_mix(ε) = the smallest t with TV(p_t, U) ≤ ε (standard choice ε = 1/(2e) or 1/4).

The same year, Aldous-Diaconis coined the term "cutoff" — TV stays nearly flat until τ_mix, then drops to 0 within a window of width O(√t). It mirrors the physical intuition of "metastable diffusion → sudden equilibration". Modern work (Berestycki-Şengül 2019, Bordenave-Lacoin-Salez 2019) extends the cutoff phenomenon to non-Abelian conjugacy-invariant walks; it holds for Lie-type groups like PGL.

14.13 Expanders and Ramanujan graphs

A sequence of k-regular graphs $\{{\Gamma }_n\}$ (number of nodes → ∞) is an expander family if there is ε > 0 with h(Γ_n) ≥ ε for all n. Equivalently (by Cheeger): λ₂(A_n)/k ≤ 1 − δ for some δ > 0. Expanders are "the sparsest connected graphs" — O(N) edges keep N nodes globally well-connected. They are a holy grail of CS (error-correcting codes, pseudorandomness, hashing, hardness amplification).

The miracle (Lubotzky-Phillips-Sarnak 1988): they constructed infinite families of Ramanujan graphs via G = PSL₂(𝔽_p) and a generating set S of p + 1 "Hecke operators" coming from quaternion algebras and Ramanujan-Petersson (Deligne 1974). The graphs are (p+1)-regular, diameter O(log |G|), girth (4/3) log_p|G|, with |λ| ≤ 2√p. They are all Cayley graphs.

Three independent expander constructions (Margulis 1973 → LPS 1988 → Alon-Roichman 1994) embody three strategies: "explicit number theory", "quaternion algebras + Ramanujan conjecture", "randomization". Later Reingold-Vadhan-Wigderson (2002) gave a purely combinatorial "zig-zag product" construction. One of the deepest threads in extremal combinatorics of the last 50 years.

14.14 The diameter problem — Babai's conjecture

How small can the diameter of Cay(G, S) be, taken over arbitrary generating sets S? The cube's 20 is one wonder — tiny diameter on a vast state space. What about other groups? Babai (1992) made a bold conjecture:

The conjecture remains open as of 2026. Known progress is "layered":

• Helfgott 2008: G = PSL₂(𝔽_p) gives diam = O((log p)^c), so c = O(1). The proof uses additive-combinatorics tools (Bourgain-Gamburd-Sarnak) to establish a "product theorem": $|A\cdot A\cdot A|\ge |A{|}^{1+ϵ}$ unless A is already close to a subgroup. Turning-point work.
• Pyber-Szabó & Breuillard-Green-Tao (2016): extended Helfgott's bound to all bounded-rank finite simple groups of Lie type (PSL_n, PSp, ...). This portion of Babai's conjecture is fully solved.
• Unbounded rank still open: A_n and PSL_n(𝔽_p) (n → ∞) remain mysteries. Babai-Seress (1992) gave an early subexponential bound $e^{(1+o(1))\sqrt{n\log n}}$; Helfgott-Seress (2014) tightened to $\exp ((\log n{)}^4\log \log n)$ — still far above polylog.

14.15 Growth functions and geometric group theory

For an infinite group G with generating set S, the growth function is ${\gamma }_G^S(n)=|B_n(e)|$, the size of the ball of radius n around e. Different S gives different γ, but the growth class is invariant:

• Polynomial growth: $\gamma (n)\le C{n}^d$. Example: ${\mathbb{Z}}^d$ grows as n^d.
• Exponential growth: $\gamma (n)\ge C{a}^n$ with a > 1. Example: free group F_2 grows as 3·4^{n-1}.
• Intermediate growth: faster than polynomial, slower than exponential. Asked by Milnor (1968); Grigorchuk (1984) gave the first example (the Grigorchuk group).

Gromov's proof introduced Gromov-Hausdorff convergence — rescale a Cayley graph and take a limit, the asymptotic cone is a metric space. This promoted the Cayley graph from "graph-theoretic object" to "geometric object", launching the field of geometric group theory. Later Cannon, Gersten, Bestvina extended this to hyperbolic groups, CAT(0) groups, mapping class groups.

14.16 Cayley's theorem (1854) — every group is a permutation group

A historical aside: a quarter century before drawing his graphs (1878), Cayley had already proved a deeper theorem (1854) that locks abstract groups to concrete permutation groups:

Proof sketch: L_g is a bijection (with inverse $L_{g^{-1}}$), and $L_{gh}(x)=(gh)x=g(hx)=L_g(L_h(x))$, so g ↦ L_g is a group homomorphism. Its kernel is {g : L_g = \mathrm{id}\} = {g : gx = x \;\forall x\} = {e}. Hence the map is injective. ∎

This is the ancestor of "the Cayley graph" — the edge g → g·s is "L_s acting on node g". Visualising Cayley's theorem = drawing each generator s as a "permutation of vertices = arrow set" = the Cayley graph. The title of Cayley's 1878 paper, Graphical representation, is precisely this: drawing his 1854 theorem on paper.

14.17 Open problems and further reading

The cube Cayley graph is one of the most thoroughly studied "extreme" finite objects in mathematics, yet many basic questions remain open:

• 4×4×4 diameter: bounded 22 ≤ diam ≤ 36 (HTM), exact unknown. State space ≈ 7.4 × 10⁴⁵, a factor of 2 × 10²⁶ larger than 3×3×3 — no Rokicki-style global BFS is feasible.
• Analytic spectral gap for the cube: λ₂/k ≈ 0.95 is numerical only; no closed form. For Abelian Cayley graphs the spectrum is Fourier; for the cube it requires character sums over G's ~80 irreps.
• Exact cube mixing time: ≥ 26 (Bordoni-Reiter 2024); ≤ 70 (numerical); exact value and cutoff window unknown.
• QTM vs HTM diameter: 26 vs 20. Both proven exact. But why the gap is exactly 6 has no analytic explanation — it is a global rearrangement effect of rewiring the graph.
• Babai's conjecture for A_n and unbounded rank: open as of 2026 (§14.14).
• Lovász Hamilton path conjecture (1969): every connected Cayley graph has a Hamiltonian cycle (up to four exceptions). For the cube: yes (Curtis 1970). The general conjecture remains open.

References (24 entries)