Proof of Aldous' spectral gap conjecture
Authors:
Pietro Caputo, Thomas M. Liggett and Thomas Richthammer
Journal:
J. Amer. Math. Soc. 23 (2010), 831851
MSC (2010):
Primary 60K35, 60J27, 05C50
Published electronically:
January 26, 2010
MathSciNet review:
2629990
Fulltext PDF
Abstract 
References 
Similar Articles 
Additional Information
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.
 1.
D. Aldous, www.stat.berkeley.edu/users/aldous/Research/OP/index.html.
 2.
D. Aldous, J. Fill, Reversible Markov Chains and Random Walks on Graphs. Book in preparation, http://www.stat.berkeley.edu/˜aldous/RWG/book.html.
 3.
P. Caputo, T.M. Liggett, T. Richthammer, A recursive approach for Aldous' spectral gap conjecture, arXiv:0906.1238v1 (2009).
 4.
F. Cesi, On the eigenvalues of Cayley graphs on the symmetric group generated by a complete multipartite set of transpositions, arXiv:0902.0727v1 (2009).
 5.
F. Cesi, Cayley graphs on the symmetric group generated by initial reversals have unit spectral gap, Elec. J. Combin. 16, N29 (2009).
 6.
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
(91m:60127)
 7.
Persi
Diaconis and Susan
P. Holmes, Random walks on trees and matchings, Electron. J.
Probab. 7 (2002), no. 6, 17. MR 1887626
(2002k:60025), 10.1214/EJP.v7105
 8.
Persi
Diaconis and Laurent
SaloffCoste, Comparison theorems for reversible Markov
chains, Ann. Appl. Probab. 3 (1993), no. 3,
696–730. MR 1233621
(94i:60074)
 9.
Persi
Diaconis and Mehrdad
Shahshahani, Generating a random permutation with random
transpositions, Z. Wahrsch. Verw. Gebiete 57 (1981),
no. 2, 159–179. MR 626813
(82h:60024), 10.1007/BF00535487
 10.
A.B. Dieker, Interlacings for random walks on weighted graphs and the interchange process, arXiv:0906.1716v1 (2009), SIAM J. Discrete Math. (accepted).
 11.
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
(89a:94023)
 12.
L.
Flatto, A.
M. Odlyzko, and D.
B. Wales, Random shuffles and group representations, Ann.
Probab. 13 (1985), no. 1, 154–178. MR 770635
(86i:60178)
 13.
Shirin
Handjani and Douglas
Jungreis, Rate of convergence for shuffling cards by
transpositions, J. Theoret. Probab. 9 (1996),
no. 4, 983–993. MR 1419872
(98a:60095), 10.1007/BF02214260
 14.
Gordon
James and Adalbert
Kerber, The representation theory of the symmetric group,
Encyclopedia of Mathematics and its Applications, vol. 16,
AddisonWesley Publishing Co., Reading, Mass., 1981. With a foreword by P.
M. Cohn; With an introduction by Gilbert de B. Robinson. MR 644144
(83k:20003)
 15.
Tohru
Koma and Bruno
Nachtergaele, The spectral gap of the ferromagnetic
𝑋𝑋𝑍 chain, Lett. Math. Phys.
40 (1997), no. 1, 1–16. MR 1445963
(98m:82015), 10.1023/A:1007351803403
 16.
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
(2010c:60209)
 17.
R. Lyons, Y. Peres, Probability on Trees and Networks. Book in preparation, http://mypage.iu.edu/˜rdlyons/prbtree/prbtree.html.
 18.
Ben
Morris, Spectral gap for the interchange process in a box,
Electron. Commun. Probab. 13 (2008), 311–318. MR 2415139
(2009g:60103), 10.1214/ECP.v131381
 19.
