Improved Mixing of Critical Hardcore Model

Abstract

The hardcore model is one of the most classic and widely studied examples of undirected graphical models. Given a graph $G$, the hardcore model describes a Gibbs distribution of $\hat{I}»$-weighted independent sets of $G$. In the last two decades, a beautiful computational phase transition has been established at a precise threshold $\hat{I}{»}_c(\hat{I}”)$ where $\hat{I}”$ denotes the maximum degree, where the task of sampling independent sets transitions from polynomial-time solvable to computationally intractable. We study the critical hardcore model where $\hat{I}»=\hat{I}{»}_c(\hat{I}”)$ and show that the Glauber dynamics, a simple yet popular Markov chain algorithm, mixes in $\tilde{O}(n^{4+O(1/\hat{I}”)})$ time on any $n$-vertex graph of maximum degree $\hat{I}”\ge 3$, significantly improving the previous upper bound $\tilde{O}(n^{12.88+O(1/\hat{I}”)})$ by the recent work arXiv:2411.03413. Our improvement comes from an optimal bound on the ${\ell }_{\infty }$-spectral independence for the hardcore model at all subcritical fugacity $\hat{I}»<\hat{I}{»}_c(\hat{I}”)$.

16 pages, addressed an error in the previous version involving ${\ell }_{\infty }$-spectral independence; see Remark 1.2 for details