Rapid Mixing of Hypergraph Independent Set

Abstract

We prove that the the mixing time of the Glauber dynamics for sampling independent sets on $n$-vertex $k$-uniform hypergraphs is $O(n\log n)$ when the maximum degree $\Delta$ satisfies $\Delta \le c{2}^{k/2}$, improving on the previous bound [BDK06] of $\Delta \le k-2$. This result brings the algorithmic bound to within a constant factor of the hardness bound of [BGG+16] which showed that it is NP-hard to approximately count independent sets on hypergraphs when $\Delta \ge 5\cdot 2^{k/2}$.

36 pages, 3 figures