# On the second largest eigenvalue of some
Cayley graphs of the Symmetric Group

Johannes Siemons  School of Mathematics, University of East Anglia, University
Plain, Norwich, NR47TJ, E-mail<EMAIL_ADDRESS>(Johannes Siemons)  and
Alexandre Zalesski  Department of Physics, Mathematics and Informatics,
National Academy of Sciences of Belarus, 66 Prospekt Nezavisimosti, Minsk,
Belarus, E-mail<EMAIL_ADDRESS>(Alexandre Zalesski)

###### Key words and phrases:

Symmetric group, Cayley graph, Adjacency matrix, Eigenvalues

###### 2000 Mathematics Subject Classification:

20G05, 20G40

Dedicated to the memory of Gordon James

Abstract: Let $S_{n}$ and $A_{n}$ denote the symmetric and alternating group
on the set $\\{1,\ldots,n\\},$ respectively. In this paper we are interested
in the second largest eigenvalue $\lambda_{2}(\Gamma)$ of the Cayley graph
$\Gamma={\rm Cay}(G,H)$ over $G=S_{n}$ or $A_{n}$ for certain connecting sets
$H.$

Let $1<k\leq n$ and denote the set of all $k$-cycles in $S_{n}$ by $C(n,k).$
For $H=C(n,n)$ we prove that $\lambda_{2}(\Gamma)=(n-2)!$ (when $n$ is even)
and $\lambda_{2}(\Gamma)=2(n-3)!$ (when $n$ is odd). Further, for $H=C(n,n-1)$
we have $\lambda_{2}(\Gamma)=3(n-3)(n-5)!$ (when $n$ is even) and
$\lambda_{2}(\Gamma)=2(n-2)(n-5)!$ (when $n$ is odd). The case $H=C(n,3)$ has
been considered in [6].

Let $1\leq r<k<n$ and let $C(n,k;r)\subseteq C(n,k)$ be set of all $k$-cycles
in $S_{n}$ which move all the points in the set $\\{1,2,\ldots,r\\}.$ That is
to say, $g=(i_{1},i_{2},\ldots,i_{k})(i_{k+1})\dots(i_{n})\in C(n,k;r)$ if and
only if $\\{1,2,\ldots,r\\}\subset\\{i_{1},i_{2},\ldots,i_{k}\\}.$

Our main result concerns $\lambda_{2}(\Gamma)$, where $\Gamma={\rm Cay}(G,H)$
with $H=C(n,r+1,r)$ for $2\leq r\leq n-2.$ Suppose that $G=S_{n}$ if $r$ is
odd and $G=A_{n}$ if $r$ is even. We prove that
$\lambda_{2}(\Gamma)=r!(n-r-1)$. The cases with $H=C(n,3;1)$ and $H=C(n,3;2)$
have been considered in [6].

##  1\. Introduction

Let $\Gamma$ be a finite undirected graph and let $A$ denote its adjacency
matrix. The eigenvalues of this matrix, together with their multiplicities,
are an important invariant of the graph. Since $A$ is symmetric all
eigenvalues are real. For a regular graph of degree $d$ it is well-known that
the largest eigenvalue of $A$ is $\lambda_{1}(\Gamma)=d.$ The second largest
eigenvalue, denoted by $\lambda_{2}(\Gamma),$ plays an important role in many
theoretical and practical applications of graph theory, from geometry to
computer science. The literature on the second largest eigenvalue is
extensive, overviews and further references can be found in [1, 3, 5, 11, 12,
13]. For regular graphs the spectral gap
$\lambda_{1}(\Gamma)-\lambda_{2}(\Gamma)$ is known as the algebraic
connectivity of $\Gamma.$

In this paper we are concerned with the second largest eigenvalue of certain
Cayley graphs ${\rm Cay}(G,H)$ where $G$ is a symmetric or alternating group
and where $H$ a connecting set in $G.$ (In particular, we have
$H=H^{-1}=\\{h^{-1}\,|\,h\in H\\},$ the identity element of $G$ does not
belong to $H,$ and $H$ is not contained in any proper subgroup of $G.)$ For
the definition of Cayley graphs see Section 2.4. References to recent work on
the second largest eigenvalue of Cayley graphs over symmetric groups can be
found in [6]. Even for symmetric groups an explicit computation of it appears
to be one of the most challenging problem in the area.

To state our results let $S_{n}={\rm Sym}(1,\ldots,n)$ and $A_{n}$ be the
symmetric and alternating group on the set $\\{1,\ldots,n\\},$ respectively.
For $1<k\leq n$ a $k$-cycle in $S_{n}$ is a permutation of the shape
$g=(i_{1},i_{2},\ldots,i_{k})(i_{k+1})\dots(i_{n})$ with
$|\\{i_{1},i_{2},\ldots,i_{k}\\}|=k.$ The set of all $k$-cycles in $S_{n}$ is
denoted by $C(n,k).$

######  Theorem 1.1.

Let $\Gamma={\rm Cay}(G,H)$ with $H=C(n,n)$ for $n>4$ and $G=S_{n}$ when $n$
is even and $G=A_{n}$ when $n$ is odd. Then $\lambda_{1}(\Gamma)=(n-1)!$.
Furthermore, $\lambda_{2}(\Gamma)=(n-2)!$ when $n$ is even and
$\lambda_{2}(\Gamma)=2(n-3)!$ when $n$ is odd.

######  Theorem 1.2.

Let $\Gamma={\rm Cay}(G,H)$ with $H=C(n,n-1)$ for $n>4$ and $G=S_{n}$ when $n$
is odd and $G=A_{n}$ when $n$ is even. Then $\lambda_{1}(\Gamma)=n(n-2)!$.
Furthermore, $\lambda_{2}(\Gamma)=3(n-3)(n-5)!$ when $n$ is even and
$\lambda_{2}(\Gamma)=2(n-2)(n-4)!$ when $n$ is odd.

An essential feature of the Cayley graphs in these two theorems is that the
connecting set $H$ is invariant under conjugation by $G.$ In fact, $C(n,k)$ is
a conjugacy class of $S_{n}$. If $k=n$ or $n-1$, the above results are deduced
from some analysis of the group characters in a relatively straightforward
way. For arbitrary $k$ computing the second largest eigenvalue for ${\rm
Cay}(G,C(n,k))$ is an open problem. For $k=3$ this is solved in [6, Theorem
3.4], for $k=2$ see [9, Lemma 3].

Next let $1\leq r<k<n$ and let $C(n,k;r)\subseteq C(n,k)$ be set of all
$k$-cycles in ${\rm Sym}(1,\ldots,n)$ which move all the points in the set
$\\{1,2,\ldots,r\\}.$ That is to say,
$g=(i_{1},i_{2},\ldots,i_{k})(i_{k+1})\dots(i_{n})\in C(n,k;r)$ if and only if
$\\{1,2,\ldots,r\\}\subset\\{i_{1},i_{2},\ldots,i_{k}\\}.$ Clearly,
$|C(n,k;r)|=(k-1)!{n-r\choose k-r}.$

Our main result is

######  Theorem 1.3.

Let $n>4$ be an integer and $2\leq r\leq n-2$. Let $\Gamma={\rm Cay}(G,H)$
with $H=C(n,r+1;r)$ where $G=S_{n}$ when $r$ is odd and $G=A_{n}$ when $r$ is
even. Then $\lambda_{1}(\Gamma)=r!(n-r)$ and $\lambda_{2}(\Gamma)=r!(n-r-1)$.

In this theorem, by contrast, the connecting set $H$ is not invariant under
$S_{n}.$ However, we make essential use of the fact that $H$ is invariant
under a subgroup isomorphic to $F=S_{r}\times S_{n-r}$. For Cayley graph
$\Gamma={\rm Cay}(G,H)$ with $H=C(n,3;1)$ and $H=C(n,3;2)$ the value of
$\lambda_{2}(\Gamma)$ has been determined in [6, Theorems 3.2 and 2.3]. This
values is also known for $H=C(n,2;1)$ see [11, Section 8.1].

Notation: All groups considered here are finite. Further, all modules and
representations are over the field $\mathop{\mathbb{C}}\nolimits$ of complex
numbers. By $\mathbb{C}G$ we denote the group algebra of the group $G$ over
$\mathop{\mathbb{C}}\nolimits$. If $H\subset G$ then $|H|$ is the number of
elements of $H$ and $H^{+}$ is the sum of all $h\in H,$ as an element of
$\mathbb{C}G$. A sentence such as ‘$L$ is a $G$-module’ means that $L$ is a
$\mathbb{C}G$-module. If $L$ is a $\mathbb{C}G$-module and $X$ is a subgroup
of $G$, we write $L|_{X}$ for the restriction of $L$ to $X$. The trivial
$G$-module and its character is denoted by $1_{G}$. We assume that the reader
is familiar with general notions and elementary facts of finite group theory,
including the representation theory of $S_{n}$ and $A_{n}$.

