## 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?!)