Mixing time for exclusion and interchange processes on hypergraphs

Stephen B. Connor, Richard Pymar

Published 2016-06-08Version 1

We introduce a natural extension of the exclusion process to hypergraphs and prove an upper bound for its mixing time. In particular we show the existence of a constant $C$ such that for any connected hypergraph $G$ within some class (which includes regular hypergraphs), the $\varepsilon$-mixing time of the exclusion process on $G$ with any feasible number of particles can be upper-bounded by $CT_{\text{EX}(2,G)}\log(|V|/\varepsilon)$, where $|V|$ is the number of vertices in $G$ and $T_{\text{EX}(2,G)}$ is the 1/4-mixing time of the corresponding exclusion process with two particles. We also obtain a similar result for the interchange process provided the number of particles is at most $|V|/2$. The proofs involve an adaptation of the chameleon process, a technical tool invented by Morris and developed by Oliveira for studying the exclusion process on a graph.