On the eigenvalues of Cayley graphs on the symmetric group generated by a complete multipartite set of transpositions
Filippo Cesi
DOI: 10.1007/s10801-009-0208-x
Abstract
Given a finite simple graph G with n vertices, we can construct the Cayley graph on the symmetric group S n generated by the edges of G, interpreted as transpositions. We show that, if G is complete multipartite, the eigenvalues of the Laplacian of Cay\thinspace ( 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 G and of Cay\thinspace ( 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.
Pages: 155–185
Keywords: Cayley graphs; Laplacian; symmetric group; Littlewood-Richardson rule; spectral gap; interchange process
Full Text: PDF
References
1. Aldous, D.:
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. (2009)
4. Chung, F.R.K.: Spectral Graph Theory. CBMS Regional Conference Series in Mathematics, vol.
92. American Mathematical Society, Providence (1997)
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)
6. Diaconis, P., Shahshahani, M.: Generating a random permutation with random transpositions. Z. Wahrscheinlichkeitstheor. Verw. Geb. 57(2), 159-179 (1981)
7. Flatto, L., Odlyzko, A.M., Wales, D.B.: Random shuffles and group representations. Ann. Probab. 13(1), 154-178 (1985)
8. Friedman, J.: On Cayley graphs on the symmetric group generated by transpositions. Combinatorica 20(4), 505-519 (2000)
9. Godsil, C., Royle, G.: Algebraic Graph Theory. Graduate Texts in Mathematics, vol.
207. Springer, New York (2001)
10. Handjani, S., Jungreis, D.: Rate of convergence for shuffling cards by transpositions. J. Theor. Probab. 9(4), 983-993 (1996)
11. Ingram, R.E.: Some characters of the symmetric group. Proc. Am. Math. Soc. 1, 358-369 (1950)
12. James, G., Kerber, A.: The Representation Theory of the Symmetric Group. Encyclopedia of Mathematics and its Applications, vol.
16. Addison-Wesley, Reading (1981)
13. Koma, T., Nachtergaele, B.: The spectral gap of the ferromagnetic XXZ chain. Lett. Math. Phys.
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. (2009)
4. Chung, F.R.K.: Spectral Graph Theory. CBMS Regional Conference Series in Mathematics, vol.
92. American Mathematical Society, Providence (1997)
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)
6. Diaconis, P., Shahshahani, M.: Generating a random permutation with random transpositions. Z. Wahrscheinlichkeitstheor. Verw. Geb. 57(2), 159-179 (1981)
7. Flatto, L., Odlyzko, A.M., Wales, D.B.: Random shuffles and group representations. Ann. Probab. 13(1), 154-178 (1985)
8. Friedman, J.: On Cayley graphs on the symmetric group generated by transpositions. Combinatorica 20(4), 505-519 (2000)
9. Godsil, C., Royle, G.: Algebraic Graph Theory. Graduate Texts in Mathematics, vol.
207. Springer, New York (2001)
10. Handjani, S., Jungreis, D.: Rate of convergence for shuffling cards by transpositions. J. Theor. Probab. 9(4), 983-993 (1996)
11. Ingram, R.E.: Some characters of the symmetric group. Proc. Am. Math. Soc. 1, 358-369 (1950)
12. James, G., Kerber, A.: The Representation Theory of the Symmetric Group. Encyclopedia of Mathematics and its Applications, vol.
16. Addison-Wesley, Reading (1981)
13. Koma, T., Nachtergaele, B.: The spectral gap of the ferromagnetic XXZ chain. Lett. Math. Phys.
© 1992–2009 Journal of Algebraic Combinatorics
©
2012 FIZ Karlsruhe /
Zentralblatt MATH for the EMIS Electronic Edition