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_76 select a vertex formula_77 and label it by the identity element of the group. Then label each vertex formula_78 of formula_7 by the unique element of formula_1 that maps formula_81 to formula_82 The set formula_2 of generators of formula_1 that yields formula_7 as the Cayley graph formula_86 is the set of labels of out-neighbors of formula_81. Schreier coset graph. If one, instead, takes the vertices to be  right cosets of a fixed subgroup formula_138 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_86 are directly tied together: take formula_128 a complete set of irreducible representations of formula_129 and let formula_130 with eigenvalues formula_131. Then the set of eigenvalues of formula_86  is exactly formula_133 where eigenvalue formula_134 appears with multiplicity formula_135 for each occurrence of formula_134 as an eigenvalue of formula_137 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_150, the Cayley graph formula_86 is formula_152-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_153 with top eigenvalue equal to formula_152, 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_165 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_86 is integral iff the eigenvalues of formula_167 are integral for every representation formula_168 of formula_1. Cayley integral simple group. A group formula_1 is Cayley integral simple (CIS) if the connected Cayley graph formula_86 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_174, or formula_175 for primes formula_176. 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_182, the symmetric generating sets (up to graph isomorphism) are The only subgroups of formula_191 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_191 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_86. Note that formula_2 no longer has to generate the entire group. The complete list of Cayley integral groups is given by formula_198, and the dicyclic group of order formula_199, where formula_200 and formula_201 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_203 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_208 is also contained in formula_2. A 2019 result by Guo, Lytkina, Mazurov, and Revin proves that the Cayley graph formula_86 is integral for any Eulerian normal subset formula_203, using purely representation theoretic techniques. The proof of this result is relatively short: given formula_2 an Eulerian normal subset, select formula_213 pairwise nonconjugate so that formula_2 is the union of the conjugacy classes formula_215. Then using the characterization of the spectrum of a Cayley graph, one can show the eigenvalues of formula_86 are given by  formula_217 taken over irreducible characters formula_115 of formula_1. Each eigenvalue formula_220 in this set must be an element of formula_221 for formula_222 a primitive formula_223 root of unity (where formula_224 must be divisible by the orders of each formula_225). 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_220 is fixed under any automorphism formula_227 of formula_221. There must be some formula_91 relatively prime to formula_224 such that formula_231 for all formula_232, and because formula_2 is both Eulerian and normal, formula_234 for some formula_235. Sending  formula_236 bijects conjugacy classes, so formula_215 and formula_238 have the same size and formula_227 merely permutes terms in the sum for formula_220. Therefore formula_220 is fixed for all automorphisms of formula_221, so formula_220 is rational and thus integral. Consequently, if formula_244 is the alternating group and formula_2 is a set of permutations given by formula_246, then the Cayley graph formula_247 is integral. (This solved a previously open problem from the Kourovka Notebook.) In addition when formula_248 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_86 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_129 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.