Improved Mixing of Critical Hardcore Model

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 -weighted independent sets of G. In the last two decades, a beautiful computational phase transition has been established at a precise threshold c () where denotes the maximum degree, where the task of sampling independent sets transfers from polynomial-time solvable to computationally intractable. We study the critical hardcore model where = c () and show that the Glauber dynamics, a simple yet popular Markov chain algorithm, mixes in O (n^7. 44 + O (1/) ) time on any n-vertex graph of maximum degree 3, significantly improving the previous upper bound O (n^12. 88+O (1/) ) by the recent work arXiv: 2411. 03413. The core property we establish in this work is that the critical hardcore model is O (n) -spectrally independent, improving the trivial bound of n and matching the critical behavior of the Ising model. Our proof approach utilizes an online decision-making framework to study a site percolation model on the infinite (-1) -ary tree, which can be interesting by itself.