##  2\. Preliminaries

We collect several well-known facts and prerequisites for the paper. All
graphs are finite, undirected and without multiple edges.

###  2.1. Graphs and Eigenvalues

Let $\Gamma$ be a graph on the vertex set $V;$ we put $m=|V|.$ For $u,v\in V$
we write $u\sim v$ if $u$ is adjacent to $v.$ For $v\in V$ the set
$N(v)=\\{u\in V\,:\,u\sim v\\}$ denotes the set of neighbours of $v$ and
$d(v)=|N(v)|$ is the degree of $v.$ The graph is regular of degree $d$ if
$d(v)=d$ for all $v\in V.$ A permutation $\gamma$ of $V,$ $u\mapsto
u^{\gamma},$ is an automorphism of $\Gamma$ if $(N(v))^{\gamma}=N(v^{\gamma})$
for all $v\in V.$ The group of all automorphisms of $\Gamma$ is denoted by
${\rm Aut}(\Gamma).$

The adjacency matrix $A=(a_{u,v})$ of $\Gamma$ is given by $a_{u,v}=1$ if
$u\sim v$ and $a_{u,v}=0$ otherwise. Then $A$ determines $\Gamma$. The
eigenvalues of $\Gamma$ are, by definition, the eigenvalues of $A$. These are
real since $A$ is symmetric.

######  Theorem 2.1.

[10, Proposition 1.48] Let $\Gamma$ be a regular graph of degree $d$ and let
$A$ be its adjacency matrix. Then
$(1)$ $d$ is an eigenvalue of $A.$ Furthermore, $d$ has multiplicity $1$ if
and only if $\Gamma$ is connected;
$(2)$ $\Gamma$ is bipartite if and only if $-d$ is an eigenvalue of $A;$
$(3)$ $d\geq|\lambda|$ for all eigenvalues $\lambda$ of $A.$ If $\Gamma$ is
bipartite and if $\lambda$ is an eigenvalue of $A$ then $-\lambda$ is an
eigenvalue of $A$ with the same multiplicity as $\lambda.$

###  2.2. Equitable partitions

Let $\Gamma$ be a graph with vertex set $V.$ Let $P$ be a partition
$V=V_{1}\cup\cdots\cup V_{k}$ of $V$. Then $P$ is called equitable if
$|N(v_{i})\cap V_{j}|$ does not depend on the choice of $v_{i}\in V_{i}$ for
all $1\leq i,\,j\leq k.$ If $P$ is equitable then the matrix
$B=B(P)=(|V_{i}\cap N(v_{j})|)$ with $1\leq i,j\leq k$ is called the
associated matrix of $P.$ As usual, a second partition $P^{\prime}$ is a
refinement of $P$ if every class of $P$ is some union of classes of
$P^{\prime}.$

For any graph $\Gamma$ examples of equitable partitions arise from the orbits
of a group of automorphisms of $\Gamma,$ see Lemma 2.3 below. For this reason
equitable partitions are also called generalized orbits. For incidence graphs
of geometries also the term tactical decomposition is used, see Dembowski’s
book [4].

Let $\mathbb{C}V$ be the vector space with basis $V$ over $\mathbb{C}.$ Then
$A$ can be viewed as a linear transformation of $\mathbb{C}V$, and then
$Av=\sum_{x\in N(v)}x$ for every $v\in V$. Let $(\cdot,\cdot)$ be the standard
bilinear form on $\mathbb{C}V$ defined by $(u,v)=\delta_{u,v}$ (the Kronecker
delta) for $u,v\in V$. Let $V=V_{1}\cup\dots\cup V_{k}$ be a partition $P$ of
$V$. Set $w_{i}=\sum_{u\in V_{i}}u$ for $i=1,\ldots,k$. Then
$(w_{i},Av)=|N(v)\cap V_{i}|$ (as $(w_{i},u)=1$ for $u\in V$ if and only if
$u\in V_{i}$). Let $\mathbb{C}P$ be the vector space with basis
$w_{1},\ldots,w_{k}$. In this notation we have:

######  Lemma 2.2.

Let $\Gamma$ be a graph with vertex set V and adjacency matrix $A$, and let
$P$ be a partition $V=V_{1}\cup\dots\cup V_{k}$ of $V.$ Then $P$ is equitable
if and only if $\mathbb{C}P$ is $A$-invariant (that is, $Ax\in\mathbb{C}P$ for
all ${\rm x}\in\mathbb{C}P).$ Furthermore, if $P$ is equitable then $B(P)$ is
the matrix of the restriction of $A$ to $\mathbb{C}P$ for the basis
$w_{1},\dots,w_{k}.$ In particular, all eigenvalues of $B$ are eigenvalues of
$\Gamma.$ If $\Gamma$ is regular of degree $d$ then $d$ is an eigenvalue of
$B.$

In addition, if $P^{\prime}$ is an equitable refinement of $P$ then the
eigenvalues of $B(P)$ are eigenvalues of $B(P^{\prime})$.

Proof: For $i=1,\ldots,k$ we have

$Aw_{i}=\sum_{v\in V}(Aw_{i},v)v=\sum_{v\in V}(w_{i},Av)v=\sum_{v\in
V}(w_{i},\sum_{u\in N(v)}u)v=\sum_{v\in V}|N(v)\cap V_{i}|v.$ (1)

To be in $\mathbb{C}P$ the right hand side must be constant on every $V_{j}$,
that is, $|N(v)\cap V_{i}|=|N(v^{\prime})\cap V_{i}|$ for every
$j\in\\{1,\ldots,k\\}$ and every $v,v^{\prime}\in V_{j}$. The converse and the
second assertion of the lemma follows from (1) as well. Finally, if $\Gamma$
is regular of degree $d$ then $A(w_{1}+\cdots+w_{k})=A\sum_{v\in
V}v=d\sum_{v\in V}v=d(w_{1}+\cdots+w_{k})$, so $d$ is an eigenvalue of $A$ on
$\mathbb{C}P$.

Let $V=V^{\prime}_{1}\cup\dots\cup V^{\prime}_{\ell}$ be a refinement
$P^{\prime}$ of $P$ and let as above $w_{1}^{\prime},\ldots,w_{l}^{\prime}$ be
a basis of $\mathbb{C}P^{\prime}.$ Then every $w_{j}$ ($j=1,\ldots,k$) is a
linear combination of $w_{1}^{\prime},\ldots,w_{\ell}^{\prime}$, so
$\mathbb{C}P\subset\mathbb{C}P^{\prime}$, whence the additional statement.
$\Box$

######  Lemma 2.3.

Let $\Gamma$ be a graph and $G$ a group of automorphisms of $\Gamma.$ Let
$V_{1},\,...,\,V_{k}$ be the orbits of $G$ on the vertex set $V$ of $\Gamma.$
Then $V=V_{1}\cup\cdots\cup V_{k}$ is equitable.

###### Proof.

For $i,j$ with $1\leq i,j\leq k$ let $v,\,v^{\prime}\in V_{i}.$ Then there
exists $g\in G$ so that $g(v)=v^{\prime}$ and therefore $|N(v)\cap
V_{j}|=|g(N(v)\cap V_{j})|=|N(g(v))\cap g(V_{j}))|=|N(v^{\prime})\cap V_{j}|.$
∎

###  2.3. Eigenvalue Inequalities

We denote the distinct eigenvalues of a graph $\Gamma$ by

$\lambda_{1}>\lambda_{2}>\dots>\lambda_{m^{\prime}}$

for some $m^{\prime}\leq m.$ If $\Gamma$ is regular of degree $d$ then
$\lambda_{1}=d$ by Theorem 2.1. The second largest eigenvalue, $\lambda_{2},$
plays a distinguished role in graph theory as it provides bounds for the
isoperimetric constant of $\Gamma,$ see also graph expanders, the Kahzdan
constant and Cheeger inequality in [10]. From Theorem 2.1 and Lemma 2.2 we
immediately have

######  Lemma 2.4.

Let $P$ be an equitable partition of the regular graph $\Gamma$ and let
$\beta_{2}$ be the second largest eigenvalue of $B(P).$ Then
$\lambda_{2}\geq\beta_{2}.$

Upper and lower bounds on eigenvalues of a symmetric matrix over the reals can
be obtained from a theorem of Hermann Weyl [15], see also [3, Theorem 2.8.1].

######  Theorem 2.5 (Weyl Inequality).

Let $C=A+B$ be symmetric $(m\times m)$-matrices, and let
$\gamma_{1}\geq\cdots\geq\gamma_{m},$ $\alpha_{1}\geq\cdots\geq\alpha_{m},$
$\beta_{1}\geq\cdots\geq\beta_{m}$ be the eigenvalues of $C,B,A,$
respectively. Then for $1\leq i,j\leq m$ we have

