Spectral Gap for the Interchange (Exclusion) Process on a Finite Graph

(6/17/09) A solution has been posted by Caputo-Liggett-Richthammer .

Consider a n-vertex graph G-- assume connected, undirected. Take n particles labeled 1,2,...,n. In a configuration, there is one particle at each vertex. The interchange process is the following continuous-time Markov chain on configurations. For each edge (i,j), at rate 1 the particles at vertex i and vertex j are interchanged.

The interchange process is reversible, and its stationary distribution is uniform on all n! configurations. There is a spectral gap $\lambda_{IP}(G) > 0$, which is the smallest non-zero eigenvalue of the transition rate matrix. If instead we just watch a single particle, it performs a continuous-time random walk on G, which is also reversible and hence has a spectral gap $\lambda_{RW}(G) > 0$. Simple arguments (the contraction principle) show $\lambda_{IP}(G) \leq \lambda_{RW}(G)$.

PROBLEM. Prove $\lambda_{IP}(G) = \lambda_{RW}(G)$ for all G.

Discussion. Fix m and color particles 1,2,...., m red. Then the red particles in the interchange process behave as the usual exclusion process. But in the finite setting, the interchange process seems more natural.

History. The problem arose around 1992 in conversation with Persi Diaconis and was stated explicitly in the 1994 version of Reversible Markov Chains and Random Walks on Graphs. It was sbsequently proved in various special cases, such as trees and complete multipartite graphs. The general case was not proved until 2009 by Caputo-Liggett-Richthammer who the conjecture to the proof of an explicit inequality for a random transposition operator involving both positive and negative rates, covering more special cases. See also Dieker and Alon - Kozma.

Instinct says that the same mathematical question will arise in some quite different setting (quantum epistemology?!)