zbMATH — the first resource for mathematics

On the eigenvalues of Cayley graphs on the symmetric group generated by a complete multipartite set of transpositions. (English) Zbl 1221.05196
Summary: Given a finite simple graph \(\mathcal G\) with \(n\) vertices, we can construct the Cayley graph on the symmetric group \(S _{n }\) generated by the edges of \(\mathcal G\), interpreted as transpositions. We show that, if \(\mathcal G\) is complete multipartite, the eigenvalues of the Laplacian of Cay \((\mathcal G)\) have a simple expression in terms of the irreducible characters of transpositions and of the Littlewood-Richardson coefficients. As a consequence, we can prove that the Laplacians of \(\mathcal G\) and of Cay \((\mathcal G)\) have the same first nontrivial eigenvalue. This is equivalent to saying that Aldous’s conjecture, asserting that the random walk and the interchange process have the same spectral gap, holds for complete multipartite graphs.

05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C81 Random walks on graphs
Full Text: DOI arXiv
[1] Aldous, D.: www.stat.berkeley.edu/ aldous/research/op/sgap.html
[2] Biggs, N.: Algebraic Graph Theory, 2nd edn. Cambridge Mathematical Library. Cambridge University Press, Cambridge (1993)
[3] Caputo, P., Liggett, T.M., Richthammer, T.: A recursive proof of Aldous’ spectral gap conjecture. arXiv:0906.1238v3 (2009) · Zbl 1203.60145
[4] Chung, F.R.K.: Spectral Graph Theory. CBMS Regional Conference Series in Mathematics, vol. 92. American Mathematical Society, Providence (1997) · Zbl 0867.05046
[5] Curtis, C.W., Reiner, I.: Representation Theory of Finite Groups and Associative Algebras. Pure and Applied Mathematics, vol. XI. Interscience Publishers, a division of John Wiley & Sons, New York (1962) · 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] Flatto, L.; Odlyzko, A. M.; Wales, D. B., Random shuffles and group representations, Ann. Probab., 13, 154-178, (1985) · Zbl 0564.60007
[8] Friedman, J., On Cayley graphs on the symmetric group generated by transpositions, Combinatorica, 20, 505-519, (2000) · Zbl 0996.05066
[9] Godsil, C., Royle, G.: Algebraic Graph Theory. Graduate Texts in Mathematics, vol. 207. Springer, New York (2001) · Zbl 0968.05002
[10] Handjani, S.; Jungreis, D., Rate of convergence for shuffling cards by transpositions, J. Theor. Probab., 9, 983-993, (1996) · Zbl 0878.60043
[11] Ingram, R. E., Some characters of the symmetric group, Proc. Am. Math. Soc., 1, 358-369, (1950) · Zbl 0054.01103
[12] James, G., Kerber, A.: The Representation Theory of the Symmetric Group. Encyclopedia of Mathematics and its Applications, vol. 16. Addison-Wesley, Reading (1981) · Zbl 0491.20010
[13] Koma, T.; Nachtergaele, B., The spectral gap of the ferromagnetic XXZ chain, Lett. Math. Phys., 40, 1-16, (1997) · Zbl 0880.60103
[14] Morris, B., Spectral gap for the interchange process in a box, Electron. Commun. Probab., 13, 311-318, (2008) · Zbl 1189.60180
[15] Sagan, B.E.: The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions, 2nd edn. Graduate Texts in Mathematics, vol. 203. Springer, New York (2001) · Zbl 0964.05070
[16] Starr, S., Conomos, M.: Asymptotics of the spectral gap for the interchange process on large hypercubes. arXiv:0802.1368v2 (2008)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.