$\gamma_{i+j-1}\leq\alpha_{i}+\beta_{j}\ {\rm whenever}\,\,i+j-1\leq m$ (2)

and

$\gamma_{i+j-m}\geq\alpha_{i}+\beta_{j}\ {\rm whenever}\,\,i+j-1\geq m.$ (3)

We note in particular, for $i,\,j\in\\{1,2\\}$ we have

$\gamma_{2}\leq\alpha_{2}+\beta_{1}\,\,\text{and}\,\,\,\gamma_{2}\leq\alpha_{1}+\beta_{2}.$
(4)

We refer to (4) as the Weyl inequality.

For adjacency matrices we have several applications. First let
$\gamma_{1}\geq\gamma_{2}\geq\gamma_{3}\geq\dots\geq\gamma_{m}$ be all
eigenvalues of $\Gamma,$ with repetitions. If $\Gamma$ is regular of degree
$d$ and connected then we have
$d=\gamma_{1}=\lambda_{1}>\lambda_{2}=\gamma_{2}$ by Theorem 2.1, for other
eigenvalues repetitions may appear.

Let $v$ be a vertex of $\Gamma$ and let $\Gamma^{\prime}$ be obtained from
$\Gamma$ by deleting all edges incident with $v.$ Denote the adjacency matrix
of $\Gamma^{\prime}$ by $A^{\prime}$ and let
$\gamma_{1}^{\prime}\geq\gamma_{2}^{\prime}\geq\dots\geq\gamma_{m}^{\prime}$
be all eigenvalues of $\Gamma^{\prime},$ with repetitions. Next let $\Sigma$
be the ‘star’ at $v$ with $d$ rays, where $d$ is the degree of $v,$ and with
$m-d-1$ isolated vertices. Denote its adjacency matrix by $S.$ The eigenvalues
of the star are
$\sigma_{1}=\sqrt{d}>\sigma_{2}=0=\dots=\sigma_{m-1}>\sigma_{m}=-\sqrt{d},$ by
a simple computation. Then $A=A^{\prime}+S$ and from Theorem 2.5 we obtain the
following

######  Corollary 2.6.

Let $v$ be a vertex of the connected graph $\Gamma$ and let $\Gamma^{\prime}$
be obtained by deleting all edges incident with $v.$ Let
$\lambda_{1}>\lambda_{2}$ and $\lambda_{1}^{\prime}>\lambda_{2}^{\prime}$ be
the largest and second largest eigenvalues of $\Gamma$ and $\Gamma^{\prime},$
respectively. Then

$\lambda_{1}\geq\lambda^{\prime}_{1}\geq\lambda_{2}\geq\lambda^{\prime}_{2}.$
(5)

Furthermore, if $d$ is the degree of $v$ then

$|\lambda_{i}-\lambda_{i}^{\prime}|\leq\sqrt{d}$ (6)

for $1\leq i\leq 2.$

Accounting for the isolated vertex $v,$ the spectrum of the graph
$\Gamma[V\setminus\\{v\\}]$ induced on $V\setminus\\{v\\}$ is obtained from
the spectrum of $\Gamma^{\prime}$ by removing one eigenvalue
$\lambda^{\prime}=0.$ The first part of the corollary is therefore an instance
of the well-known interlacing theorem, see [3, Theorem 2.5.1]. However, the
second part of the corollary appears to be new.

###  2.4. Cayley Graphs

Let $G$ be a group with identity element $1$ or $1_{G}$ and let $H$ be a
subset of $G.$ Then $H$ is a connecting set if (i) $1\not\in H,$ (ii)
$H=H^{-1}(=\\{h^{-1}\,|\,h\in H\\})$ and (iii) $H$ is not contained in any
proper subgroup of $G.$ For such a set $H$ the Cayley graph ${\rm Cay}(G,H)$
is the graph with vertex set $V=G$ so that two vertices $u,\,v\in G$ are
adjacent if and only if $uv^{-1}\in H.$ Thus $N(v)=Hv$ and so ${\rm Cay}(G,H)$
is regular of degree $|H|$. The adjacency matrix of ${\rm Cay}(G,H)$ is
denoted by $A=A(G,H).$

More generally, one can construct a similar graph $\Gamma(G,H)$ if (i),(ii)
holds and (iii) fails. Then $\Gamma(G,H)$ is still a regular graph of degree
$|H|$. Let $G_{1}$ be the least subgroup of $G$ containing $H$. Then $H$ is a
connecting set for $G_{1}$, and $\Gamma(G,H)$ is a disconnected graph
isomorphic to the union of $|G:G_{1}|$ copies of ${\rm Cay}(G_{1},H).$ In
particular, the eigenvalues of $\Gamma(G,H)$ and ${\rm Cay}(G_{1},H)$ are the
same (disregarding the multiplicities). In fact, $A(G,H)$ is similar to a
block diagonal matrix in which all blocks are $A(G_{1},H).$ So we have:

######  Lemma 2.7.

Let $H$ be a subset of the group $G$ such that $1\notin H$ and $H=H^{-1}$. Let
$G_{1}$ be the smallest subgroup of $G$ containing $H.$ Then $\Gamma(G,H)$ and
${\rm Cay}(G_{1},H)$ have the same distinct eigenvalues.

Thus, such a generalization is not essential. However, for the study of
eigenvalues of ${\rm Cay}(G_{1},H)$ by means of representation theory one
sometimes prefers to deal with the adjacency matrix of $\Gamma(G,H)$ if the
representation theory of $G$ is simpler than that of $G_{1}$. In Section 6 we
observe this for $G=S_{n}$ and $G_{1}=A_{n}$.

There is no harm in identifying $g\in G$ with its matrix in the regular
representation of $G,$ of size $|G|\times|G|.$ A key fact for adjacency
matrices of Cayley graphs then is that $\sum_{h\in H}\,h$, the sum over $h\in
H$ of the matrices just defined, is the adjacency matrix of ${\rm Cay}(G,H).$
Thus $A(G,H)=H^{+}$ under this identification. (Recall that we define $H^{+}$
as an element of the group algebra of $G$ over
$\mathop{\mathbb{C}}\nolimits$.) This is well known and explained, for
instance, in [14, p. 384]. In other words, $A$ is the image of $H^{+}$ in the
regular representation of the group algebra. Note that $A$ is a linear
transformation of the vector space $\mathbb{C}V=\mathbb{C}G$, the
$\mathop{\mathbb{C}}\nolimits$-span of $G$.

######  Lemma 2.8.

Let $H$ be a connecting set in the group $G$ and let $F$ be the the normalizer
of $H$ in $G.$ Then $F\times G$ acts as a group of automorphisms on
$\Gamma={\rm Cay}(G,H)$ by $(f,g)\\!:\,v\mapsto f^{-1}vg$ for all $(f,g)\in
F\times G$ and $v\in G.$ In particular, ${\rm Aut}(\Gamma)$ is vertex
transitive.

###### Proof.

Let $u,v\in G.$ Then $uv^{-1}\in H$ if and only if
$(f^{-1}ug)(g^{-1}v^{-1}f)\in f^{-1}Hf=H.$ Evidently $\\{1_{F}\\}\times G$ is
transitive on $G.$ ∎

##  3\. Some general results

In this section we discuss representation theoretical aspects of eigenvalue
problems for Cayley graphs. Let $G$ be a finite group, $H\subset G$ a
connecting subset, and put $H^{+}=\sum_{h\in H}$ as an element in the group
algebra $\mathbb{C}G$ of $G$ over $\mathbb{C}.$ If $\rho$ is the regular
representation of $G$ then $A(G,H)=\rho(H^{+}).$ If we identify $g$ with
$\rho(g)$ then $A(G,H)=H^{+}$ as discussed in Section 2.4. Thus, if $\phi$ is
any representation of $G$ then $\phi(H^{+})$ is meaningful, and the
eigenvalues of $\phi(H^{+})$ are eigenvalues of $\Gamma$. We think that this
convention makes the exposition more transparent.

By standard results, $\rho$ is a direct sum of all irreducible representations
$\phi$ of $G,$ each occurring with multiplicity $\dim\phi$. It follows that
the set of all eigenvalues of $Cay(G,H)$ (disregarding the multiplicities) is
the union, over the irreducible representations $\phi$ of $G,$ of the
eigenvalues of $\phi(H^{+})$. See [10, Proposition 7.1] or elsewhere.

If $\phi_{0}$ is the trivial representation of $G$ then, obviously,
$\phi_{0}(H^{+})=|H|$. Conversely, if $|H|$ is an eigenvalue of $\phi(H^{+}),$
where $\phi$ is an irreducible representation of $G$, then $\phi=\phi_{0}$ by
Theorem 2.1 (as $\phi_{0}$ occurs in $\rho$ with multiplicity 1; here we use
that $H$ is a connecting set).

