Editing Cayley graph (section)

=== 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.