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