######  Lemma 3.1.

Let $G_{1}$ be a subgroup of $G$ and let M be an irreducible G-submodule with
character $\chi$. Let $H$ be a subset of $G.$
$(1)$ If H is G-stable (that is, $gHg^{-1}=H$ for every $g\in G$) then the
restriction $H^{+}$ to M acts as a scalar matrix $\mu\cdot\mathop{\rm
Id}\nolimits$. If $H=h^{G}$ is a conjugacy class then
$\mu=|H|\cdot\frac{\chi(h)}{\chi(1)}=|G:C_{G}(h)|\cdot\frac{\chi(h)}{\chi(1)}$.
$(2)$ Let $L$ be an irreducible $G_{1}$-module occurring in $M|_{G_{1}}$
exactly once.
$(i)$ Suppose that H is $G_{1}$-stable. Then $H^{+}$ acts scalarly on L.
$(ii)$ Suppose that $H=H_{1}\cup H_{2}$, where $H_{1},H_{2}$ are
$G_{1}$-stable. Then $H^{+},H^{+}_{1}$ and $H_{2}^{+}$ act scalarly on L, and
$\nu=\nu_{1}+\nu_{2}$, where $\nu,\nu_{1},\nu_{2}$ are the eigenvalues of
$H^{+},H^{+}_{1}$ and $H_{2}^{+}$ on L. This remains true if
$H=H_{1}\cup\cdots\cup H_{k}$, where $H_{1},\ldots,H_{k}$ are $G_{1}$-normal.
(That is, $H^{+}_{i}$ acts scalarly on L, and $\nu=\nu_{1}+...+\nu_{k}$, where
$\nu_{i}$ is the eigenvalue of $H^{+}_{i}$ on L.
$(iii)$ Suppose that $H_{1}=H\cap G_{1}$ and that $H_{1}$ is a connecting set
in $G_{1}$. Then $\nu_{1}$ is the eigenvalue of the Cayley graph ${\rm
Cay}(G_{1},H_{1})$ occurring on $L$. In particular, if $H_{1}$ is a single
conjugacy class of $G_{1}$ and $\chi_{L}$ is the character of $L$ then
$\nu_{1}=|H_{1}|\cdot\frac{\chi_{L}(h_{1})}{\chi_{L}(1)}$, where $h_{1}\in
H_{1}$.

###### Proof.

(1) is well known. (2) (i) Clearly, $H^{+}$ commutes with every $g\in G_{1}$.
Therefore, $H^{+}L$ is a $G_{1}$-module. By assumption, $H^{+}L=L$. Then, by
Schur’s lemma, $H^{+}$ acts scalarly on $L$.
(ii) By (2), $H_{i}^{+}$ stabilizes $L$ and acts on it as
$\nu_{i}\cdot\mathop{\rm Id}\nolimits$ for $i=1,2$. As
$H^{+}=H^{+}_{1}+H^{+}_{2}$, the claim follows.
(iii) Let $V_{1}=G_{1}$ be the vertices of the Cayley graph ${\rm
Cay}(G_{1},H_{1})$. As $L$ is an irreducible $G_{1}$-module, $L$ is an
irreducible constituent of the regular $G_{1}$-module
$\mathbb{C}V_{1}=\mathbb{C}G_{1}$, and hence the eigenvalue of $H_{1}^{+}$ on
$L$ occurs as an eigenvalue of $H_{1}^{+}$ on $\mathbb{C}G_{1}$. The second
claim in (iii) follows from (1). ∎

Remarks. (1) Unfortunately, $\nu_{1}$ and $\nu_{2}$ depend not only on $L$ but
on both $M,L$. In other words, if $L$ is a constituent of $M^{\prime}$, an
irreducible $G$-module not isomorphic to $M$, then $\nu_{1}(M,L)$ may not be
equal to $\nu_{1}(M^{\prime},L)$. However, if $H_{1}=H\cap G_{1}$ then
$\nu_{1}$ depends on $L$ but does not depend on $M$.

(2) If $G=S_{n},\,G_{1}=S_{n-1}$ then every irreducible $G$-module $M$ is
multiplicity free as $G_{1}$-module (that is, every irreducible constituent of
$M|_{S_{n-1}}$ occurs exactly once). This follows from the branching rule
expressed in terms of Young diagrams (we cannot get the same diagram by
removing distinct single boxes from a given Young diagram. This remains true
for alternating groups.) In addition, if $C$ is a conjugacy class of $S_{n}$
then $C\cap S_{n-1}$ is either empty or a single conjugacy class of $G_{1}$,
as two permutations $x,y\in G_{1}$ are conjugate in $S_{n}$ if and only if
they are conjugate in $G_{1}$. In the following we view ${\rm
Sym}(1,\ldots,k)$ as the largest subgroup of $S_{n}$ which fixes all
$i\not\in\\{1,\dots,k\\},$ etc.

######  Lemma 3.2.

Let $G=S_{n}$, let $M$ be the natural permutation G-module and $F={\rm
Sym}(1,\ldots,k)\times{\rm Sym}(k+1,\ldots,n)\subset G$ for $2\leq k\leq n-2$.
Let $H\subset G$ be a set such that $xHx^{-1}=H$ for all $x\in F.$ Then
$H^{+}$ has at most $4$ distinct eigenvalues on M, two of them are of
multiplicity $1$, and two others, if distinct, are of multiplicity
multiplicity $k-1$, $n-k-1$.

###### Proof.

Set $F_{1}={\rm Sym}(1,\ldots,k)\times\mathop{\rm Id}\nolimits$ and
$F_{2}=\mathop{\rm Id}\nolimits\times{\rm Sym}(k+1,\ldots,n)$. As $H$ is
$F$-invariant, $H^{+}$ commutes with $F$ in the group algebra
$\mathbb{C}S_{n}$ and hence in ${\rm End}\,M$. We have $M|_{F}=M_{1}\oplus
M_{2}$, where $M_{i}$ is an $F$-module such that $M_{i}|_{F_{i}}$ the natural
permutation modules for $F_{i}$ and $M_{i}|_{F_{j}}$ is trivial for $i\neq j$,
$i,j=1,2$. Then $M_{1}=T_{1}\oplus L_{1}$, where $T_{1}$ is the trivial
$F_{1}$-module and $L_{1}$ is irreducible of dimension $k-1$. Similarly,
$M_{2}=T_{2}\oplus L_{2}$, where $L_{2}$ is irreducible of dimension $n-k-1$.
Clearly, $L_{1},L_{2}$ are non-equivalent non-trivial $F$-modules. So
$M|_{F}=L_{1}\oplus L_{2}\oplus T$, where $T$ is a trivial $F$-module of
dimension 2. By Schur’s lemma, $H^{+}$ acts scalarly on $L_{1},L_{2}$, and
hence $H^{+}$ has at most four distinct eigenvalues on $M$. ∎

One observes that if $k=1$ then $L_{0}=0$ and $H^{+}$ has at most three
distinct eigenvalues on $M$.

##  4\. Symmetric group: the largest conjugacy classes

For basic definitions concerning the characters of symmetric and alternating
groups see [7, 8].

Let $G=S_{n}$ and let $1\leq k\leq n.$ We denote the set of all $k$-cycles in
$G$ by $C(n,k).$ Since two permutations are conjugate to each other in $G$ if
and only if they have the same cycle type we have $|C(n,k)|=|G:C_{G}(g)|$ when
$g$ is any $k$-cycle and $C_{G}(g)$ denotes the centralizer of $g$ in $G.$ In
particular, $|C(n,n)|=(n-1)!$ and $|C(n,n-1)|=n(n-2)!.$ By the same argument,
the enumeration of permutations by cycle type shows that all other conjugacy
class sizes in $G$ are smaller if $n>4$. It is well-known that the smallest
subgroup of $S_{n}$ containing $C(n,k)$ is $S_{n}$ if $k$ is even and $A_{n}$
if $k$ is odd.

In this section we compute the second largest eigenvalue of $H^{+}$ when
$H=C(n,n)$ or $H=C(n,n-1).$ For this we first quote a well-known result for
the cycles of length $n$ in representations of $S_{n}$ [7, Lemma 21.4].

Below let $\chi=\chi_{\mu}$ denote an irreducible character of $G$ labeled by
the Young diagram $\mu$.

######  Lemma 4.1.

Let $h\in S_{n}$ be an $n$-cycle. Then $\chi(h)=0$ if $\mu$ is not a hook. If
$\mu=[n-m,1^{m}]$ is a hook with leg length m then $\chi(h)=(-1)^{m}$.

Note that for $n\geq 4$ we have $\chi_{[n-2,1^{2}]}(1)=(n-1)(n-2)/2$ and
$\chi_{[n-2,2]}(1)=n(n-3)/2$, so $\chi_{[n-2,2]}(1)+1=\chi_{[n-2,1^{2}]}(1)$.

######  Lemma 4.2.

Let $h\in S_{n}$ be an $n$-cycle, $n>4$, and let $H=h^{G}$ be the conjugacy
class of $h.$
$(1)$ Suppose that $n$ is odd. Then the maximum of the irreducible character
ratio $\chi(h)/\chi(1)$ with $\chi(1)\neq 1$ is attained at
$\chi_{[n-2,1^{2}]}$ and equals $2/(n-1)(n-2)$. The corresponding eigenvalue
of $H^{+}$ equals $2|H|/(n-1)(n-2)=2(n-3)!$.
$(2)$ Suppose that n is even. Then the maximum of the irreducible character
ratio $\chi(h)/\chi(1)$ with $\chi(1)\neq 1$ is attained at
$\chi_{[2,1^{n-2}]}$ and equals $1/(n-1)$. The corresponding eigenvalue of
$H^{+}$ equals $|H|/(n-1)=(n-2)!$

###### Proof.

By Lemma 3.1(1), it suffices to prove the claim on the ratio, and, by Lemma
4.1, only for the hook characters $\chi_{[n-m,1^{m}]}$ with $m$ even. In this
case $\chi_{[n-m,1^{m}]}(h)=1$, so we have to show that
$\chi_{[n-m,1^{m}]}(1)$ is minimal for $m=2$ for $n$ odd and $n-2$ for $n$
even.

(1) Here $\chi_{[n-2,1^{2}]}(h)=1=\chi_{[3,1^{n-3}]}(h)$ and
$\chi_{[n-2,1^{2}]}(1)=(n-1)(n-2)/2=\chi_{[3,1^{n-3}]}$. As
$\chi_{[n-1,1]}(h)=\chi_{[2,1^{n-2}]}(h)=-1$, it suffices to show that
$\chi_{[n-m,1^{m}]}(1)>(n-1)(n-2)/2$ for $2<m<n-3$. For such $m$ we have

$\chi_{[n-m,1^{m}]}(1)=\frac{n!}{n(n-m-1)!m!}=\frac{(n-1)(n-2)\cdot...\cdot(n-m+1)}{2\cdot
3\cdot...\cdot m}>\frac{(n-1)(n-2)}{2}.$

(2) In this case $\chi_{[n-1,1]}(h)=-1$, $\chi_{[2,1^{n-2}]}(h)=1$ as these
characters differ by sign character multiple. In addition,
$\chi_{[2,1^{n-2}]}(1)=n-1<(n-1)(n-2)/2<\chi_{[n-m,1^{m}]}(1)$ for $3<m<n-4$.
So the result follows. ∎

######  Lemma 4.3.

Let $h\in G=S_{n}$, $n>4$, be an $(n-1)$-cycle and let $H$ be the conjugacy
class of $h.$
$(1)$ Suppose n is even. Then the maximum of the irreducible character ratio
$\chi(h)/\chi(1)$ with $\chi(1)\neq 1$ is attained at $\chi_{[n-3,2,1]}$ and
equals $3/n(n-2)(n-4)$; the corresponding eigenvalue of $H^{+}$ equals
$3|H|/n(n-2)(n-4)=3(n-3)(n-5)!$.
$(2)$ Suppose n is odd. Then the maximum of the irreducible character ratio
$\chi(h)/\chi(1)$ with $\chi(1)\neq 1$ is attained at $\chi_{[2,2,1^{n-4}]}$
and equals $2/n(n-3)$; the corresponding eigenvalue of $H^{+}$ equals
$2|H|/n(n-3)=2(n-2)(n-4)!$.

###### Proof.

Note that $|H|=n!/(n-1)=n(n-2)!$. Let $\chi=\chi_{\mu}$ be an irreducible
character of $G$ labeled by the Young diagram $\mu$. Suppose that $\chi(1)>1$.
Let $h\in H$; we can assume that $h\in C_{G}(n)\cong S_{n-1}$.

$(i)$ We have $\chi(h)=0$ unless $\mu=[n-m,2,1^{m-2}]$ with $(2\leq m\leq
n-2)$. To show this let $\chi|_{S_{n-1}}=\nu_{1}+\cdots+\nu_{k}$, where
$\nu_{1},\ldots,\nu_{k}$ are irreducible character of $S_{n-1}$; then
$\chi(h)=\nu_{1}(h)+\cdots+\nu_{k}(h)$. By Lemma 4.1, $\nu_{i}(h)=0$ unless
$\nu_{i}$ corresponds to a hook. So $\chi(h)=0$ unless $\mu$ is obtained from
a hook diagram by adding one box. Obviously, either $\mu$ itself is a hook or
$\mu$ is obtained from a hook diagram by adding one box at the
$(2,2)$-position, that is, $\mu=[n-m,2,1^{m-2}]$ for $m=2,\ldots,n-2$.

Suppose $\mu=[n-m,1^{m}]$ is a hook, $1\leq m\leq n-1$. Then
$\chi|_{S_{n-1}}=\nu_{1}+\nu_{2}$, where the diagrams of $\nu_{1},\nu_{2}$ are
$[n-m-1,1^{m}]$ and $[n-m,1^{m-1}]$. The legs of these hooks are of distinct
parity, so $\nu_{1}(h)+\nu_{2}(h)=0$ by Lemma 4.1.

$(ii)$ For $2\leq m\leq n-2$ set $\chi_{m}=\chi_{\mu}$ for
$\mu=[n-m,2,1^{m-2}]$. Then $\chi_{\mu}(h)=(-1)^{m-1}$.

Indeed, if $2<m<n-1$ then $\chi_{m}|_{S_{n-1}}=\nu_{1}+\nu_{2}+\nu_{3}$, where
$\nu_{1},\nu_{2},\nu_{3}$ are irreducible characters of $S_{n-1}$ with Young
diagrams $[n-m-1,2,1^{m-2}]$, $[n-m,2,1^{m-3}]$ and $[n-m,1^{m-1}]$,
respectively. So $\nu_{1}(g)=\nu_{2}(g)=0$ by Lemma 4.1, whereas
$\nu_{3}(g)=(-1)^{m-1}$. So $\chi_{m}(h)=(-1)^{m-1}$. If $m=2$ then
$\chi_{2}|_{S_{n-1}}=\nu_{1}+\nu_{3}$, whose Young diagrams are $[n-3,2]$ and
$[n-2,1]$. As above, $\nu_{1}(h)=0$, $\nu_{3}(h)=-1$ so $\chi_{2}(h)=-1$. Let
$m=n-2$, so $\mu=[2,2,1^{n-4}]$. Then
$\chi_{[2,2,1^{n-4}]}(h)=(-1)^{n}\chi_{[n-2,2]}(h)$ (because $h$ takes the
value $-1$ at the sign non-trivial character if and only if the permutation
$h$ is even). So the claim follows.

Thus, $\chi_{\mu}(h)=1$ if $\mu=[n-m,2,1^{m-2}]$ with $m$ odd, and
$\chi_{\mu}(h)<1$ otherwise (assuming $\chi_{\mu}(1)\neq 1$). Therefore, to
complete the proof of the lemma it suffices to determine the minimum of
$\chi_{\mu}(1):\,\mu=[n-m,2,1^{m-2}],\,m$ odd.

$(iii)$ Let $2\leq m\leq(n-1)/2$. Then

$\displaystyle\chi_{m}(1)$ $\displaystyle=$
$\displaystyle\frac{n!}{(n-m-2)!(n-m)(n-1)m(m-2)!}$
$\displaystyle<\,\,\,\chi_{m+1}(1)$ $\displaystyle=$
$\displaystyle\frac{n!}{(n-m-3)!(n-m-1)(n-1)(m+1)(m-1)!}$ (7)

as $(n-m-1)(m+1)(m-1)<m(n-m)(n-m-2)$. (Indeed, $m\leq(n-1)/2$ implies $n-m\geq
m+1$ and
$m(n-m)(n-m-2)\geq(n-m-2)m(m+1)=(n-m-1)m(m+1)-m(m+1)\geq(n-m-1)m(m+1)-(n-m-1)(m+1)=(n-m-1)(m+1)(m-1)$.)

$(iv)$ By $(ii)$ and $(iii)$, the maximum of the ratio
$\chi_{m}(h)/\chi_{m}(1)$ is attained for $m=n-2$ if $n$ is even, and for
$n=3$ is $n$ is odd. This implies the result.∎

We expect that the behaviour of $\chi_{[n-1,1]}(h)$ is not typical when $h$ is
a $k$-cycle with $k=n,n-1.$ Namely, for $k<n-1$ we expect that the second
largest eigenvalue is attained for $\chi=\chi_{[n-1,1]}$.

By Lemma 2.7 we have:

######  Lemma 4.4.

For $n>4$ let $H$ be the set of all $n$-cycles in $A_{n}$ if $n>3$ is odd and
all $n-1$-cycles in $A_{n}$ if $n>5$ is even. Then $H$ is a connecting set in
$V=A_{n}$ and the largest second eigenvalue of $H^{+}$ on the Cayley graph
$Cay(A_{n},H)$ equals $2(n-3)!$ and $3(n-3)(n-5)!$ respectively.

###### Proof of Theorems 1.1 and 1.2.

If $G=A_{n}$ the result follows from Lemma 4.4. If $G=S_{n}$ then ${\rm
Cay}(G,H)$ is bipartite, with partition $G=A_{n}\cup(S_{n}\setminus A_{n}),$
since $u\sim v$ implies that $uv^{-1}\in H\subset S_{n}\setminus A_{n}$ and so
$u,\,v$ do not have the same parity. Hence $|H|$ and $-|H|$ are eigenvalues of
${\rm Cay}(G,H)$ by Theorem 2.1, corresponding to the trivial and the
alternating characters of $S_{n},$ respectively. All other characters have
degree $>1$ and so the result follows from Lemmas 4.2 and 4.3. ∎

##  5\. The natural $S_{n}$-module and equitable partitions

Let $G=S_{n}$ and let $K$ be the stabilizer of some point in
$\\{1,\ldots,n\\}.$ Then the set $G/K$ of cosets of $K$ in $G$ and
$\\{1,\ldots,n\\}$ are isomorphic as $G$-sets. The associated permutation
module over $\mathbb{C}$ is the natural module for $G,$ denoted $M=1^{G}_{K}.$
This is probably the most important $S_{n}$-module. Moreover, we expect that
in a majority of cases the second largest eigenvalue of Cayley graphs over
$S_{n}$ occurs on $M$ (although we have no means to justify this).

For $1\leq r<k\leq n$ let $C(n,k;r)\subseteq C(n,k)$ be the set of all
$k$-cycles in $S_{n}$ which move all the points in the set
$\\{1,2,\ldots,r\\}.$ That is to say,
$g=(i_{1},i_{2},\ldots,i_{k})(i_{k+1})\dots(i_{n})\in C(n,k;r)$ if and only if
$\\{1,2,\ldots,r\\}\subset\\{i_{1},i_{2},\ldots,i_{k}\\}.$ Clearly,
$|C(n,k;r)|=(k-1)!{n-r\choose k-r}.$

######  Lemma 5.1.

Let $1\leq r<k\leq n$ and let X be the smallest subgroup of $S_{n}$ containing
$C(n,k;r).$ Then $X=S_{n}$ if $k$ is even, and $X=A_{n}$ if $k$ is odd.

###### Proof.

This holds when $k=n$ since $C(n,n;r)=C(n,n)$ for all $r$ and so it suffices
to show that $X\supseteq{\rm Alt}_{n}$ for $1\leq r<k<n.$ Since for every
$i\in\\{2,\ldots,n\\}$ there is some $h\in C(n,k;r)$ with $h(i)=1$ it follows
that $X$ is transitive on $\\{1,2,\ldots,n\\}.$ If $i<n$ we may assume
additionally that $h(n)=n$ since $k<n.$ Hence the stabilizer of $n$ in $X$ is
transitive on $\\{1,2,\ldots,n-1\\}$ and so $X$ is doubly transitive. The
result follows if $k=2$ or $=3,$ since a double transitive group containing a
$2$\- or $3$-cycle contains ${\rm Alt}_{n}.$ For $k\geq 4$ consider the
elements $h=(1,2,\ldots,k-3,k-2,k-1,k)$ and
$h^{\prime}=(k-1,k,k-2,k-3,\ldots,2,1).$ Then
$h^{\prime}h=(1)(2)\dots(k-3)(k-2,k,k-1)\in X$ is a $3$-cycle and hence the
result follows.∎

######  Theorem 5.2.

Let $G=S_{n}$ and $H=C(n,k;r)$ for $2\leq r<k<n$. Then the eigenvalues of
$H^{+}$ on the natural module $M$ are

$\mu_{1}=|H|=(k-1)!{n-r\choose k-r}$, $\mu_{4}=-(k-2)!{n-r\choose k-r}$

$\mu_{2}=(k-2)!\begin{pmatrix}n-r\\\
k-r\end{pmatrix}\big{(}k-1-\frac{(k-r)(2k-2-r)}{n-r}\big{)}$ and
$\mu_{3}=(k-2)!{n-r\choose k-r}\big{(}\frac{r(n-k)}{n-r}-1\big{)}.$

In the remainder of this section let $r,\,k,$ $G$ and $H$ be as in the theorem
and put $\Gamma={\rm Cay}(G,H).$ We exhibit two equitable partitions of
$\Gamma$ so that the associated eigenvalues belong to
$\\{\mu_{1},\,\mu_{2},\,\mu_{3},\,\mu_{4}\\}.$ The proof is completed at the
end of the section.

First let $K_{1}=K={\rm Sym}(1,\ldots,n-1)$ be the stabilizer in $G$ of $n.$
Define the partition $P_{1}$ of the vertices of $\Gamma$ by

$\displaystyle V_{1}$ $\displaystyle=$ $\displaystyle K=\\{g\in
G:\,\,g(n)=n\\};$ $\displaystyle V_{2}$ $\displaystyle=$
$\displaystyle(n,1)K\cup\dots\cup(n,r)K=\\{g\in
G:\,\,g(n)\in\\{1,...,r\\}\\};$ $\displaystyle V_{3}$ $\displaystyle=$
$\displaystyle(n,r+1)K\cup\dots\cup(n,n-1)K=\\{g\in
G:\,\,g(n)\in\\{r+1,...,n-1\\}\\}.$ (8)

Below ${a\choose b}$ for integers $a\geq b>0$ denotes the number of choices of
$b$ elements from a set of $a$ elements. For uniformity we need to make the
cases with $b=0$ and $b=-1$ meaningful: we define ${a\choose 0}$ to be 1, and
${a\choose-1}$ to be $0$.

######  Lemma 5.3.

Let $2\leq r<k<n.$ Then $P_{1}$ is an equitable partition of $\Gamma$ with
matrix

$B_{1}=\begin{pmatrix}\,\,\,(k-1)!{n-r-1\choose k-r}&r(k-2)!{n-r-1\choose
k-r-1}&(n-r-1)(k-2)!{n-r-2\choose k-r-2}\,\,\,\cr&&\cr(k-2)!{n-r-1\choose
k-r-1}&(r-1)(k-2)!{n-r\choose k-r}&(n-r-1)(k-2)!{n-r-1\choose
k-r-1}\cr&&\cr(k-2)!{n-r-2\choose k-r-2}&r(k-2)!{n-r-1\choose
k-r-1}&(n-r-2)(k-2)!{n-r-2\choose k-r-2}+(k-1)!{n-r-1\choose
k-r}\end{pmatrix}$

$=(k-2)!\begin{pmatrix}\,\,\,(k-1){n-r-1\choose k-r}&r{n-r-1\choose
k-r-1}&(k-r-1){n-r-1\choose k-r-1}\,\,\,\cr&&\cr{n-r-1\choose
k-r-1}&(r-1){n-r\choose k-r}&(n-r-1){n-r-1\choose k-r-1}\cr&&\cr{n-r-2\choose
k-r-2}&r{n-r-1\choose k-r-1}&(n-r-2){n-r-2\choose k-r-2}+(k-1){n-r-1\choose
k-r}\end{pmatrix}.$

The eigenvalues of $B_{1}$ are
$\mu_{1}=(k-1)!{n-r\choose k-r}$, $\mu_{2}=(k-2)!\begin{pmatrix}n-r\\\
k-r\end{pmatrix}\big{(}k-1-\frac{(k-r)(2k-2-r)}{n-r}\big{)}$ and
$\mu_{3}=(k-2)!{n-r\choose k-r}(r-1-r\frac{k-r}{n-r}\,)=(k-2)!{n-r\choose
k-r}\big{(}\frac{r(n-k)}{n-r}-1\big{)}.$

###### Proof.

Put $F={\rm Sym}(1,\ldots,r)\times{\rm Sym}(r+1,\ldots,n-1)$ and let $F\times
K$ act on $V$ as in Lemma 2.8. Then $F\times K$ stabilizes each $V_{i}$ and
acts transitively on it. Hence $P_{1}$ is equitable by Lemma 2.3.

Let $B_{1}=(\beta_{ij})$ for $1\leq i,j\leq 3$ and so
$\beta_{ij}=|N(v_{i})\cap V_{j}|=|Hv_{i}\cap V_{j}|=|H\cap V_{j}v_{i}^{-1}|$
for $v_{i}\in V_{i}.$ Taking $v_{1}=1_{G},\,v_{2}=(n,1)$ and $v_{3}=(n,n-1)$
we have

($i=1$): $\beta_{11}=|H\cap K|=(k-1)!{n-r-1\choose k-r};$
$\beta_{12}=|H\cap V_{2}|=r|H\cap Kv_{2}|=r(k-2)!{n-r-1\choose k-r-1};$
$\beta_{13}=|H\cap V_{3}|=(n-r-1)\,|H\cap v_{3}K|=(n-r-1)(k-2)!{n-r-2\choose
k-r-2}$.

($i=2$): $\beta_{21}=r\,|H\cap K(n,1)|=|\\{h\in
H\,:\,h(1)=n\\}|=(k-2)!{n-r-1\choose k-r-1};$
$\beta_{22}=|H\cap
V_{2}v_{2}|=|H\cap(n,1)Kv_{2}|+|H\cap(n,2)Kv_{2}|+\dots+|H\cap(n,r)Kv_{2}|=\\\
{}\hskip 28.45274pt=0+(r-1)\,|(n,2)Kv_{2}\cap H|=(r-1)(k-2)!{n-r\choose k-r};$
$\beta_{23}=|H\cap
V_{3}v_{2}|=|H\cap(n,r+1)K(n,1)|+\dots+|H\cap(n,n-1)K(n,1)|=(n-r-1)(k-2!){n-r-1\choose
k-r-1}$.

$(i=3)$: $\beta_{31}=|H\cap V_{1}v_{3}|=(k-2)!{n-r-2\choose k-r-2};$
$\beta_{32}=|H\cap V_{2}v_{3}|=r(k-2)!{n-r-1\choose k-r-1};$
$\beta_{33}=|H\cap V_{3}v_{3}|=(n-r-2)(k-2)!{n-r-2\choose
k-r-2}+(k-1)!{n-r-1\choose k-r}$ .

This gives the matrix above after some further transformations. One easily
checks that the eigenvalues of $B_{1}$ are as stated.∎

Next let $K_{2}=K={\rm Sym}(2,\ldots,n)$ be the stabilizer in $G$ of $1.$
Define the partition $P_{2}$ of the vertices of $\Gamma$ by

$\displaystyle V_{1}$ $\displaystyle=$ $\displaystyle K=\\{g\in
G:\,\,g(1)=1\\}$ $\displaystyle V_{2}$ $\displaystyle=$
$\displaystyle(2,1)K\cup\dots\cup(r,1)K=\\{g\in G:\,\,g(1)\in\\{2,...,r\\}\\}$
$\displaystyle V_{3}$ $\displaystyle=$
$\displaystyle(r+1,1)K\cup\dots\cup(n,1)K=\\{g\in
G:\,\,g(1)\in\\{r+1,...,n\\}\\}$ (9)

######  Lemma 5.4.

Let $2\leq r<k<n.$ Then $P_{2}$ is an equitable partition of $\Gamma$ with
matrix

$B_{2}=\begin{pmatrix}\,\,\,0&(r-1)(k-2)!{n-r\choose
k-r}&(k-r)(k-2)!{n-r\choose k-r}\,\,\,\cr&&\cr(k-2)!{n-r\choose
k-r}&(k-2)!(r-2){n-r\choose k-r}&(k-r)(k-2)!{n-r\choose
k-r}\cr&&\cr(k-2)!{n-r-1\choose k-r-1}&(r-1)(k-2)!{n-r\choose
k-r-1}&(k-2)!(n-r-1){n-r-2\choose k-r-2}+(k-1)!{n-r-1\choose
k-r}\end{pmatrix}$ $=(k-2)!{n-r\choose
k-r}\begin{pmatrix}\,\,\,0&r-1&k-r\,\,\,\cr&&\cr
1&r-2&k-r\cr&&\cr\,\,\frac{k-r}{n-r}&\,\,(r-1)\frac{k-r}{n-r}&\,\,\,k-1-r\frac{(k-r)}{n-r}\,\,\end{pmatrix}.$

The eigenvalues of $B_{2}$ are $\mu_{1}=(k-1)!{n-r\choose k-r}$,
$\mu_{3}=(k-2)!{n-r\choose k-r}\big{(}\frac{r(n-k)}{n-r}-1\big{)}$ and
$\mu_{4}=-(k-2)!{n-r\choose k-r}$.

###### Proof.

Put $F={\rm Sym}(2,\ldots,r)\times{\rm Sym}(r+1,\ldots,n)$ and let $F\times K$
act on $V$ as in Lemma 2.8. Then $F\times K$ stabilizes each $V_{i}$ and acts
transitively on it. Hence $P_{1}$ is equitable by Lemma 2.3.

Let $B_{2}=(\beta_{ij})$ for $1\leq i,j\leq 3$ and so
$\beta_{ij}=|N(v_{i})\cap V_{j}|=|Hv_{i}\cap V_{j}|=|H\cap V_{j}v_{i}^{-1}|$
for $v_{i}\in V_{i}.$ Taking $v_{1}=1_{G},\,v_{2}=(2,1)$ and $v_{3}=(n,1)$ we
have

($i=1$): $\beta_{11}=|H\cap K|=0;$
$\beta_{12}=|H\cap V_{2}|=(r-1)(k-2)!{n-r\choose k-r};$
$\beta_{13}=|H\cap V_{3}|=(n-r)(k-2)!{n-r-1\choose
k-r-1}=(k-r)(k-2)!{n-r\choose k-r}$.

($i=2$): $\beta_{21}=|H\cap K(12)|=(k-2)!{n-r\choose k-r};$
$\beta_{22}=|H\cap V_{2}(1,2)|=(r-2)(k-2)!{n-r\choose k-r};$
$\beta_{23}=|H\cap V_{3}(1,2)|=(n-r)(k-2)!{n-r-1\choose
k-r-1}=(k-r)(k-2)!{n-r\choose k-r}.$

($i=3$): $\beta_{3,1}=|H\cap K(1,n)|=(k-2)!{n-r-1\choose k-r-1};$
$\beta_{32}=|H\cap V_{2}(1,n)|=(k-2)!(r-1){n-r-1\choose k-r-1};$
$\beta_{33}=|H\cap V_{3}(1,n)|=(k-2)!(n-r-1){n-r-2\choose
k-r-2}+(k-1)!{n-r-1\choose k-r}=\\\ {}\hskip
28.45274pt=(k-2)!(k-r-1){n-r-1\choose k-r-1}+(k-1)!{n-r-1\choose k-r}.$

This gives the matrix above after some further transformations. One easily
checks that the eigenvalues of $B_{2}$ are as stated. ∎

Proof of Theorem 5.2. Let $1\leq r<k<n,$ $H=C(n,k,r)\subset Sym(1,\ldots,n)$
and let $\mu_{1},\,\mu_{2},\,\mu_{3},\,\mu_{4}$ be the eigenvalues stated in
Lemmas 5.3 and 5.4. By Lemma 2.2, we have $\mu_{1}=\lambda_{1}(\Gamma).$ Since
$G/K_{1}$ and $G/K_{2}$ are permutationally isomorphic, by Lemma 2.2,
$\mu_{1},\,\mu_{2},\,\mu_{3},\,\mu_{4}$ are distinct eigenvalue of $H^{+}$ on
$M.$ Next we note that $H$ is invariant under conjugation by $F={\rm
Sym}(1,\ldots,r)\times{\rm Sym}(r+1,\ldots,n).$ By Lemma 3.2, $H^{+}$ has at
most four eigenvalues and hence the result. $\Box$

##  6\. Proof of Theorem 1.3

In this section let $4<n,$ $2\leq r\leq n-2$ and $H=C(n,r+1;r)\subset S_{n}$.
Let $M$ be the natural $S_{n}$-module.

######  Lemma 6.1.

The multiplicities of the eigenvalues of $H^{+}$ on M are as follows:

Eigenvalue of $H^{+}$ on $M$ | $r!(n-r)$ | $r!(n-r-1)$ | $(r-1)(r-1)!(n-r-1)-r!$ | $-(r-1)!(n-r)$
---|---|---|---|---
the multiplicity | $1$ | $n-r-1$ | $1$ | $r-1$

###### Proof.

The eigenvalues of $|H^{+}|$ on $M$ are determined in Theorem 5.2, where we
take $k=r+1$. Note that the trace of $h\in H$ on $M$ equals $n-r-1$. So the
trace of $H^{+}$ equals $|H^{+}|(n-r-1)=r!(n-r)(n-r-1)$. We know that the
eigenvalue $|H^{+}|$ has multiplicity 1 (Theorem 2.1), and the multiplicities
$x,y,z$ of the three other eigenvalues are in the set $\\{1,n-r-1,r-1\\}$ by
Lemma 3.2. So we have

$|H^{+}|(n-r-1)=r!(n-r)(n-r-1)=r!(n-r)+xr!(n-r-1)+y((r-1)(r-1)!(n-r-1)-r!)-z(r-1)!(n-r).$

If we take $x=n-r-1$, $y=1$, $z=r-1$ then the equality holds. In addition, the
equality fails for any other choice of $\\{x,y,z\\}\in\\{1,n-r-1,r-1\\}$.
Whence the result. ∎

######  Corollary 6.2.

Let $M^{\prime}$ be an $S_{n}$-module whose composition factor dimensions are
at most $n-1$. Then the second largest eigenvalue of $H^{+}$ on $M^{\prime}$
does not exceed $r!(n-r-1)$.

###### Proof.

Let $\rho$ be an irreducible characters of $S_{n}$ of degree at most $n-1$.
Then $\rho$ is well known to be a constituent either of $M$ or
$M\otimes\sigma$, where $\sigma$ denotes the sign representation of $S_{n}$.
It follows that the eigenvalues of $H^{+}$ on $M^{\prime}$ are in the list of
Lemma 3.2 if $r$ is even, and also their negatives, if $r$ is odd. So the
result follows as $r!(n-r-1)>(r-1)!(n-r)$. ∎

######  Lemma 6.3.

Let $G=S_{n}$ and let L be an irreducible $G$-module. Then there is a basis of
L such that the matrices $g+g^{-1}$ $(g\in G)$ are symmetric. Consequently, if
$H\subset G$ is a subset such that $H=H^{-1}$ then the matrix of $H^{+}$ on L
is symmetric.

###### Proof.

It is well known that there is a basis of $L$ such that all matrices $g\in G$
are orthogonal, that is, if $g_{L}$ is the matrix of $g$ on $L$ then
$g_{L}^{T}=(g_{L})^{-1}=(g^{-1})_{L}$, where $(g_{L})^{T}$ is the transpose of
$g_{L}$. Then $g_{L}+g_{L}^{-1}=g_{L}+(g_{L})^{T}$, whence the claim.∎

######  Lemma 6.4.

Let L be an irreducible $S_{n}$-module and $\lambda$ an eigenvalue of $H^{+}$
on L. Then $\lambda\leq|H|$ and $\lambda=|H|$ implies $\dim L=1$.

###### Proof.

If $H$ is connecting then the lemma follows from Theorem 2.1. Indeed,
$\lambda=|H|$ if $L$ is the trivial module, and the trivial module has
multiplicity 1 in $\mathbb{C}S_{n}$. If $H$ is not a connecting set then $H$
is a connecting set of $A_{n}$ (Lemma 5.1), and the same argument is valid if
$L$ is an $A_{n}$-module. So $|H|$ is an eigenvalue of $H^{+}$ on $L$ if and
only if the restriction of $L$ to $A_{n}$ contains the trivial $A_{n}$-module.
This is well known to imply that $\dim L=1$. ∎

Set $H_{n-1}=H\cap K$, where $K={\rm Sym}(1,\ldots,n-1)$ and $E=H\setminus
H_{n-1}\subset{\rm Sym}(1,\ldots,n-2,n)$. Then $|H_{n-1}|=r!(n-r-1)$ and
$|E|=|H|-|H_{n-1}|=r!$

######  Theorem 6.5.

Let L be an irreducible $S_{n}$-module and $\dim L>n-1$. Let $\lambda$ be an
eigenvalue of $H^{+}$ on L. Then $\lambda\leq r!(n-r-1)$.

######  Lemma 6.6.

Theorem 6.5 is true for $r=n-2>2$.

###### Proof.

The case of $n=5$ can be checked straightforwardly. Let $n>5$.

Note that $r!(n-r-1)$ equals $(n-2)!$ for $r=n-2$. We have
$H_{n-1}=\\{(n-1,i_{1},\ldots,i_{n-2})\\}$ and
$E=\\{(n,i_{1},\ldots,i_{n-2})\\}$, where
$\\{i_{1},\ldots,i_{n-2}\\}=\\{1,\ldots,n-2\\}$. So $H_{n-1}$ is a conjugacy
class in $Sym\\{1,\ldots,n-1\\}$. Let $\alpha_{1},\beta_{1}$ be the maximum of
eigenvalues of $H_{n-1}^{+},E^{+}$, respectively, on $L$. By the branching
rule, as an $S_{n-1}$-module $L$ has no irreducible constituent of dimension
1. So, by Lemma 4.2, if $n-1>4$ is even then $\alpha_{1}\leq(n-3)!$, and if
$n-1$ is odd then this is at most $\alpha_{1}\leq 2(n-4)!$. As $E$ is a
conjugacy class of $Sym(1,\ldots,n-2,n)\cong S_{n-1}$, the same conclusion
holds for the eigenvalue $\beta_{1}$ of $E^{+}$and $\alpha_{1}=\beta_{1}$. By
Lemma 6.3, we can assume that the matrices of $H^{+},$ $H_{n-1}^{+}$, $E$ on
$L$ are symmetric. If $\gamma_{1}$ is the largest eigenvalue of $H^{+}$ on
$L$, then, by the Weyl inequality,
$\gamma_{1}\leq\alpha_{1}+\beta_{1}=2\alpha_{1}$. So $\gamma_{1}\leq 4(n-4)!$
if $n-1$ is odd, and $\gamma_{1}\leq 2(n-3)!$ if $n-1$ is even. Obviously,
$\gamma_{1}<(n-2)!$. ∎

###### Proof of Theorem 6.5.

As mentioned above, as an $S_{n-1}$-module $L$ has no composition factor of
dimension $1.$ Therefore, by Lemma 6.4, $H_{n-1}^{+}$ does not have eigenvalue
$|H_{n-1}^{+}|=r!(n-r-1)$ on $L$. We use induction on $n-r$ with $n-r=2$ as
base of induction. The case with $r=n-2$ is settled in Lemma 6.6. By the
induction assumption, if $\mu$ is an eigenvalue of $H_{n-1}^{+}$ on $L$ then
$\mu\leq r!(n-r-2)$.

Let $\nu$ be the largest eigenvalue of $E^{+}$ on $L$. Then $\nu\leq|E|=r!$
(by Theorem 2.1 applied to the graph $(E,V)$.) By the Weyl inequality (4)
applied to $L,$ we have $\lambda\leq\mu+\nu\leq r!(n-r-2)+r!=r!(n-r-1)$, as
required. ∎

###### Proof of Theorem 1.3.

If $G=S_{n}$ then then this is equivalent to Theorem 6.5. For $A_{n}$ the
result follows from the statement for $S_{n}$ and Lemma 2.7. ∎

## References

  * [1] N. Alon, Eigenvalues and Expanders, Combinatorica 6(1986), $83-96$.
  * [2] W. Barrett, Hermitian and Positive Definite Matrices, Chapter 8 in: Handbook in Linear Algebra, Chapman and Hall, London, 2007.
  * [3] A.E. Brouwer and W.H. Haemers, Spectra of Graphs, Springer, Berlin, 2012.
  * [4] P. Dembowski, Finite Geometries, Springer Verlag, Berlin, 1968.
  * [5] S. Hoory, N. Linial, A. Wigderson, Expander Graphs and their Applications, Bull. Amer. Math. Soc., 43(2006), $439-561$.
  * [6] X. Huang and Q. Huang, The second largest eigenvalue of some Cayley graphs on alternating groups, J. Algebraic Combinatorics 50(2019), $99-111$.
  * [7] G. James, The Representation Theory of the Symmetric Groups, Springer, Berlin, 1978.
  * [8] G. James and A. Kerber, The Representation Theory of the symmetric group, Addison-Wesley, London, 1981.
  * [9] K. Kalpakis and Y. Yesha, On the bisection width of the transposition network, Networks 29(1997), $69-76$.
  * [10] M. Krebs and A. Shaheen, Expander Families and Cayley Graphs, Oxford Univ. Press, Oxford, 2011.
  * [11] X. Liu and S. Zhou, Eigenvalues of Cayley graphs, ArXiv 1809.09829v2 [math.CO], 22 Jan 2019.
  * [12] A. Lubotzky, Cayley Graphs: Eigenvalues, Expander and Random Walks; in: Surveys in Combinatorics BCC 1995, ed. P. Rowlinson, LMS Mathematical Lecture Notes, Vol. 218 (1995), $155-191$.
  * [13] Z. Stanic, Inequalities for Graph Eigenvalues, LMS Lecture Note Series, Vol 423, Cambridge Univ. Press, Cambridge, 2015.
  * [14] J. Siemons and A.E. Zalesski, Remarks on singular Cayley graphs and vanishing elements of simple groups, J. Algebraic Combinatorics 50(2019), $379-401$.
  * [15] H.Weyl, Das asymptotische Verteilungsgesetz der Eigenwerte linearer partieller Differentialgleichungen, Math. Ann. 71(1912), $441-479$.