Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion

We prove an optimal mixing time bound for 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 α ≈ 1.763, and O(m log n) mixing for generating random matchings of any graph with bounded degree and m edges. Our approach is based on two steps. First, we show that the approximate tensorization of entropy (i.e., factorizing entropy into single vertices), which is a key step for establishing the modified log-Sobolev inequality in many previous works, can be deduced from entropy factorization into blocks of fixed linear size. Second, we adapt the local-to-global scheme of Alev and Lau (2020) to establish such block factorization of entropy in a more general setting of pure weighted simplicial complexes satisfying local spectral expansion; this also substantially generalizes the result of Cryan et al. (2019) .