2020/12/22 by Johannes Siemons, Siemons, Johannes, Alexandre Zalesski +1 · 1 citation
Engineering · Mathematics · #20G05 #20G40 #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Graph theory and applications #Representation Theory (math.RT) #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2012.12460
openalex publication_date 2020/12/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let Sn and An denote the symmetric and alternating group on the set\n 1,.., n , respectively. In this paper we are interested in the second\nlargest eigenvalue \λ2(\Γ) of the Cayley graph \Γ=Cay(G,H)\nover G=Sn or An for certain connecting sets H.\n Let 1<k\≤ n and denote the set of all k-cycles in Sn by C(n,k).\nFor H=C(n,n) we prove that \λ2(\Γ)=(n-2)! (when n is even)\nand \λ2(\Γ)=2(n-3)! (when n is odd). Further, for H=C(n,n-1)\nwe have \λ2( \Γ)=3(n-3)(n-5)! (when n is even) and\n\λ2(\Γ)=2(n-2)(n-5) ! (when n is odd). The case H=C(n,3) has\nbeen considered in X. Huang and Q. Huang, The second largest eigenvalue of some\nCayley graphs on alternating groups, J. Algebraic Combinatorics 50(2019),\n99-111.\n Let 1\≤ r<k<n and let C(n,k;r) \⊆ C(n,k) be set of all\nk-cycles in Sn which move all the points in the set 1,2,..., r .\nThat is to say, g=(i1,i2... ik)(ik+1)\…(in)\∈ C(n,k;r) if\nand only if 1,2,..., r \⊂ i1,i2,..., ik .\n Our main result concerns \λ2( \Γ), where \Γ=Cay(G,H) with\nH=C(n,k;r) with 1\≤ r<k<n when G=Sn if k is even and G=An if\nk is odd. Here we observe that
lambda2(
Gamma)
geq (k-2)! n-r
choose\nk-r
frac1n-r
big((k-1)(n-k) -
frac(k-r-1)(k-r)n-r-1
big). We show\nthat this bound is sharp in the special case k=r+1 , giving\n\λ2(\Γ)=r!(n-r-1). The cases with H=C(n,3;1) and H=C(n,3;2)\nwere considered earlier in the same paper of X. Huang and Q. Huang.\n