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  be a group and  be a generating set of . The Cayley graph  is an edge-colored directed graph constructed as follows:

 Each element  of  is assigned a vertex: the vertex set of  is identified with 
 Each element  of  is assigned a color .
 For every  and , there is a directed edge of color  from the vertex corresponding to  to the one corresponding to . 

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

If an element  of  is its own inverse,  then it is typically represented by an undirected edge.

The set  is sometimes assumed to be  symmetric (i.e. ) 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  is often assumed to be finite which corresponds to  being locally finite.

Examples 
 Suppose that  is the infinite cyclic group and the set  consists of the standard generator 1 and its inverse (−1 in the additive notation); then the Cayley graph is an infinite path.
 Similarly, if  is the finite cyclic group of order  and the set  consists of two elements, the standard generator of  and its inverse, then the Cayley graph is the cycle . More generally, the Cayley graphs of finite cyclic groups are exactly the circulant graphs.
 The Cayley graph of the direct product of groups (with the cartesian product of generating sets as a generating set) is the cartesian product of the corresponding Cayley graphs.  Thus the Cayley graph of the abelian group  with the set of generators consisting of four elements  is the infinite grid on the plane , while for the direct product  with similar generators the Cayley graph is the  finite grid on a torus.

 A Cayley graph of the dihedral group  on two generators  and  is depicted to the left. Red arrows represent composition with . Since  is self-inverse, the blue lines, which represent composition with , are undirected. Therefore the graph is mixed: it has eight vertices, eight arrows, and four edges. The Cayley table of the group  can be derived from the group presentation

A different Cayley graph of  is shown on the right.  is still the horizontal reflection and is represented by blue lines, and  is a diagonal reflection and is represented by pink lines. As both reflections are self-inverse the Cayley graph on the right is completely undirected. This graph corresponds to the presentation

 The Cayley graph of the free group on two generators  and  corresponding to the set  is depicted at the top of the article, and  represents the identity element. Travelling along an edge to the right represents right multiplication by  while travelling along an edge upward corresponds to the multiplication by   Since the free group has no relations, the Cayley graph has no cycles. This Cayley graph is a 4-regular infinite tree and is a key ingredient in the proof of the Banach–Tarski paradox.

 A Cayley graph of the discrete Heisenberg group 

is depicted to the right. The generators used in the picture are the three matrices  given by the three permutations of 1, 0, 0 for the entries . They satisfy the relations , which can also be understood from the picture. This is a non-commutative infinite group, and despite being a three-dimensional space, the Cayley graph has four-dimensional volume growth.

