Aldous' spectral gap conjecture

In probability theory, Aldous' spectral gap conjecture is the statement that two Markov chains associated to a graph, namely the random walk and the interchange process, have the same spectral gap. The conjecture was proven in 2009 by Caputo, Liggett, and Richthammer.[1]

History

The statement was proven for the complete graph by Persi Diaconis and Mehrdad Shahshahani in 1981,[2] and for star graphs by Leopold Flatto, Andrew Odlyzko, and David Wales in 1985.[3] It was first formally stated as an open problem in a book in preparation by David Aldous and James Fill.[4]

For weighted trees, the statement was proven in 1996 by Shirin Handjani and Douglas Jungreis.[5] For boxes in , the statement was independently proven by Morris and by Conomos and Starr in 2008.[6][7] The full connector was proven in 2009.[1]

References

  1. 1 2 Caputo, Pietro; Liggett, Thomas; Richthammer, Thomas (2010-01-26). "Proof of Aldous' spectral gap conjecture". Journal of the American Mathematical Society. 23 (3): 831–851. arXiv:0906.1238. doi:10.1090/S0894-0347-10-00659-4. ISSN 0894-0347.
  2. ↑ Diaconis, Persi; Shahshahani, Mehrdad (1981). "Generating a random permutation with random transpositions". Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete. 57 (2): 159–179. doi:10.1007/BF00535487. ISSN 0044-3719.
  3. ↑ Flatto, L.; Odlyzko, A. M.; Wales, D. B. (1985-02-01). "Random Shuffles and Group Representations". The Annals of Probability. 13 (1). doi:10.1214/aop/1176993073. ISSN 0091-1798.
  4. ↑ "Aldous-Fill book". Sitemap for www.stat.berkeley.edu. 1999-07-20.
  5. ↑ Handjani, Shirin; Jungreis, Douglas (1996). "Rate of convergence for shuffling cards by transpositions". Journal of Theoretical Probability. 9 (4): 983–993. doi:10.1007/BF02214260. ISSN 0894-9840.
  6. ↑ Morris, Ben (2008-01-01). "Spectral gap for the interchange process in a box". Electronic Communications in Probability. 13 (none). doi:10.1214/ECP.v13-1381. ISSN 1083-589X.
  7. ↑ Starr, Shannon; Conomos, Matthew P (2011-10-20). "Asymptotics of the spectral gap for the interchange process on large hypercubes". Journal of Statistical Mechanics: Theory and Experiment. 2011 (10). IOP Publishing. arXiv:0802.1368. doi:10.1088/1742-5468/2011/10/p10018. ISSN 1742-5468.
This page is issued from Wikipedia. The text is available under Creative Commons Attribution-Share Alike 4.0 unless otherwise noted. Additional terms may apply for the media files.