In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group,[1] 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 expander graphs.

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

Definition

edit

Let   be a group and   be a generating set of  . The Cayley graph   is an edge-colored directed graph constructed as follows:[2]

  • 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 convention 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 often assumed to be finite, especially in geometric group theory, which corresponds to   being locally finite and   being finitely generated.

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

Examples

edit
  • 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.[3] 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.
 
Cayley graph of the dihedral group   on two generators a and b
 
Cayley graph of  , on two generators which are both self-inverse
  • 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, with   being the identity. 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: it is the 4-regular infinite tree. It is a key ingredient in the proof of the Banach–Tarski paradox.
  • More generally, the Bethe lattice or Cayley tree is the Cayley graph of the free group on   generators. A presentation of a group   by   generators corresponds to a surjective homomorphism from the free group on   generators to the group   defining a map from the Cayley tree to the Cayley graph of  . Interpreting graphs topologically as one-dimensional simplicial complexes, the simply connected infinite tree is the universal cover of the Cayley graph; and the kernel of the mapping is the fundamental group of the Cayley graph.
 
Part of a Cayley graph of the Heisenberg group. (The coloring is only for visual aid.)
  • 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.[4]
 
Cayley Q8 graph showing cycles of multiplication by quaternions i, j and k

Characterization

edit

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  . In fact, all automorphisms of the colored directed graph   are of this form, so that   is isomorphic to the symmetry group of  .[note 1][note 2]

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).[5]

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  . Since   is uncolored, it might have more directed graph automorphisms than the left multiplication maps, for example group automorphisms of   which permute  .

Elementary properties

edit
  • 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 among 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  .[1]
  • 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.[6]
  • 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  . The associated eigenvalue is   which, when   is Abelian, 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

edit

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

edit

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.[7]

Geometric group theory

edit

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

edit

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:[8]

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

edit

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

edit

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  .[9] 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.[9]

Cayley integral group

edit

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.[9] 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

edit

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.[10]

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

edit

Cayley graphs were first considered for finite groups by Arthur Cayley in 1878.[2] 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.[11]

See also

edit
  1. ^ Proof: Let   be an arbitrary automorphism of the colored directed graph  , and let   be the image of the identity. We show that   for all  , by induction on the edge-distance of   from  . Assume  . The automorphism   takes any  -colored edge   to another  -colored edge  . Hence  , and the induction proceeds. Since   is connected, this shows   for all  .
  2. ^ It is easy to modify   into a simple graph (uncolored, undirected) whose symmetry group is isomorphic to  : replace colored directed edges of   with appropriate trees corresponding to the colors.

Notes

edit
  1. ^ a b Magnus, Wilhelm; Karrass, Abraham; Solitar, Donald (2004) [1966]. Combinatorial Group Theory: Presentations of Groups in Terms of Generators and Relations. Courier. ISBN 978-0-486-43830-6.
  2. ^ a b Cayley, Arthur (1878). "Desiderata and suggestions: No. 2. The Theory of groups: graphical representation". American Journal of Mathematics. 1 (2): 174–6. doi:10.2307/2369306. JSTOR 2369306. In his Collected Mathematical Papers 10: 403–405.
  3. ^ Theron, Daniel Peter (1988). An extension of the concept of graphically regular representations (Ph.D. thesis). University of Wisconsin, Madison. p. 46. MR 2636729..
  4. ^ Bartholdi, Laurent (2017). "Growth of groups and wreath products". In Ceccherini-Silberstein, Tullio; Salvatori, Maura; Sava-Huss, Ecaterina (eds.). Groups, graphs and random walks: Selected papers from the workshop held in Cortona, June 2–6, 2014. London Math. Soc. Lecture Note Ser. Vol. 436. Cambridge Univ. Press, Cambridge. pp. 1–76. arXiv:1512.07044. ISBN 978-1-316-60440-3. MR 3644003.
  5. ^ Sabidussi, Gert (October 1958). "On a class of fixed-point-free graphs". Proceedings of the American Mathematical Society. 9 (5): 800–4. doi:10.1090/s0002-9939-1958-0097068-7. JSTOR 2033090.
  6. ^ See Theorem 3.7 of Babai, László (1995). "27. Automorphism groups, isomorphism, reconstruction" (PDF). In Graham, Ronald L.; Grötschel, Martin; Lovász, László (eds.). Handbook of Combinatorics. Vol. 1. Elsevier. pp. 1447–1540. ISBN 9780444823465.
  7. ^ White, Arthur T. (1972). "On the genus of a group". Transactions of the American Mathematical Society. 173: 203–214. doi:10.1090/S0002-9947-1972-0317980-2. MR 0317980.
  8. ^ Proposition 1.12 in Lubotzky, Alexander (2012). "Expander graphs in pure and applied mathematics". Bulletin of the American Mathematical Society. 49: 113–162. arXiv:1105.2389. doi:10.1090/S0273-0979-2011-01359-3.
  9. ^ a b c Ahmady, Azhvan; Bell, Jason; Mohar, Bojan (2014). "Integral Cayley graphs and groups". SIAM Journal on Discrete Mathematics. 28 (2): 685–701. arXiv:1307.6155. doi:10.1137/130925487. S2CID 207067134.
  10. ^ Guo, W.; Lytkina, D.V.; Mazurov, V.D.; Revin, D.O. (2019). "Integral Cayley graphs" (PDF). Algebra and Logic. 58 (4): 297–305. arXiv:1808.01391. doi:10.1007/s10469-019-09550-2. S2CID 209936465.
  11. ^ Dehn, Max (2012) [1987]. Papers on Group Theory and Topology. Springer-Verlag. ISBN 978-1461291077. Translated from the German and with introductions and an appendix by John Stillwell, and with an appendix by Otto Schreier.
edit