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 Õ(n7.44 + O(1/Δ)) time on any n-vertex graph of maximum degree Δ≥3, significantly improving the previous upper bound Õ(n12.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.