Geodesic
Proof of Aldous’ spectral gap conjecture
Caputo, Pietro1 ; Liggett, Thomas2 ; Richthammer, Thomas2
1 Dipartimento di Matematica, Università di Roma Tre, Italy and Department of Mathematics, University of California, Los Angeles, California 90095
2 Department of Mathematics, University of California, Los Angeles, California 90095
Journal of the American Mathematical Society, Tome 23 (2010) no. 3, pp. 831-851

Voir la notice de l'article provenant de la source American Mathematical Society

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.
DOI : 10.1090/S0894-0347-10-00659-4

Caputo, Pietro 1 ; Liggett, Thomas 2 ; Richthammer, Thomas 2

1 Dipartimento di Matematica, Università di Roma Tre, Italy and Department of Mathematics, University of California, Los Angeles, California 90095
2 Department of Mathematics, University of California, Los Angeles, California 90095 
@article{10_1090_S0894_0347_10_00659_4,
     author = {Caputo, Pietro and Liggett, Thomas and Richthammer, Thomas},
     title = {Proof of {Aldous\^a€™} spectral gap conjecture},
     journal = {Journal of the American Mathematical Society},
     pages = {831--851},
     publisher = {mathdoc},
     volume = {23},
     number = {3},
     year = {2010},
     doi = {10.1090/S0894-0347-10-00659-4},
     url = {http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-10-00659-4/}
}
TY  - JOUR
AU  - Caputo, Pietro
AU  - Liggett, Thomas
AU  - Richthammer, Thomas
TI  - Proof of Aldous’ spectral gap conjecture
JO  - Journal of the American Mathematical Society
PY  - 2010
SP  - 831
EP  - 851
VL  - 23
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-10-00659-4/
DO  - 10.1090/S0894-0347-10-00659-4
ID  - 10_1090_S0894_0347_10_00659_4
ER  - 
%0 Journal Article
%A Caputo, Pietro
%A Liggett, Thomas
%A Richthammer, Thomas
%T Proof of Aldous’ spectral gap conjecture
%J Journal of the American Mathematical Society
%D 2010
%P 831-851
%V 23
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-10-00659-4/
%R 10.1090/S0894-0347-10-00659-4
%F 10_1090_S0894_0347_10_00659_4
Caputo, Pietro; Liggett, Thomas; Richthammer, Thomas. Proof of Aldous’ spectral gap conjecture. Journal of the American Mathematical Society, Tome 23 (2010) no. 3, pp. 831-851. doi: 10.1090/S0894-0347-10-00659-4

[1] Diaconis, Persi, Fill, James Allen Strong stationary times via a new form of duality Ann. Probab. 1990 1483 1522

[2] Diaconis, Persi, Holmes, Susan P. Random walks on trees and matchings Electron. J. Probab. 2002

[3] Diaconis, Persi, Saloff-Coste, Laurent Comparison theorems for reversible Markov chains Ann. Appl. Probab. 1993 696 730

[4] Diaconis, Persi, Shahshahani, Mehrdad Generating a random permutation with random transpositions Z. Wahrsch. Verw. Gebiete 1981 159 179

[5] Doyle, Peter G., Snell, J. Laurie Random walks and electric networks 1984

[6] Flatto, L., Odlyzko, A. M., Wales, D. B. Random shuffles and group representations Ann. Probab. 1985 154 178

[7] Handjani, Shirin, Jungreis, Douglas Rate of convergence for shuffling cards by transpositions J. Theoret. Probab. 1996 983 993

[8] James, Gordon, Kerber, Adalbert The representation theory of the symmetric group 1981

[9] Koma, Tohru, Nachtergaele, Bruno The spectral gap of the ferromagnetic 𝑋𝑋𝑍 chain Lett. Math. Phys. 1997 1 16

[10] Levin, David A., Peres, Yuval, Wilmer, Elizabeth L. Markov chains and mixing times 2009

[11] Morris, Ben Spectral gap for the interchange process in a box Electron. Commun. Probab. 2008 311 318

Cité par Sources :