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.
History The statement was proven for the complete graph by Persi Diaconis and Mehrdad Shahshahani in 1981, and for star graphs by Leopold Flatto, Andrew Odlyzko, and David Wales in 1985. It was first formally stated as an open problem in a book in preparation by David Aldous and James Fill. For weighted trees, the statement was proven in 1996 by Shirin Handjani and Douglas Jungreis. For boxes in Z d {\displaystyle \mathbb {Z} ^{d}} , the statement was independently proven by Morris and by Conomos and Starr in 2008. The full connector was proven in 2009.
References