论文标题
在对称群的某些cayley图的第二大特征值中
On the second largest eigenvalue of some Cayley graphs of the Symmetric Group
论文作者
论文摘要
令$ s_n $和$ a_ {n} $分别在集合$ \ {1，..，n \}，$上表示对称和交替组。在本文中，我们对Cayley图的第二大特征值$λ_{2}（2}（γ）$ 令$ 1 <k \ leq n $表示$ c（n，k）的所有$ k $ -cycles in $ c（n，k）。 奇怪的）。此外，对于$ h = c（n，n，n-1）$，我们有$λ_{2}（γ）= 3（n-3）（n-5）！$（当$ n $均为偶数）和$λ_{2}（γ）= 2（n-2）= 2（n-2）（n-5）（n-5）！ Case $ h = C（n，3）$在X.Huang和Q. Huang中被考虑，这是交替组上一些Cayley图的第二大特征值，J。Algebraic Combinatorics} 50（2019），$ 99-111 $。 令$ 1 \ leq r <k <n $和让$ c（n，k; r）\ subseteq c（n，k）$设置为所有$ k $ -cycles in $ s_ {n} $中的所有$ s {n} $，这些点在集合$ \ {1,2，...，...，r \}中移动所有点i_ {k}）（i_ {k+1}）\ dots（i_ {n}）\ in c（n，k; r）$ in c（n，k; r）$ if and仅当且仅当$ \ {1,2，...，...，r \} \ subset \ subset \ subset \ subset \ {i_ {1}，I_ {1}，I_ {2}，I_ {2}，... 我们的主要结果涉及$λ_{2}（γ）$，其中$γ= CAY（g，h）$，带$ h = C（n，k; r）$，$ 1 \ leq r <k <n $当$ g = s_ {n} $均匀而$ g = a_ g = a_ {n} $时，当$ g = s_ {n} $时。在这里，我们观察到$$λ_{2}（γ）\ geq（k-2）！ {N-R \选择K-R} \ frac {1} {N-R} \ big（（K-1）（n-k） - \ frac {（k-r-1）（k-r-1）（k-r）} {n-r-1} \ big）。$$我们表明，在特殊情况下，这种限制在特殊情况下是庞大的$ k = r+1 $ $ $ 1 $，给予$ 1 $，给予$ $ up / $ c = r）= 2} c（r！ $ h = c（n，3; 1）$和$ h = c（n，3; 2）$的案例在X. Huang和Q. Huang的同一篇论文中被考虑。
Let $S_n$ and $A_{n}$ denote the symmetric and alternating group on the set $\{1,.., n\},$ respectively. In this paper we are interested in the second largest eigenvalue $λ_{2}(Γ)$ of the Cayley graph $Γ=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 $λ_{2}(Γ)=(n-2)!$ (when $n$ is even) and $λ_{2}(Γ)=2(n-3)!$ (when $n$ is odd). Further, for $H=C(n,n-1)$ we have $λ_{2}( Γ)=3(n-3)(n-5)!$ (when $n$ is even) and $λ_{2}(Γ)=2(n-2)(n-5) !$ (when $n$ is odd). The case $H=C(n,3)$ has been considered in X. Huang and Q. Huang, The second largest eigenvalue of some Cayley graphs on alternating groups, J. Algebraic Combinatorics} 50(2019), $99-111$. 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,..., r\}.$ That is to say, $g=(i_{1},i_{2}... i_{k})(i_{k+1})\dots(i_{n})\in C(n,k;r)$ if and only if $\{1,2,..., r\}\subset \{i_{1},i_{2},..., i_{k}\}.$ Our main result concerns $λ_{2}( Γ)$, where $Γ=Cay(G,H)$ with $H=C(n,k;r)$ with $1\leq r<k<n$ when $G=S_{n}$ if $k$ is even and $G=A_{n}$ if $k$ is odd. Here we observe that $$λ_{2}( Γ)\geq (k-2)! {n-r \choose k-r} \frac{1}{n-r} \big((k-1)(n-k) - \frac{(k-r-1)(k-r)}{n-r-1}\big).$$ We show that this bound is sharp in the special case $k=r+1$ , giving $λ_{2}(Γ)=r!(n-r-1)$. The cases with $H=C(n,3;1)$ and $H=C(n,3;2)$ were considered earlier in the same paper of X. Huang and Q. Huang.
