Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion

We prove an optimal mixing time bound on the single-site update Markov chain known as the Glauber dynamics or Gibbs sampling in a variety of settings. Our work presents an improved version of the spectral independence approach of Anari et al. (2020) and shows $O(n\log{n})$ mixing time on any $n$-vertex graph of bounded degree when the maximum eigenvalue of an associated influence matrix is bounded. As an application of our results, for the hard-core model on independent sets weighted by a fugacity $λ$, we establish $O(n\log{n})$ mixing time for the Glauber dynamics on any $n$-vertex graph of constant maximum degree $Δ$ when $λ<λ_c(Δ)$ where $λ_c(Δ)$ is the critical point for the uniqueness/non-uniqueness phase transition on the $Δ$-regular tree. More generally, for any antiferromagnetic 2-spin system we prove $O(n\log{n})$ mixing time of the Glauber dynamics on any bounded degree graph in the corresponding tree uniqueness region. Our results apply more broadly; for example, we also obtain $O(n\log{n})$ mixing for $q$-colorings of triangle-free graphs of maximum degree $Δ$ when the number of colors satisfies $q > αΔ$ where $α\approx 1.763$, and $O(m\log{n})$ mixing for generating random matchings of any graph with bounded degree and $m$ edges.