×

zbMATH — the first resource for mathematics

Proof of Aldous’ spectral gap conjecture. (English) Zbl 1203.60145
Two random processes are considered on an undirected graph with edge weights: the random walk process with the weights as jump rates and the random transposition (or interchange) process with the weights as transition rates. Aldous’ spectral gap conjecture asserts that both processes have the same spectral gap. The recursive strategy used to prove the conjecture is a natural extension of the method already used for 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 coset decompositions of the associated matrices with rows and columns indexed by permutations. In the last section the authors study the spectral gap of other stochastic processes associated to weighted graphs. Symmetric exclusion process, cycle process and matching process are successively considered.

MSC:
60K35 Interacting random processes; statistical mechanics type models; percolation theory
60J27 Continuous-time Markov processes on discrete state spaces
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[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/ãldous/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). · Zbl 1221.05196
[5] F. Cesi, Cayley graphs on the symmetric group generated by initial reversals have unit spectral gap, Elec. J. Combin. 16, N29 (2009). · Zbl 1185.05079
[6] Persi Diaconis and James Allen Fill, Strong stationary times via a new form of duality, Ann. Probab. 18 (1990), no. 4, 1483 – 1522. · Zbl 0723.60083
[7] Persi Diaconis and Susan P. Holmes, Random walks on trees and matchings, Electron. J. Probab. 7 (2002), no. 6, 17. · Zbl 1007.60071 · doi:10.1214/EJP.v7-105 · doi.org
[8] Persi Diaconis and Laurent Saloff-Coste, Comparison theorems for reversible Markov chains, Ann. Appl. Probab. 3 (1993), no. 3, 696 – 730. · Zbl 0799.60058
[9] Persi Diaconis and Mehrdad Shahshahani, Generating a random permutation with random transpositions, Z. Wahrsch. Verw. Gebiete 57 (1981), no. 2, 159 – 179. · Zbl 0485.60006 · doi:10.1007/BF00535487 · doi.org
[10] A.B. Dieker, Interlacings for random walks on weighted graphs and the interchange process, arXiv:0906.1716v1 (2009), SIAM J. Discrete Math. (accepted). · Zbl 1213.60125
[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. · Zbl 0583.60065
[12] L. Flatto, A. M. Odlyzko, and D. B. Wales, Random shuffles and group representations, Ann. Probab. 13 (1985), no. 1, 154 – 178. · Zbl 0564.60007
[13] Shirin Handjani and Douglas Jungreis, Rate of convergence for shuffling cards by transpositions, J. Theoret. Probab. 9 (1996), no. 4, 983 – 993. · Zbl 0878.60043 · doi:10.1007/BF02214260 · doi.org
[14] 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. · Zbl 0491.20010
[15] Tohru Koma and Bruno Nachtergaele, The spectral gap of the ferromagnetic \?\?\? chain, Lett. Math. Phys. 40 (1997), no. 1, 1 – 16. · Zbl 0880.60103 · doi:10.1023/A:1007351803403 · doi.org
[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. · Zbl 1160.60001
[17] R. Lyons, Y. Peres, Probability on Trees and Networks. Book in preparation, http://mypage.iu.edu/\~rdlyons/prbtree/prbtree.html. · Zbl 1376.05002
[18] Ben Morris, Spectral gap for the interchange process in a box, Electron. Commun. Probab. 13 (2008), 311 – 318. · Zbl 1189.60180 · doi:10.1214/ECP.v13-1381 · doi.org
[19] S. Starr, M. Conomos, 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.