Cayley graph

The Cayley graph of the free group on two generators a and b
Graph families defined by their automorphisms
distance-transitive → distance-regular ← strongly regular
↓
symmetric (arc-transitive) ← t-transitive, t ≥ 2 skew-symmetric
↓
(if connected)
vertex- and edge-transitive
→ edge-transitive and regular → edge-transitive
↓ ↓ ↓
vertex-transitive → regular → (if bipartite)
biregular
↑
Cayley graph ← zero-symmetric asymmetric

In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group, is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Cayley), and uses a specified set of generators for the group. It is a central tool in combinatorial and geometric group theory. The structure and symmetry of Cayley graphs make them particularly good candidates for constructing expander graphs.

Definition

Let G be a group and S be a generating set of G. The Cayley graph Γ=Γ(G,S) is an edge-colored directed graph constructed as follows:

Not every convention requires that S generate the group. If S is not a generating set for G, then Γ is disconnected and each connected component represents a coset of the subgroup generated by S.

If an element s of S is its own inverse, s=s−1, then it is typically represented by an undirected edge.

The set S is often assumed to be finite, especially in geometric group theory, which corresponds to Γ being locally finite and G being finitely generated.

The set S is sometimes assumed to be symmetric (S=S−1) and not containing the group identity element. In this case, the uncolored Cayley graph can be represented as a simple undirected graph.

Examples

Cayley graph of the dihedral group D4 on two generators a and b
Cayley graph of D4, on two generators which are both self-inverse
Part of a Cayley graph of the Heisenberg group. (The coloring is only for visual aid.)
Cayley Q8 graph showing cycles of multiplication by quaternions i, j and k

Characterization

