# 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.

##### MSC:
 05C25 Graphs and abstract algebra (groups, rings, fields, etc.) 05C50 Graphs and linear algebra (matrices, eigenvalues, etc.) 05C81 Random walks on graphs
Full Text:
##### References:
  Aldous, D.: www.stat.berkeley.edu/ aldous/research/op/sgap.html  Biggs, N.: Algebraic Graph Theory, 2nd edn. Cambridge Mathematical Library. Cambridge University Press, Cambridge (1993)  Caputo, P., Liggett, T.M., Richthammer, T.: A recursive proof of Aldous’ spectral gap conjecture. arXiv:0906.1238v3 (2009) · Zbl 1203.60145  Chung, F.R.K.: Spectral Graph Theory. CBMS Regional Conference Series in Mathematics, vol. 92. American Mathematical Society, Providence (1997) · Zbl 0867.05046  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  Diaconis, P.; Shahshahani, M., Generating a random permutation with random transpositions, Z. Wahrscheinlichkeitstheor. Verw. Geb., 57, 159-179, (1981) · Zbl 0485.60006  Flatto, L.; Odlyzko, A. M.; Wales, D. B., Random shuffles and group representations, Ann. Probab., 13, 154-178, (1985) · Zbl 0564.60007  Friedman, J., On Cayley graphs on the symmetric group generated by transpositions, Combinatorica, 20, 505-519, (2000) · Zbl 0996.05066  Godsil, C., Royle, G.: Algebraic Graph Theory. Graduate Texts in Mathematics, vol. 207. Springer, New York (2001) · Zbl 0968.05002  Handjani, S.; Jungreis, D., Rate of convergence for shuffling cards by transpositions, J. Theor. Probab., 9, 983-993, (1996) · Zbl 0878.60043  Ingram, R. E., Some characters of the symmetric group, Proc. Am. Math. Soc., 1, 358-369, (1950) · Zbl 0054.01103  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  Koma, T.; Nachtergaele, B., The spectral gap of the ferromagnetic XXZ chain, Lett. Math. Phys., 40, 1-16, (1997) · Zbl 0880.60103  Morris, B., Spectral gap for the interchange process in a box, Electron. Commun. Probab., 13, 311-318, (2008) · Zbl 1189.60180  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  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.