×

On the partitions associated with the smallest eigenvalues of certain Cayley graphs on symmetric group generated by cycles. (English) Zbl 1473.05173

Summary: Let \(\mathcal{S}_n\) be the symmetric group on \([n]=\{1,2,\dots,n\}\) and \(\mathcal{Z}_n(s)=\{\alpha\in\mathcal{S}_n:\alpha \text{ is an }s\text{-cycle}\}\) where \(2\leq s\leq n\). In this paper, we determine all the partitions associated with the smallest eigenvalues of the Cayley graph \(\Gamma(\mathcal{S}_n,\mathcal{Z}_n(s))\) for \(s=3\).

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
20C10 Integral representations of finite groups
05A05 Permutations, words, matrices
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abdollahi, A.; Vatandoost, E., Which Cayley graphs are integral?, Electron. J. Comb., 16, 1, Article R122 pp. (2009) · Zbl 1186.05064
[2] Babai, L., Spectra of Cayley graphs, J. Comb. Theory, Ser. B, 27, 180-189 (1979) · Zbl 0338.05110
[3] Chapuy, G.; Féray, V., A note on a Cayley graph of \(S_n\)
[4] Chen, B. F.; Ghorbani, E.; Wong, K. B., On the eigenvalues of certain Cayley graphs and arrangement graphs, Linear Algebra Appl., 444, 246-253 (2014) · Zbl 1285.05087
[5] Curtis, C. W.; Reiner, I., Representation Theory of Finite Groups and Associative Algebras, Pure and Applied Mathematics, vol. XI (1962), Wiley: Wiley New York · Zbl 0131.25601
[6] Diaconis, P.; Shahshahani, M., Generating a random permutation with random transpositions, Z. Wahrscheinlichkeitstheor. Verw. Geb., 57, 159-179 (1981) · Zbl 0485.60006
[7] Friedman, J., On Cayley graphs on the symmetric group generated by transpositions, Combinatorica, 20, 505-519 (2000) · Zbl 0996.05066
[8] Ingram, R. E., Some characters of the symmetric group, Proc. Am. Math. Soc., 1, 3, 358-369 (1950) · Zbl 0054.01103
[9] Isaacs, I. M., Character Theory of Finite Groups (1976), Academic Press: Academic Press New York · Zbl 0337.20005
[10] James, G. D., The Representation Theory of the Symmetric Groups (1978), Springer-Verlag: Springer-Verlag New York · Zbl 0393.20009
[11] Kabanov, V. V.; Konstantinova, E. V.; Shalaginov, L.; Valyuzhenich, A., The Star graph eigenfunctions with non-zero eigenvalues, Linear Algebra Appl., 610, 222-226 (2021) · Zbl 1458.05144
[12] Kalpakis, K.; Yesha, Y., On the bisection width of the transposition network, Networks, 29, 69-76 (1997) · Zbl 0874.05029
[13] Krakovski, R.; Mohar, B., Spectrum of Cayley graphs on the symmetric group generated by transpositions, Linear Algebra Appl., 437, 1033-1039 (2012) · Zbl 1243.05149
[14] Lakshmivarahan, S.; Jwo, Jung-Sing; Dhall, S. K., Symmetry in interconnection networks based on Cayley graphs of permutation groups: a survey, Parallel Comput., 19, 361-407 (1993) · Zbl 0777.05064
[15] T.S.C. Lau, K.B. Wong, The Spectrum of Cayley graphs on symmetric group generated by certain subset of r-cycles, preprint. · Zbl 1504.05129
[16] Leighton, F. T., Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes (1992), Morgan Kaufmann Publishers, Inc.: Morgan Kaufmann Publishers, Inc. California · Zbl 0743.68007
[17] Lubotzky, A., Discrete Groups, Expanding Graphs, and Invariant Measures (1994), Birkhäuser Verlag: Birkhäuser Verlag Basel · Zbl 0826.22012
[18] Mühle, Henri; Nadeau, Philippe, The alternating group generated by 3-cycles, Proceedings of the 29th Conference on Formal Power Series and Algebraic Combinatorics. Proceedings of the 29th Conference on Formal Power Series and Algebraic Combinatorics, London. Proceedings of the 29th Conference on Formal Power Series and Algebraic Combinatorics. Proceedings of the 29th Conference on Formal Power Series and Algebraic Combinatorics, London, Sémin. Lothar. Comb., 78B, Article 36 pp. (2017) · Zbl 1384.05179
[19] Ram Murty, M., Ramanujan graphs, J. Ramanujan Math. Soc., 18, 1-20 (2003) · Zbl 1038.05038
[20] Sagan, B. E., The Symmetric Group, Grad. Texts in Math., vol. 203 (2001), Springer-Verlag: Springer-Verlag New York · Zbl 0964.05070
[21] Serre, J. P., Linear Representations of Finite Groups (1977), Springer-Verlag: Springer-Verlag New York · Zbl 0355.20006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.