The group G acts on itself by left multiplication (see Cayley's theorem). This may be viewed as the action of G on its Cayley graph. Explicitly, an element h∈G maps a vertex g∈V(Γ) to the vertex hg∈V(Γ). The set of edges of the Cayley graph and their color is preserved by this action: the edge (g,gs) is mapped to the edge (hg,hgs), both having color cs. In fact, all automorphisms of the colored directed graph Γ are of this form, so that G is isomorphic to the symmetry group of Γ.

The left multiplication action of a group on itself is simply transitive, in particular, Cayley graphs are vertex-transitive. The following is a kind of converse to this:

Sabidussi's Theorem—An (unlabeled and uncolored) directed graph Γ is a Cayley graph of a group G if and only if it admits a simply transitive action of G by graph automorphisms (i.e., preserving the set of directed edges).

To recover the group G and the generating set S from the unlabeled directed graph Γ, select a vertex v1∈V(Γ) and label it by the identity element of the group. Then label each vertex v of Γ by the unique element of G that maps v1 to v. The set S of generators of G that yields Γ as the Cayley graph Γ(G,S) is the set of labels of out-neighbors of v1. Since Γ is uncolored, it might have more directed graph automorphisms than the left multiplication maps, for example group automorphisms of G which permute S.

Elementary properties

Schreier coset graph

If one instead takes the vertices to be right cosets of a fixed subgroup H, one obtains a related construction, the Schreier coset graph, which is at the basis of coset enumeration or the Todd–Coxeter process.

Connection to group theory

Knowledge about the structure of the group can be obtained by studying the adjacency matrix of the graph and in particular applying the theorems of spectral graph theory. Conversely, for symmetric generating sets, the spectral and representation theory of Γ(G,S) are directly tied together: take ρ1,…,ρk a complete set of irreducible representations of G, and let ρi(S)=∑s∈Sρi(s) with eigenvalues Λi(S). Then the set of eigenvalues of Γ(G,S) is exactly ⋃iΛi(S), where eigenvalue λ appears with multiplicity dim⁡(ρi) for each occurrence of λ as an eigenvalue of ρi(S).

The genus of a group is the minimum genus for any Cayley graph of that group.

Geometric group theory

For infinite groups, the coarse geometry of the Cayley graph is fundamental to geometric group theory. For a finitely generated group, this is independent of choice of finite set of generators, hence an intrinsic property of the group. This is only interesting for infinite groups: every finite group is coarsely equivalent to a point (or the trivial group), since one can choose as finite set of generators the entire group.

Formally, for a given choice of generators, one has the word metric (the natural distance on the Cayley graph), which determines a metric space. The coarse equivalence class of this space is an invariant of the group.

Signal Processing

In addition to their role in pure mathematics, Cayley graphs have applications in signal processing and harmonic analysis. The adjacency matrix of a Cayley graph constructed over a finite group encodes the algebraic structure of the group, and its eigenvalues correspond to the spectral coefficients in the basis defined by the group's irreducible representations. For the cyclic group, this recovers the discrete Fourier transform; for the dihedral group, the discrete cosine transform.

Expansion properties

When S=S−1, the Cayley graph Γ(G,S) is |S|-regular, so spectral techniques may be used to analyze the expansion properties of the graph. In particular for abelian groups, the eigenvalues of the Cayley graph are more easily computable and given by λχ=∑s∈Sχ(s) with top eigenvalue equal to |S|, so we may use Cheeger's inequality to bound the edge expansion ratio using the spectral gap.

Representation theory can be used to construct such expanding Cayley graphs, in the form of Kazhdan property (T). The following statement holds:

If a discrete group G has Kazhdan's property (T), and S is a finite, symmetric generating set of G, then there exists a constant c>0 depending only on G,S such that for any finite quotient Q of G the Cayley graph of Q with respect to the image of S is a c-expander.

For example the group G=SL3(ℤ) has property (T) and is generated by elementary matrices and this gives relatively explicit examples of expander graphs.

Integral classification

An integral graph is one whose eigenvalues are all integers. While the complete classification of integral graphs remains an open problem, the Cayley graphs of certain groups are always integral. Using previous characterizations of the spectrum of Cayley graphs, note that Γ(G,S) is integral iff the eigenvalues of ρ(S) are integral for every representation ρ of G.

Cayley integral simple group

A group G is Cayley integral simple (CIS) if the connected Cayley graph Γ(G,S) is integral exactly when the symmetric generating set S is the complement of a subgroup of G. A result of Ahmady, Bell, and Mohar shows that all CIS groups are isomorphic to ℤ/pℤ,ℤ/p2ℤ, or ℤ2×ℤ2 for primes p. It is important that S actually generates the entire group G in order for the Cayley graph to be connected. (If S does not generate G, the Cayley graph may still be integral, but the complement of S is not necessarily a subgroup.)

In the example of G=ℤ/5ℤ, the symmetric generating sets (up to graph isomorphism) are

  • S={1,4}: Γ(G,S) is a 5-cycle with eigenvalues 2,5−12,5−12,−5−12,−5−12
  • S={1,2,3,4}: Γ(G,S) is K5 with eigenvalues 4,−1,−1,−1,−1

The only subgroups of ℤ/5ℤ are the whole group and the trivial group, and the only symmetric generating set S that produces an integral graph is the complement of the trivial group. Therefore ℤ/5ℤ must be a CIS group.

The proof of the complete CIS classification uses the fact that every subgroup and homomorphic image of a CIS group is also a CIS group.

Cayley integral group

A slightly different notion is that of a Cayley integral group G, in which every symmetric subset S produces an integral graph Γ(G,S). Note that S no longer has to generate the entire group.

The complete list of Cayley integral groups is given by ℤ2n×ℤ3m,ℤ2n×ℤ4n,Q8×ℤ2n,S3, and the dicyclic group of order 12, where m,n∈ℤ≥0 and Q8 is the quaternion group. The proof relies on two important properties of Cayley integral groups:

  • Subgroups and homomorphic images of Cayley integral groups are also Cayley integral groups.
  • A group is Cayley integral iff every connected Cayley graph of the group is also integral.

Normal and Eulerian generating sets

Given a general group G, a subset S⊆G is normal if S is closed under conjugation by elements of G (generalizing the notion of a normal subgroup), and S is Eulerian if for every s∈S, the set of elements generating the cyclic group ⟨s⟩ is also contained in S. A 2019 result by Guo, Lytkina, Mazurov, and Revin proves that the Cayley graph Γ(G,S) is integral for any Eulerian normal subset S⊆G, using purely representation theoretic techniques.

The proof of this result is relatively short: given S an Eulerian normal subset, select x1,…,xt∈G pairwise nonconjugate so that S is the union of the conjugacy classes Cl⁡(xi). Then using the characterization of the spectrum of a Cayley graph, one can show the eigenvalues of Γ(G,S) are given by {λχ=∑i=1tχ(xi)|Cl⁡(xi)|χ(1)} taken over irreducible characters χ of G. Each eigenvalue λχ in this set must be an element of ℚ(ζ) for ζ a primitive mth root of unity (where m must be divisible by the orders of each xi). Because the eigenvalues are algebraic integers, to show they are integral it suffices to show that they are rational, and it suffices to show λχ is fixed under any automorphism σ of ℚ(ζ). There must be some k relatively prime to m such that σ(χ(xi))=χ(xik) for all i, and because S is both Eulerian and normal, σ(χ(xi))=χ(xj) for some j. Sending x↦xk bijects conjugacy classes, so Cl⁡(xi) and Cl⁡(xj) have the same size and σ merely permutes terms in the sum for λχ. Therefore λχ is fixed for all automorphisms of ℚ(ζ), so λχ is rational and thus integral.

Consequently, if G=An is the alternating group and S is a set of permutations given by {(12i)±1}, then the Cayley graph Γ(An,S) is integral. (This solved a previously open problem from the Kourovka Notebook.) In addition when G=Sn is the symmetric group and S is either the set of all transpositions or the set of transpositions involving a particular element, the Cayley graph Γ(G,S) is also integral.

History

Cayley graphs were first considered for finite groups by Arthur Cayley in 1878. Max Dehn in his unpublished lectures on group theory from 1909–10 reintroduced Cayley graphs under the name Gruppenbild (group diagram), which led to the geometric group theory of today. His most important application was the solution of the word problem for the fundamental group of surfaces with genus ≥ 2, which is equivalent to the topological problem of deciding which closed curves on the surface contract to a point.

See also