View source for Cayley graph

{{Short description|Graph defined from a mathematical group}}
[[Image:Cayley graph of F2.svg|right|thumb|The Cayley graph of the [[free group]] on two generators ''a'' and ''b'']]
{{Graph families defined by their automorphisms}}
In [[mathematics]], a '''Cayley graph''', also known as a '''Cayley color graph''', '''Cayley diagram''', '''group diagram''', or '''color group''',<ref name = CGT>{{cite book |author-link=Wilhelm Magnus |first1=Wilhelm |last1=Magnus |first2=Abraham |last2=Karrass |author3-link=Baumslag–Solitar group |first3=Donald |last3=Solitar |title=Combinatorial Group Theory: Presentations of Groups in Terms of Generators and Relations |url=https://books.google.com/books?id=1LW4s1RDRHQC&pg=PR2 |year=2004 |orig-year=1966 |publisher=Courier |isbn=978-0-486-43830-6 }}</ref> is a [[Graph (discrete mathematics)|graph]] that encodes the abstract structure of a [[group (mathematics)|group]]. Its definition is suggested by [[Cayley's theorem]] (named after [[Arthur Cayley]]), and uses a specified [[generating set of a group|set of generators]] for the group. It is a central tool in [[combinatorial group theory|combinatorial]] and [[geometric group theory]]. The structure and symmetry of Cayley graphs makes them particularly good candidates for constructing [[expander graphs]].

== Definition ==
Let <math>G</math> be a [[group (mathematics)|group]] and <math>S</math> be a [[generating set of a group|generating set]] of <math>G</math>. The Cayley graph <math>\Gamma = \Gamma(G,S)</math> is an [[Edge coloring|edge-colored]] [[directed graph]] constructed as follows:<ref name=Cayley78>{{cite journal|first1= Arthur |last1=Cayley|journal= American Journal of Mathematics | year=1878|volume=1|issue=2|pages=174–6|title=Desiderata and suggestions: No. 2. The Theory of groups: graphical representation | url=https://babel.hathitrust.org/cgi/pt?id=uc1.$c239465;view=1up;seq=194|jstor=2369306|doi=10.2307/2369306}} In his Collected Mathematical Papers 10: 403–405.</ref>

* Each element <math>g</math> of <math>G</math> is assigned a vertex: the vertex set of <math>\Gamma</math> is identified with <math>G.</math>
* Each element <math>s</math> of <math>S</math> is assigned a color <math>c_s</math>.
* For every <math>g \in G</math> and <math>s \in S</math>, there is a directed edge of color <math>c_s</math> from the vertex corresponding to <math>g</math> to the one corresponding to <math>gs</math>. 

Not every convention requires that <math>S</math> generate the group. If <math>S</math> is not a generating set for <math>G</math>, then <math>\Gamma</math> is [[connectivity (graph theory)|disconnected]] and each connected component represents a coset of the subgroup generated by <math>S</math>.

If an element <math>s</math> of <math>S</math> is its own inverse, <math>s = s^{-1},</math> then it is typically represented by an undirected edge.

The set <math>S</math> is often assumed to be finite, especially in [[geometric group theory]], which corresponds to <math>\Gamma</math> being locally finite and <math>G</math> being finitely generated.

The set <math>S</math> is sometimes assumed to be [[Symmetric set|symmetric]] (<math>S = S^{-1}</math>) and not containing the group [[identity element]]. In this case, the uncolored Cayley graph can be represented as a simple undirected [[graph (discrete mathematics)|graph]].

== Examples ==
* Suppose that <math>G=\Z</math> is the infinite cyclic group and the set <math>S</math> consists of the standard generator 1 and its inverse (−1 in the additive notation); then the Cayley graph is an infinite path.
* Similarly, if <math>G=\Z_n</math> is the finite [[cyclic group]] of order <math>n</math> and the set <math>S</math> consists of two elements, the standard generator of <math>G</math> and its inverse, then the Cayley graph is the [[cycle graph|cycle]] <math>C_n</math>. More generally, the Cayley graphs of finite cyclic groups are exactly the [[circulant graph]]s.
* 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 graphs|cartesian product]] of the corresponding Cayley graphs.<ref>{{cite thesis | last = Theron | first = Daniel Peter | mr = 2636729 | page = 46 | publisher = University of Wisconsin, Madison | type = Ph.D. thesis | title = An extension of the concept of graphically regular representations | year = 1988}}.</ref>  Thus the Cayley graph of the abelian group <math>\Z^2</math> with the set of generators consisting of four elements <math>(\pm 1,0),(0,\pm 1)</math> is the infinite [[grid graph|grid]] on the plane <math>\R^2</math>, while for the direct product <math>\Z_n \times \Z_m</math> with similar generators the Cayley graph is the <math>n \times m</math> finite grid on a [[torus]].

[[Image:Dih 4 Cayley Graph; generators a, b.svg|220px|left|thumb|Cayley graph of the dihedral group <math>D_4</math> on two generators ''a'' and ''b'']]
[[File:Dih 4 Cayley Graph; generators b, c.svg|170px|right|thumb|Cayley graph of <math>D_4</math>, on two generators which are both self-inverse]]
* A Cayley graph of the [[dihedral group]] <math>D_4</math> on two generators <math>a</math> and <math>b</math> is depicted to the left. Red arrows represent composition with <math>a</math>. Since <math>b</math> is [[Cayley table|self-inverse]], the blue lines, which represent composition with <math>b</math>, are undirected. Therefore the graph is mixed: it has eight vertices, eight arrows, and four edges. The [[Cayley table]] of the group <math>D_4</math> can be derived from the [[presentation of a group|group presentation]] <math display="block"> \langle a, b \mid a^4 = b^2 = e, a b = b a^3 \rangle. </math> A different Cayley graph of <math>D_4</math> is shown on the right. <math>b</math> is still the horizontal reflection and is represented by blue lines, and <math>c</math> 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 <math display="block"> \langle b, c \mid b^2 = c^2 = e, bcbc = cbcb \rangle. </math>
* The Cayley graph of the [[free group]] on two generators <math>a</math> and <math>b</math> corresponding to the set <math>S = \{a, b, a^{-1}, b^{-1}\}</math> is depicted at the top of the article, with <math>e</math> being the identity. Travelling along an edge to the right represents right multiplication by <math>a,</math> while travelling along an edge upward corresponds to the multiplication by <math>b.</math>  Since the free group has no [[Presentation of a group|relations]], the Cayley graph has no [[Cycle (graph theory)|cycles]]: it is the 4-[[regular graph|regular]] infinite [[Tree (graph theory)|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 <math>n</math> generators. A [[Presentation of a group|presentation]] of a group <math>G</math> by <math>n</math> generators corresponds to a surjective [[Group homomorphism|homomorphism]] from the free group on <math>n</math> generators to the group <math>G,</math> defining a map from the Cayley tree to the Cayley graph of <math>G</math>. Interpreting graphs [[Topology|topologically]] as one-dimensional [[Simplicial complex|simplicial complexes]], the [[simply connected]] infinite tree is the [[universal cover]] of the Cayley graph; and the [[Kernel (algebra)#group homomorphism|kernel]] of the mapping is the [[fundamental group]] of the Cayley graph.
[[Image:HeisenbergCayleyGraph.png|thumb|240px|right|Part of a Cayley graph of the Heisenberg group. (The coloring is only for visual aid.)]]
* A Cayley graph of the [[discrete Heisenberg group]]  <math display="block">\left\{ \begin{pmatrix}
 1 & x & z\\
 0 & 1 & y\\
 0 & 0 & 1\\
\end{pmatrix},\ x,y,z \in \Z\right\} </math> is depicted to the right. The generators used in the picture are the three matrices <math>X, Y, Z</math> given by the three permutations of 1, 0, 0 for the entries <math>x, y, z</math>. They satisfy the relations <math>Z = XYX^{-1}Y^{-1}, XZ = ZX, YZ = ZY</math>, which can also be understood from the picture. This is a [[nonabelian group|non-commutative]] infinite group, and despite being embedded in a three-dimensional space, the Cayley graph has four-dimensional [[Growth rate (group theory)|volume growth]].<ref>{{cite conference
 | last = Bartholdi | first = Laurent
 | editor1-last = Ceccherini-Silberstein | editor1-first = Tullio
 | editor2-last = Salvatori | editor2-first = Maura
 | editor3-last = Sava-Huss | editor3-first = Ecaterina
 | arxiv = 1512.07044
 | contribution = Growth of groups and wreath products
 | isbn = 978-1-316-60440-3
 | mr = 3644003
 | pages = 1–76
 | publisher = Cambridge Univ. Press, Cambridge
 | series = London Math. Soc. Lecture Note Ser.
 | title = Groups, graphs and random walks: Selected papers from the workshop held in Cortona, June 2–6, 2014
 | volume = 436
 | year = 2017}}</ref>
[[File:Cayley_Q8_multiplication_graph.svg|thumb|link={{filepath:Cayley_Q8_multiplication_graph.svg}}|Cayley Q8 graph showing cycles of multiplication by [[quaternion]]s {{red|'''i'''}}, {{green|'''j'''}} and {{blue|'''k'''}}]]

== Characterization ==
The group <math>G</math> [[Group action (mathematics)|acts]] on itself by left multiplication (see [[Cayley's theorem]]). This may be viewed as the action of <math>G</math> on its Cayley graph. Explicitly, an element <math>h\in G</math> maps a vertex <math>g\in V(\Gamma)</math> to the vertex <math>hg\in V(\Gamma).</math> The set of edges of the Cayley graph and their color is preserved by this action: the edge <math>(g,gs)</math> is mapped to the edge <math>(hg,hgs)</math>, both having color <math>c_s</math>. In fact, all [[Graph automorphism|automorphisms]] of the colored directed graph <math>\Gamma</math> are of this form, so that <math>G</math> is isomorphic to the [[symmetry group]] of <math>\Gamma</math>.{{NoteTag|Proof: Let <math>\sigma : V(\Gamma) \to V(\Gamma)</math> be an arbitrary automorphism of the colored directed graph <math>\Gamma</math>, and let <math>h = \sigma(e)</math> be the image of the identity. We show that <math>\sigma(g) = hg</math> for all <math>g\in V(\Gamma)</math>, by induction on the edge-distance of <math>g</math> from <math>e</math>. Assume <math>\sigma(g) = hg</math>. The automorphism <math>\sigma</math> takes any <math>c_s</math>-colored edge <math>g\to gs</math> to another  <math>c_s</math>-colored edge <math>\sigma(g)\to\sigma(gs)</math>. Hence <math>\sigma(gs) = \sigma(g)s = hgs</math>, and the induction proceeds. Since <math>\Gamma</math> is connected, this shows <math>\sigma(g) = hg</math> for all <math>g\in V(\Gamma)</math>.}}{{NoteTag|It is easy to modify <math>\Gamma</math> into a simple graph (uncolored, undirected) whose symmetry group is isomorphic to <math>G</math>: replace colored directed edges of <math>\Gamma</math> with appropriate trees corresponding to the colors.|name=note 2}} 

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

{{math theorem | name = Sabidussi's Theorem | math_statement = An (unlabeled and uncolored) directed graph <math>\Gamma</math> is a Cayley graph of a group <math>G</math> if and only if it admits a simply transitive action of <math>G</math> by [[graph automorphism]]s (i.e., preserving the set of directed edges).<ref>{{cite journal|first= Gert |last=Sabidussi|author-link=Gert Sabidussi | journal=[[Proceedings of the American Mathematical Society]] |date=October 1958 |volume=9 |number=5 | pages=800–4 | title=On a class of fixed-point-free graphs |jstor=2033090 |doi=10.1090/s0002-9939-1958-0097068-7|doi-access=free }}</ref>}}

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

== Elementary properties ==

* The Cayley graph <math>\Gamma(G,S)</math> depends in an essential way on the choice of the set <math>S</math> of generators. For example, if the generating set <math>S</math> has <math>k</math> elements then each vertex of the Cayley graph has <math>k</math> incoming and <math>k</math> outgoing directed edges. In the case of a symmetric generating set <math>S</math> with <math>r</math> elements, the Cayley graph is a [[regular graph|regular directed graph]] of degree <math>r.</math>
* [[Cycle (graph theory)|Cycles]] (or ''closed walks'') in the Cayley graph indicate [[Presentation of a group|relations]] among the elements of <math>S.</math> In the more elaborate construction of the [[Cayley complex]] of a group, closed paths corresponding to relations are "filled in" by [[polygon]]s. This means that the problem of constructing the Cayley graph of a given presentation <math>\mathcal{P}</math> is equivalent to solving the [[Word problem for groups|Word Problem]] for <math>\mathcal{P}</math>.<ref name = CGT/>
* If <math>f: G'\to G</math> is a [[surjective]] [[group homomorphism]] and the images of the elements of the generating set <math>S'</math> for <math>G'</math> are distinct, then it induces a covering of graphs <math display="block"> \bar{f}: \Gamma(G',S')\to \Gamma(G,S),</math> where <math>S = f(S').</math> In particular, if a group <math>G</math> has <math>k</math> generators, all of order different from 2, and the set <math>S</math> consists of these generators together with their inverses, then the Cayley graph <math>\Gamma(G,S)</math> is covered by the infinite regular [[tree (graph theory)|tree]] of degree <math>2k</math> corresponding to the [[free group]] on the same set of generators.
* For any finite Cayley graph, considered as undirected, the [[Connectivity (graph theory)|vertex connectivity]] is at least equal to 2/3 of the [[Degree (graph theory)|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 [[Connectivity (graph theory)|edge connectivity]] is in all cases equal to the degree.<ref>See Theorem 3.7 of {{cite book | chapter=27. Automorphism groups, isomorphism, reconstruction|title=Handbook of Combinatorics|pages=1447–1540|editor1-first=Ronald L.|editor1-last=Graham|editor1-link= Ronald Graham|editor2-first=Martin|editor2-last=Grötschel|editor2-link= Martin Grötschel |editor3-first=László|editor3-last=Lovász|editor3-link=László Lovász|first=László|last=Babai|author-link=László Babai| publisher=Elsevier|volume=1 |isbn=9780444823465 |url=https://books.google.com/books?id=5Y9NCwlx63IC |year=1995|chapter-url=http://people.cs.uchicago.edu/~laci/handbook/handbookchapter27.pdf}}</ref>
* If <math>\rho_{\text{reg}}(g)(x) = gx</math> is the left-regular representation with <math>|G|\times |G|</math> matrix form denoted <math>[\rho_{\text{reg}}(g)]</math>, the adjacency matrix of <math>\Gamma(G,S)</math> is <math display="inline">A = \sum_{s\in S} [\rho_{\text{reg}}(s)]</math>.
* Every group [[Multiplicative character|character]] <math>\chi</math> of the group <math>G</math> induces an [[eigenvector]] of the [[adjacency matrix]] of <math>\Gamma(G,S)</math>. The associated [[eigenvalue]] is  <math display="block">\lambda_\chi=\sum_{s\in S}\chi(s),</math> which, when <math>G</math> is Abelian, takes the form <math display="block">\sum_{s\in S} e^{2\pi ijs/|G|}</math> for integers <math>j = 0,1,\dots,|G|-1.</math> In particular, the associated eigenvalue of the trivial character (the one sending every element to 1) is the degree of <math>\Gamma(G,S)</math>, that is, the order of <math>S</math>. If <math>G</math> is an Abelian group, there are exactly <math>|G|</math> characters, determining all eigenvalues. The corresponding orthonormal basis of eigenvectors is given by <math>v_j = \tfrac{1}{\sqrt{|G|}}\begin{pmatrix} 1 & e^{2\pi ij/|G|} & e^{2\cdot 2\pi ij/|G|} & e^{3\cdot 2\pi ij/|G|} & \cdots & e^{(|G|-1)2\pi ij/|G|}\end{pmatrix}.</math> It is interesting to note that this eigenbasis is independent of the generating set <math>S</math>. {{pb}} More generally for symmetric generating sets, take <math>\rho_1,\dots,\rho_k</math> a complete set of irreducible representations of <math>G,</math> and let <math display="inline">\rho_i(S) = \sum_{s\in S} \rho_i(s)</math> with eigenvalue set <math>\Lambda_i(S)</math>. Then the set of eigenvalues of <math>\Gamma(G,S)</math> is exactly <math display="inline">\bigcup_i \Lambda_i(S),</math> where eigenvalue <math>\lambda</math> appears with multiplicity <math>\dim(\rho_i)</math> for each occurrence of <math>\lambda</math> as an eigenvalue of <math>\rho_i(S).</math>

== Schreier coset graph ==
{{main article|Schreier coset graph}}

If one instead takes the vertices to be right cosets of a fixed subgroup <math>H,</math> 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 <math>\Gamma(G,S)</math> are directly tied together: take <math>\rho_1,\dots,\rho_k</math> a complete set of irreducible representations of <math>G,</math> and let <math display="inline">\rho_i(S) = \sum_{s \in S} \rho_i(s)</math> with eigenvalues <math>\Lambda_i(S)</math>. Then the set of eigenvalues of <math>\Gamma(G,S)</math> is exactly <math display="inline">\bigcup_i \Lambda_i(S),</math> where eigenvalue <math>\lambda</math> appears with multiplicity <math>\dim(\rho_i)</math> for each occurrence of <math>\lambda</math> as an eigenvalue of <math>\rho_i(S).</math>

The [[Genus (mathematics)|genus]] of a group is the minimum genus for any Cayley graph of that group.<ref>{{cite journal | last=White |first=Arthur T. |title=On the genus of a group |journal=[[Transactions of the American Mathematical Society]] |volume=173 |year=1972 |pages=203–214 |mr=0317980 |doi=10.1090/S0002-9947-1972-0317980-2|doi-access=free }}</ref>

=== Geometric group theory ===
For infinite groups, the [[Coarse structure|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 <math>S = S^{-1}</math>, the Cayley graph <math>\Gamma(G,S)</math> is <math>|S|</math>-regular, so spectral techniques may be used to analyze the [[expander graph|expansion properties]] of the graph. In particular for abelian groups, the eigenvalues of the Cayley graph are more easily computable and given by <math display="inline">\lambda_\chi = \sum_{s\in S} \chi(s)</math> with top eigenvalue equal to <math>|S|</math>, so we may use [[Spectral graph theory#Cheeger inequality|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:<ref>Proposition 1.12 in {{cite journal|last=Lubotzky|first=Alexander | authorlink=Alexander Lubotzky |title=Expander graphs in pure and applied mathematics | journal=[[Bulletin of the American Mathematical Society]] |year=2012 |volume=49 |pages=113–162  |arxiv=1105.2389| doi=10.1090/S0273-0979-2011-01359-3 |doi-access=free}}</ref> 

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

For example the group <math>G = \mathrm{SL}_3(\Z)</math> 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 <math>\Gamma(G,S)</math> is integral iff the eigenvalues of <math>\rho(S)</math> are integral for every representation <math>\rho</math> of <math>G</math>.

=== Cayley integral simple group ===

A group <math>G</math> is Cayley integral simple (CIS) if the connected Cayley graph <math>\Gamma(G,S)</math> is integral exactly when the symmetric generating set <math>S</math> is the complement of a subgroup of <math>G</math>. A result of Ahmady, Bell, and Mohar shows that all CIS groups are isomorphic to <math>\mathbb{Z}/p\mathbb{Z}, \mathbb{Z}/p^2\mathbb{Z}</math>, or <math>\mathbb{Z}_2 \times \mathbb{Z}_2</math> for primes <math>p</math>.<ref name="CIS">{{cite journal|last1=Ahmady|first1=Azhvan |last2=Bell|first2=Jason|last3=Mohar|first3=Bojan|authorlink3=Bojan Mohar|title=Integral Cayley graphs and groups|journal=[[SIAM Journal on Discrete Mathematics]]|volume=28|issue=2|pages=685–701|year=2014|arxiv=1307.6155 |doi=10.1137/130925487 |s2cid=207067134}}</ref> It is important that <math>S</math> actually generates the entire group <math>G</math> in order for the Cayley graph to be connected. (If <math>S</math> does not generate <math>G</math>, the Cayley graph may still be integral, but the complement of <math>S</math> is not necessarily a subgroup.)

In the example of <math>G=\mathbb{Z}/5\mathbb{Z}</math>, the symmetric generating sets (up to graph isomorphism) are
*<math>S = \{1,4\}</math>: <math>\Gamma(G,S)</math> is a <math>5</math>-cycle with eigenvalues <math>2, \tfrac{\sqrt{5}-1}{2},\tfrac{\sqrt{5}-1}{2},\tfrac{-\sqrt{5}-1}{2},\tfrac{-\sqrt{5}-1}{2}</math>
*<math>S = \{1,2,3,4\}</math>: <math>\Gamma(G,S)</math> is <math>K_5</math> with eigenvalues <math>4, -1,-1,-1,-1</math>
The only subgroups of <math>\mathbb{Z}/5\mathbb{Z}</math> are the whole group and the trivial group, and the only symmetric generating set <math>S</math> that produces an integral graph is the complement of the trivial group. Therefore <math>\mathbb{Z}/5\mathbb{Z}</math> 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.<ref name="CIS" />

=== Cayley integral group ===

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

The complete list of Cayley integral groups is given by <math>\mathbb{Z}_2^n\times \mathbb{Z}_3^m,\mathbb{Z}_2^n\times \mathbb{Z}_4^n, Q_8\times \mathbb{Z}_2^n,S_3</math>, and the dicyclic group of order <math>12</math>, where <math>m,n\in \mathbb{Z}_{\ge 0}</math> and <math>Q_8</math> is the quaternion group.<ref name="CIS"/> 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 <math>G</math>, a subset <math>S \subseteq G</math> is normal if <math>S</math> is closed under [[conjugation (group theory)|conjugation]] by elements of <math>G</math> (generalizing the notion of a normal subgroup), and <math>S</math> is Eulerian if for every <math>s \in S</math>, the set of elements generating the cyclic group <math>\langle s \rangle</math> is also contained in <math>S</math>.
A 2019 result by Guo, Lytkina, Mazurov, and Revin proves that the Cayley graph <math>\Gamma(G,S)</math> is integral for any Eulerian normal subset <math>S \subseteq G</math>, using purely representation theoretic techniques.<ref>{{cite journal| last1=Guo|first1=W.|last2=Lytkina|first2=D.V.|last3=Mazurov|first3=V.D.|last4=Revin|first4=D.O.|title=Integral Cayley graphs|journal=Algebra and Logic | year=2019|volume=58 |issue=4 |pages=297–305 |doi=10.1007/s10469-019-09550-2|arxiv=1808.01391 |s2cid=209936465 |url=https://link.springer.com/content/pdf/10.1007/s10469-019-09550-2.pdf}}</ref>

The proof of this result is relatively short: given <math>S</math> an Eulerian normal subset, select <math>x_1,\dots, x_t\in G</math> pairwise nonconjugate so that <math>S</math> is the union of the [[conjugacy classes]] <math>\operatorname{Cl}(x_i)</math>. Then using the characterization of the spectrum of a Cayley graph, one can show the eigenvalues of <math>\Gamma(G,S)</math> are given by <math display="inline">\left\{\lambda_\chi = \sum_{i=1}^t \frac{\chi(x_i) \left|\operatorname{Cl}(x_i)\right|}{\chi(1)}\right\}</math> taken over irreducible characters <math>\chi</math> of <math>G</math>. Each eigenvalue <math>\lambda_\chi</math> in this set must be an element of <math>\mathbb{Q}(\zeta)</math> for <math>\zeta</math> a primitive <math>m^{th}</math> root of unity (where <math>m</math> must be divisible by the orders of each <math>x_i</math>). Because the eigenvalues are algebraic integers, to show they are integral it suffices to show that they are rational, and it suffices to show <math>\lambda_\chi</math> is fixed under any automorphism <math>\sigma</math> of <math>\mathbb{Q}(\zeta)</math>. There must be some <math>k</math> relatively prime to <math>m</math> such that <math>\sigma(\chi(x_i)) = \chi(x_i^k)</math> for all <math>i</math>, and because <math>S</math> is both Eulerian and normal, <math>\sigma(\chi(x_i)) = \chi(x_j)</math> for some <math>j</math>. Sending <math>x\mapsto x^k</math> bijects conjugacy classes, so <math>\operatorname{Cl}(x_i)</math> and <math>\operatorname{Cl}(x_j)</math> have the same size and <math>\sigma</math> merely permutes terms in the sum for <math>\lambda_\chi</math>. Therefore <math>\lambda_\chi</math> is fixed for all automorphisms of <math>\mathbb{Q}(\zeta)</math>, so <math>\lambda_\chi</math> is rational and thus integral.

Consequently, if <math>G=A_n</math> is the alternating group and <math>S</math> is a set of permutations given by <math>\{ (12i)^{\pm 1} \}</math>, then the Cayley graph <math>\Gamma(A_n,S)</math> is integral. (This solved a previously open problem from the [[Kourovka Notebook]].) In addition when <math>G = S_n</math> is the symmetric group and <math>S</math> is either the set of all transpositions or the set of transpositions involving a particular element, the Cayley graph <math>\Gamma(G,S)</math> is also integral.

== History ==
Cayley graphs were first considered for finite groups by [[Arthur Cayley]] in 1878.<ref name=Cayley78/> [[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 (mathematics)|word problem]] for the [[fundamental group]] of [[Surface (topology)|surface]]s with genus ≥ 2, which is equivalent to the topological problem of deciding which closed curves on the surface contract to a point.<ref>{{cite book |last=Dehn |first=Max |author-link=Max Dehn| title=Papers on Group Theory and Topology |publisher=Springer-Verlag |year=2012 |orig-year=1987 |isbn=978-1461291077 }} Translated from the German and with introductions and an appendix by [[John Stillwell]], and with an appendix by [[Otto Schreier]].</ref>

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

{{reflist|group=note}}

== Notes ==
{{reflist}}

== External links ==
* [http://www.weddslist.com/groups/cayley-plat/index.html Cayley diagrams]
* {{mathworld | urlname = CayleyGraph  | title = Cayley graph }}

{{DEFAULTSORT:Cayley Graph}}
[[Category:Group theory]]
[[Category:Permutation groups]]
[[Category:Graph families]]
[[Category:Application-specific graphs]]
[[Category:Geometric group theory]]
[[Category:Cayley graphs| ]]