Proof of Aldous' spectral gap conjecture
By Pietro Caputo, Thomas M. Liggett, Thomas Richthammer. 2009
141 citations recorded by the source corpus.
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 on permutations.
Subfields: Geometry and Topology, Statistics and Probability
View Paper: https://www.semanticscholar.org/paper/8f1497a3cb5d62c78eebf80171041a504f9b97bb
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Geometry and Topology
- Yuval Peres
- Russell Lyons
- Pablo Shmerkin
- Manjunath Krishnapur
- Michael Hochman
- Assaf Naor
- De-Jun Feng
- Jérémie Brieussel
In Statistics and Probability
- Russell Lyons
- Yuval Peres
- Cyril Labbé
- Alexei Borodin
- Charles Bordenave
- Manjunath Krishnapur
- Pietro Caputo
- Subhro Ghosh
Citations in the corpus
- Probability on Trees and Networks (2017, methodology): “A probabilistic proof of the Varopoulos-Carne bound, Theorem 13.4, was given by Peyre (2008). The application of this bound to mixing time was prompted by discussions with Itai Benjamini, James Lee, and Manor Mendel.”
- Cutoff phenomenon for the asymmetric simple exclusion process and the biased card shuffling (2016, result): “tion rates p and q on the segment (and this will also be the case for the ASEP). This result is reminiscent of Aldous’ spectral gap conjecture, now a theorem proved by Caputo, Liggett and Richthammer [9], which states that the spectral gap for the interchange process on an arbitrary graph equals tha”