Skip to content

Cayley Graph

A graph with group elements as vertices and edges given uniformly by multiplication by a chosen generating set.

Version
v1 · 2026-10-03 · History
Domain-specific #
13049

Core Idea

Given a group \(G\) and chosen generating set \(S\), a Cayley graph has the elements of \(G\) as vertices. Under a declared right-multiplication convention, each \(g\) has an edge to \(gs\) for every \(s\in S\). The same multiplication rule works at every vertex. The exact graph depends on \(S\); it is not determined by the group name alone.[ref-daa81b0b9ac1][ref-1964c4ffdafa]

Scope of Application

University of New Brunswick illustrates the construction with the six symmetries of a triangle and rotation/reflection generators. Columbia's lecture represents the binary \(n\)-cube using \((\mathbb Z/2\mathbb Z)^n\) and coordinate-flip generators. Labelled paths correspond to products of generators, making group words visible as routes. For finite generating sets, different Cayley graphs of one group have quasi-isometric path metrics, not necessarily equal local edges or exact distances.[ref-daa81b0b9ac1][ref-1964c4ffdafa][^ref-42eb9b597a6e]

Clarity

Specify multiplication side, edge direction and whether \(S\) includes inverses. Ordinary undirected shortest-path distance matches word length in \(S^{\pm1}\); a directed \(S\)-only graph need not allow every forward path in an infinite group. Vertex transitivity or a visually symmetric drawing alone does not demonstrate the group/generator edge rule.[ref-daa81b0b9ac1][ref-42eb9b597a6e]

Manages Complexity

One repeated local rule replaces a large multiplication table: from each group element, multiply by each chosen generator. Paths then encode compound products. Suppressing edge labels may simplify a drawing but can erase the information needed to read path words or distinguish generating sets.[^ref-daa81b0b9ac1]

Abstract Reasoning

To test a proposed Cayley representation, identify a group, a generating set and a bijection between group elements and vertices. Check that every proposed generator edge is uniform multiplication. For a path, multiply labels in the stated order; a closed path at the identity represents an identity word. This does not by itself solve every group's word problem.[^ref-daa81b0b9ac1]

Knowledge Transfer

The construction transfers literally from a dihedral symmetry group to a binary-vector hypercube; only the group elements and generators change. Live prime Network is a semantic node-edge genus, but its current strict Reservoir-Flux Network ancestor would wrongly impose conserved stocks/flows on Cayley graphs. Cayley Transform is a separate live abstraction sharing only the historical name.

[^ref-daa81b0b9ac1]: Nicholas Touikan, Cayley Graphs, University of New Brunswick MATH 6022, §1.5. [^ref-1964c4ffdafa]: Columbia University CS E6204, Lecture 6: Cayley Graphs, adapted from Brian Alspach, PDF pp. 3, 12–13. [^ref-42eb9b597a6e]: George Hyun, “Hyperbolicity and the Word Problem”, University of Chicago REU paper (August 19, 2013), §5, PDF pp. 8–9, Lemma 5.4.

Neighborhood in Abstraction Space

Cayley Graph sits in a moderately populated region (59th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Graph Structures & Combinatorial Objects (44 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08