Cayley graph

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 makes them particularly good candidates for constructing families of expander graphs.
Definition.
Let formula_1 be a group and formula_2 be a generating set of formula_1. The Cayley graph formula_4 is an edge-colored directed graph constructed as follows:
Not every source requires that formula_2 generate the group. If formula_2 is not a generating set for formula_1, then formula_7 is disconnected and each connected component represents a coset of the subgroup generated by formula_2.
If an element formula_9 of formula_2 is its own inverse, formula_24 then it is typically represented by an undirected edge.
The set formula_2 is sometimes assumed to be symmetric (i.e. formula_26) and not containing the identity element of the group. In this case, the uncolored Cayley graph can be represented as a simple undirected graph.
In geometric group theory, the set formula_2 is often assumed to be finite which corresponds to formula_7 being locally finite.
Characterization.
The group formula_1 acts on itself by left multiplication (see Cayley's theorem). This may be viewed as the action of formula_1 on its Cayley graph. Explicitly, an element formula_65 maps a vertex formula_66 to the vertex formula_67 The set of edges of the Cayley graph and their color is preserved by this action: the edge formula_68 is mapped to the edge formula_69, both having color formula_11. 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:
To recover the group formula_1 and the generating set formula_2 from the unlabeled directed graph formula_73 select a vertex formula_74 and label it by the identity element of the group. Then label each vertex formula_75 of formula_7 by the unique element of formula_1 that maps formula_78 to formula_79 The set formula_2 of generators of formula_1 that yields formula_7 as the Cayley graph formula_83 is the set of labels of out-neighbors of formula_78. 
Schreier coset graph.
If one, instead, takes the vertices to be right cosets of a fixed subgroup formula_135 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 formula_83 are directly tied together: take formula_125 a complete set of irreducible representations of formula_126 and let formula_139 with eigenvalues formula_128. Then the set of eigenvalues of formula_83 is exactly formula_130 where eigenvalue formula_131 appears with multiplicity formula_132 for each occurrence of formula_131 as an eigenvalue of formula_134
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.
Expansion properties.
When formula_26, the Cayley graph formula_83 is formula_149-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 formula_150 with top eigenvalue equal to formula_149, 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: 
For example the group formula_152 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 formula_83 is integral iff the eigenvalues of formula_154 are integral for every representation formula_155 of formula_1.
Cayley integral simple group.
A group formula_1 is Cayley integral simple (CIS) if the connected Cayley graph formula_83 is integral exactly when the symmetric generating set formula_2 is the complement of a subgroup of formula_1. A result of Ahmady, Bell, and Mohar shows that all CIS groups are isomorphic to formula_161, or formula_162 for primes formula_163. It is important that formula_2 actually generates the entire group formula_1 in order for the Cayley graph to be connected. (If formula_2 does not generate formula_1, the Cayley graph may still be integral, but the complement of formula_2 is not necessarily a subgroup.)
In the example of formula_169, the symmetric generating sets (up to graph isomorphism) are
The only subgroups of formula_178 are the whole group and the trivial group, and the only symmetric generating set formula_2 that produces an integral graph is the complement of the trivial group. Therefore formula_178 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 formula_1, in which every symmetric subset formula_2 produces an integral graph formula_83. Note that formula_2 no longer has to generate the entire group.
The complete list of Cayley integral groups is given by formula_185, and the dicyclic group of order formula_186, where formula_187 and formula_188 is the quaternion group. The proof relies on two important properties of Cayley integral groups:
Normal and Eulerian generating sets.
Given a general group formula_1, a subset formula_190 is normal if formula_2 is closed under conjugation by elements of formula_1 (generalizing the notion of a normal subgroup), and formula_2 is Eulerian if for every formula_13, the set of elements generating the cyclic group formula_195 is also contained in formula_2.
A 2019 result by Guo, Lytkina, Mazurov, and Revin proves that the Cayley graph formula_83 is integral for any Eulerian normal subset formula_190, using purely representation theoretic techniques.
The proof of this result is relatively short: given formula_2 an Eulerian normal subset, select formula_200 pairwise nonconjugate so that formula_2 is the union of the conjugacy classes formula_202. Then using the characterization of the spectrum of a Cayley graph, one can show the eigenvalues of formula_83 are given by formula_204 taken over irreducible characters formula_112 of formula_1. Each eigenvalue formula_207 in this set must be an element of formula_208 for formula_209 a primitive formula_210 root of unity (where formula_211 must be divisible by the orders of each formula_212). Because the eigenvalues are algebraic integers, to show they are integral it suffices to show that they are rational, and it suffices to show formula_207 is fixed under any automorphism formula_214 of formula_208. There must be some formula_88 relatively prime to formula_211 such that formula_218 for all formula_219, and because formula_2 is both Eulerian and normal, formula_221 for some formula_222. Sending formula_223 bijects conjugacy classes, so formula_202 and formula_225 have the same size and formula_214 merely permutes terms in the sum for formula_207. Therefore formula_207 is fixed for all automorphisms of formula_208, so formula_207 is rational and thus integral.
Consequently, if formula_231 is the alternating group and formula_2 is a set of permutations given by formula_233, then the Cayley graph formula_234 is integral. (This solved a previously open problem from the Kourovka Notebook.) In addition when formula_235 is the symmetric group and formula_2 is either the set of all transpositions or the set of transpositions involving a particular element, the Cayley graph formula_83 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.
Bethe lattice.
The Bethe lattice or infinite Cayley tree is the Cayley graph of the free group on formula_32 generators. A presentation of a group formula_1 by formula_32 generators corresponds to a surjective map from the free group on formula_32 generators to the group formula_126 and at the level of Cayley graphs to a map from the infinite Cayley tree to the Cayley graph. This can also be interpreted (in algebraic topology) as the universal cover of the Cayley graph, which is not in general simply connected.