Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Journal of the American Mathematical Society
Journal of the American Mathematical Society
ISSN 1088-6834(online) ISSN 0894-0347(print)

 

Proof of Aldous' spectral gap conjecture


Authors: Pietro Caputo, Thomas M. Liggett and Thomas Richthammer
Journal: J. Amer. Math. Soc. 23 (2010), 831-851
MSC (2010): Primary 60K35, 60J27, 05C50
Published electronically: January 26, 2010
MathSciNet review: 2629990
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: 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.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2010): 60K35, 60J27, 05C50

Retrieve articles in all journals with MSC (2010): 60K35, 60J27, 05C50


Additional Information

Pietro Caputo
Affiliation: Dipartimento di Matematica, Università di Roma Tre, Italy and Department of Mathematics, University of California, Los Angeles, California 90095
Email: caputo@mat.uniroma3.it

Thomas M. Liggett
Affiliation: Department of Mathematics, University of California, Los Angeles, California 90095
Email: tml@math.ucla.edu

Thomas Richthammer
Affiliation: Department of Mathematics, University of California, Los Angeles, California 90095
Email: richthammer@math.ucla.edu

DOI: http://dx.doi.org/10.1090/S0894-0347-10-00659-4
PII: S 0894-0347(10)00659-4
Keywords: Random walk, weighted graph, spectral gap, interchange process, symmetric exclusion process
Received by editor(s): June 26, 2009
Published electronically: January 26, 2010
Additional Notes: The first author was partially supported by the Advanced Research Grant “PTRELSS” ADG-228032 of the European Research Council. He thanks Filippo Cesi for helpful discussions
Partial support from NSF Grant DMS-0301795 is acknowledged
Article copyright: © Copyright 2010 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.