S. Starr, M. Conomos, Asymptotics of the spectral gap for the interchange process on large hypercubes, arXiv:0802.1368v2 (2008).
 1.
 D. Aldous, www.stat.berkeley.edu/users/aldous/Research/OP/index.html.
 2.
 D. Aldous, J. Fill, Reversible Markov Chains and Random Walks on Graphs. Book in preparation, http://www.stat.berkeley.edu/˜aldous/RWG/book.html.
 3.
 P. Caputo, T.M. Liggett, T. Richthammer, A recursive approach for Aldous' spectral gap conjecture, arXiv:0906.1238v1 (2009).
 4.
 F. Cesi, On the eigenvalues of Cayley graphs on the symmetric group generated by a complete multipartite set of transpositions, arXiv:0902.0727v1 (2009).
 5.
 F. Cesi, Cayley graphs on the symmetric group generated by initial reversals have unit spectral gap, Elec. J. Combin. 16, N29 (2009).
 6.
 P. Diaconis, J. Fill, Strong stationary times via a new form of duality, Ann. Probab. 18, 14831522 (1990). MR 1071805 (91m:60127)
 7.
 P. Diaconis, S. Holmes, Random walks on trees and matchings, Electron. J. Probab. 7, 117 (2002). MR 1887626 (2002k:60025)
 8.
 P. Diaconis, L. SaloffCoste, Comparison theorems for reversible Markov chains, Ann. Appl. Probab. 3, 696730 (1993). MR 1233621 (94i:60074)
 9.
 P. Diaconis, M. Shahshahani, Generating a random permutation with random transpositions, Z. Wahrsch. Verw. Gebiete 57 (2), 159179 (1981). MR 626813 (82h:60024)
 10.
 A.B. Dieker, Interlacings for random walks on weighted graphs and the interchange process, arXiv:0906.1716v1 (2009), SIAM J. Discrete Math. (accepted).
 11.
 P. Doyle, J. Snell, Random walks and electric networks. Carus Mathematical Monographs, 22. Mathematical Association of America, Washington, DC, 1984. MR 920811 (89a:94023)
 12.
 L. Flatto, A.M. Odlyzko, D.B. Wales, Random shuffles and group representations, Ann. Probab. 13 (1), 154178 (1985). MR 770635 (86i:60178)
 13.
 S. Handjani, D. Jungreis, Rate of convergence for shuffling cards by transpositions, J. Theoret. Probab. 9 (4), 983993 (1996). MR 1419872 (98a:60095)
 14.
 G. James, A. Kerber, The representation theory of the symmetric group. Encyclopedia of Mathematics and its Applications, vol. 16. AddisonWesley Publishing Co., Reading, Mass. (1981). MR 644144 (83k:20003)
 15.
 T. Koma, B. Nachtergaele, The spectral gap of the ferromagnetic XXZ chain, Lett. Math. Phys. 40(1), 116 (1997). MR 1445963 (98m:82015)
 16.
 D. Levin, Y. Peres, E. Wilmer, Markov Chains and Mixing Times. AMS Bookstore (2008). MR 2466937
 17.
 R. Lyons, Y. Peres, Probability on Trees and Networks. Book in preparation, http://mypage.iu.edu/˜rdlyons/prbtree/prbtree.html.
 18.
 B. Morris, Spectral gap for the interchange process in a box, Electron. Commun. Probab. 13, 311318 (2008). MR 2415139 (2009g:60103)
 19.
 S. Starr, M. Conomos, Asymptotics of the spectral gap for the interchange process on large hypercubes, arXiv:0802.1368v2 (2008).
Similar Articles
Retrieve articles in Journal of the American Mathematical Society
with MSC (2010):
60K35,
60J27,
05C50
Retrieve articles in all journals
with MSC (2010):
60K35,
60J27,
05C50
Additional Information
Pietro Caputo
Affiliation:
Dipartimento di Matematica, Università di Roma Tre, Italy and Department of Mathematics, University of California, Los Angeles, California 90095
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
DOI:
http://dx.doi.org/10.1090/S0894034710006594
Keywords:
Random walk,
weighted graph,
spectral gap,
interchange process,
symmetric exclusion process
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” ADG228032 of the European Research Council. He thanks Filippo Cesi for helpful discussions
Partial support from NSF Grant DMS0301795 is acknowledged
Article copyright:
© Copyright 2010
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.