Characterization 
The group  acts on itself by left multiplication (see Cayley's theorem). This may be viewed as the action of  on its Cayley graph. Explicitly, an element  maps a vertex  to the vertex  The set of edges of the Cayley graph and their color is preserved by this action: the edge  is mapped to the edge , both having color . 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  if and only if it admits a simply transitive action of  by graph automorphisms (i.e. preserving the set of directed edges).

To recover the group  and the generating set  from the unlabeled directed graph  select a vertex  and label it by the identity element of the group. Then label each vertex   of  by the unique element of  that maps  to  The set  of generators of  that yields  as the Cayley graph  is the set of labels of out-neighbors of .

Elementary properties 

 The Cayley graph  depends in an essential way on the choice of the set  of generators. For example, if the generating set  has  elements then each vertex of the Cayley graph has  incoming and  outgoing directed edges. In the case of a symmetric generating set  with  elements, the Cayley graph is a regular directed graph of degree 
 Cycles (or closed walks) in the Cayley graph indicate relations between the elements of  In the more elaborate construction of the Cayley complex of a group, closed paths corresponding to relations are "filled in" by polygons. This means that the problem of constructing the Cayley graph of a given presentation  is equivalent to solving the Word Problem for .
 If  is a surjective group homomorphism and the images of the elements of the generating set  for  are distinct, then it induces a covering of graphs
  
where  In particular, if a group  has  generators, all of order different from 2, and the set  consists of these generators together with their inverses, then the Cayley graph  is covered by the infinite regular tree of degree  corresponding to the free group on the same set of generators.
 For any finite Cayley graph, considered as undirected, the vertex connectivity is at least equal to 2/3 of the degree of the graph.  If the generating set is minimal (removal of any element and, if present, its inverse from the generating set leaves a set which is not generating), the vertex connectivity is equal to the degree.  The edge connectivity is in all cases equal to the degree.
 If  is the left-regular representation with  matrix form denoted , the adjacency matrix of  is .
 Every group character  of the group  induces an eigenvector of the adjacency matrix of . When  is Abelian, the associated eigenvalue is 
 which takes the form  for integers 
In particular, the associated eigenvalue of the trivial character (the one sending every element to 1) is the degree of , that is, the order of . If  is an Abelian group, there are exactly  characters, determining all eigenvalues. The corresponding orthonormal basis of eigenvectors is given by  It is interesting to note that this eigenbasis is independent of the generating set .
More generally for symmetric generating sets, take  a complete set of irreducible representations of  and let  with eigenvalue set . Then the set of eigenvalues of  is exactly  where eigenvalue  appears with multiplicity  for each occurrence of  as an eigenvalue of

Schreier coset graph 

If one, instead, takes the vertices to be right cosets of a fixed subgroup  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  are directly tied together: take  a complete set of irreducible representations of  and let  with eigenvalues . Then the set of eigenvalues of  is exactly  where eigenvalue  appears with multiplicity  for each occurrence of  as an eigenvalue of 

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 , the Cayley graph  is -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  with top eigenvalue equal to , 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  has Kazhdan's property (T), and  is a finite, symmetric generating set of , then there exists a constant  depending only on  such that for any finite quotient  of  the Cayley graph of  with respect to the image of  is a -expander. 

For example the group  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  is integral iff the eigenvalues of  are integral for every representation  of .

Cayley integral simple group 

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

In the example of , the symmetric generating sets (up to graph isomorphism) are
:  is a -cycle with eigenvalues 
:  is  with eigenvalues 
The only subgroups of  are the whole group and the trivial group, and the only symmetric generating set  that produces an integral graph is the complement of the trivial group. Therefore  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 , in which every symmetric subset  produces an integral graph . Note that  no longer has to generate the entire group.

The complete list of Cayley integral groups is given by , and the dicyclic group of order , where  and  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 , a subset  is normal if  is closed under conjugation by elements of  (generalizing the notion of a normal subgroup), and  is Eulerian if for every , the set of elements generating the cyclic group  is also contained in .
A 2019 result by Guo, Lytkina, Mazurov, and Revin proves that the Cayley graph  is integral for any Eulerian normal subset , using purely representation theoretic techniques.

The proof of this result is relatively short: given  an Eulerian normal subset, select  pairwise nonconjugate so that  is the union of the conjugacy classes . Then using the characterization of the spectrum of a Cayley graph, one can show the eigenvalues of  are given by  taken over irreducible characters  of . Each eigenvalue  in this set must be an element of  for  a primitive  root of unity (where  must be divisible by the orders of each ). 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  relatively prime to  such that  for all , and because  is both Eulerian and normal,  for some . Sending  bijects conjugacy classes, so  and  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  is the alternating group and  is a set of permutations given by , then the Cayley graph  is integral. (This solved a previously open problem from the Kourovka Notebook.) In addition when  is the symmetric group and  is either the set of all transpositions or the set of transpositions involving a particular element, the Cayley graph  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  generators. A presentation of a group  by  generators corresponds to a surjective map from the free group on  generators to the group  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.

See also 
 Vertex-transitive graph
 Generating set of a group
 Lovász conjecture
 Cube-connected cycles
 Algebraic graph theory
 Cycle graph (algebra)

Notes

External links 
 Cayley diagrams
 

Group theory
Permutation groups
Graph families
Application-specific graphs
Geometric group theory