0 0 4 views

**Unformatted text preview: **

A Proof of Aldous Spectral Gap Conjecture Thomas M Liggett UCLA Stirring Processes Given a graph G V E associate with each edge e E a Poisson process e with rate ce 0 Labels are put on the vertices v V At the event times of e interchange the contents of the two vertices joined by e Depending on the nature of the labels one can define various continuous time Markov chains One particle MC Symmetric exclusion MC on permutations Let Q be the rate matrix for a symmetric irreducible n state Markov chain i e q x y q y x is the exponential rate at which the chain goes from state x to state y pt x y q x y t o t t 0 for x 6 y Then Q has eigenvalues 0 0 1 2 n 1 The smallest positive eigenvalue 1 determines the rate of convergence to equilibrium pt x y 1 a x y e 1 t o e 1 t n t It is the largest value of for which X 1X g x 2 q x y g y g x 2 2 x y x X x g x 0 Consider the stirring process on the complete graph G with n vertices The one particle Markov chain has q x y cxy The Markov chain on permutations has q xy cxy where xy is the permutation obtained from by applying the transposition that interchanges x and y Let 0 0 1 2 n 1 be the eigenvalues for the one particle Markov chain and 0 0 1 2 n 1 be the eigenvalues for the Markov chain on permutations Note Each i some j so 1 1 In fact any sum of the form i1 ik is an eigenvalue of the permutation chain There are 4n 1 n eigenvalues of this type and all are 1 How about the others Aldous Conjecture 1992 1 1 Why guess this 1 True for ce 1 on complete graph Diaconis and Shahshahani 1981 2 True for ce 1 on star graphs Flatto Odlyzko and Wales 1985 3 True for general ce on trees Handjani and Jungreis 1996 4 True for ce 1 on complete multipartite graphs Cesi 2009 5 Other related results by Koma and Nachtergele 1997 Morris 2008 Starr and Conomos 2008 and Dieker 2009 Theorem On a general finite graph with arbitrary rates 1 1 Joint with P Caputo Rome and T Richthammer UCLA Why should you care 1 It is MUCH easier to compute eigenvalues for an