Proof of Aldous’ spectral gap conjecture
HTML articles powered by AMS MathViewer
- by Pietro Caputo, Thomas M. Liggett and Thomas Richthammer
- J. Amer. Math. Soc. 23 (2010), 831-851
- DOI: https://doi.org/10.1090/S0894-0347-10-00659-4
- Published electronically: January 26, 2010
- PDF | Request permission
Abstract:
Aldous’ spectral gap conjecture asserts that on any graph the random walk process and the random transposition (or interchange) process have the same spectral gap. We prove the conjecture using a recursive strategy. The approach is a natural extension of the method already used to prove the validity of the conjecture on trees. The novelty is an idea based on electric network reduction, which reduces the problem to the proof of an explicit inequality for a random transposition operator involving both positive and negative rates. The proof of the latter inequality uses suitable coset decompositions of the associated matrices with rows and columns indexed by permutations.References
- D. Aldous, www.stat.berkeley.edu/users/aldous/Research/OP/index.html.
- D. Aldous, J. Fill, Reversible Markov Chains and Random Walks on Graphs. Book in preparation, http://www.stat.berkeley.edu/˜aldous/RWG/book.html.
- P. Caputo, T.M. Liggett, T. Richthammer, A recursive approach for Aldous’ spectral gap conjecture, arXiv:0906.1238v1 (2009).
- F. Cesi, On the eigenvalues of Cayley graphs on the symmetric group generated by a complete multipartite set of transpositions, arXiv:0902.0727v1 (2009).
- F. Cesi, Cayley graphs on the symmetric group generated by initial reversals have unit spectral gap, Elec. J. Combin. 16, N29 (2009).
- Persi Diaconis and James Allen Fill, Strong stationary times via a new form of duality, Ann. Probab. 18 (1990), no. 4, 1483–1522. MR 1071805
- Persi Diaconis and Susan P. Holmes, Random walks on trees and matchings, Electron. J. Probab. 7 (2002), no. 6, 17. MR 1887626, DOI 10.1214/EJP.v7-105
- Persi Diaconis and Laurent Saloff-Coste, Comparison theorems for reversible Markov chains, Ann. Appl. Probab. 3 (1993), no. 3, 696–730. MR 1233621
- Persi Diaconis and Mehrdad Shahshahani, Generating a random permutation with random transpositions, Z. Wahrsch. Verw. Gebiete 57 (1981), no. 2, 159–179. MR 626813, DOI 10.1007/BF00535487
- A.B. Dieker, Interlacings for random walks on weighted graphs and the interchange process, arXiv:0906.1716v1 (2009), SIAM J. Discrete Math. (accepted).
- Peter G. Doyle and J. Laurie Snell, Random walks and electric networks, Carus Mathematical Monographs, vol. 22, Mathematical Association of America, Washington, DC, 1984. MR 920811, DOI 10.5948/UPO9781614440222
- L. Flatto, A. M. Odlyzko, and D. B. Wales, Random shuffles and group representations, Ann. Probab. 13 (1985), no. 1, 154–178. MR 770635, DOI 10.1214/aop/1176993073
- Shirin Handjani and Douglas Jungreis, Rate of convergence for shuffling cards by transpositions, J. Theoret. Probab. 9 (1996), no. 4, 983–993. MR 1419872, DOI 10.1007/BF02214260
- Gordon James and Adalbert Kerber, The representation theory of the symmetric group, Encyclopedia of Mathematics and its Applications, vol. 16, Addison-Wesley Publishing Co., Reading, Mass., 1981. With a foreword by P. M. Cohn; With an introduction by Gilbert de B. Robinson. MR 644144
- Tohru Koma and Bruno Nachtergaele, The spectral gap of the ferromagnetic $XXZ$ chain, Lett. Math. Phys. 40 (1997), no. 1, 1–16. MR 1445963, DOI 10.1023/A:1007351803403
- David A. Levin, Yuval Peres, and Elizabeth L. Wilmer, Markov chains and mixing times, American Mathematical Society, Providence, RI, 2009. With a chapter by James G. Propp and David B. Wilson. MR 2466937, DOI 10.1090/mbk/058
- R. Lyons, Y. Peres, Probability on Trees and Networks. Book in preparation, http://mypage.iu.edu/˜rdlyons/prbtree/prbtree.html.
- Ben Morris, Spectral gap for the interchange process in a box, Electron. Commun. Probab. 13 (2008), 311–318. MR 2415139, DOI 10.1214/ECP.v13-1381
- S. Starr, M. Conomos, Asymptotics of the spectral gap for the interchange process on large hypercubes, arXiv:0802.1368v2 (2008).
Bibliographic Information
- Pietro Caputo
- Affiliation: Dipartimento di Matematica, Università di Roma Tre, Italy and Department of Mathematics, University of California, Los Angeles, California 90095
- MR Author ID: 659765
- ORCID: 0000-0002-2871-2566
- Email: caputo@mat.uniroma3.it
- Thomas M. Liggett
- Affiliation: Department of Mathematics, University of California, Los Angeles, California 90095
- Email: tml@math.ucla.edu
- Thomas Richthammer
- Affiliation: Department of Mathematics, University of California, Los Angeles, California 90095
- Email: richthammer@math.ucla.edu
- Received by editor(s): June 26, 2009
- Published electronically: January 26, 2010
- Additional Notes: The first author was partially supported by the Advanced Research Grant “PTRELSS” ADG-228032 of the European Research Council. He thanks Filippo Cesi for helpful discussions
Partial support from NSF Grant DMS-0301795 is acknowledged - © Copyright 2010
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: J. Amer. Math. Soc. 23 (2010), 831-851
- MSC (2010): Primary 60K35, 60J27, 05C50
- DOI: https://doi.org/10.1090/S0894-0347-10-00659-4
- MathSciNet review: 2629990