Spectral independence, coupling with the stationary distribution, and the spectral gap of the Glauber dynamics
share
We present a new lower bound on the spectral gap of the Glauber dynamics for the Gibbs distribution of a spectrally independent q-spin system on a graph G = (V,E) with maximum degree Δ. Notably, for several interesting examples, our bound covers the entire regime of Δ excluded by arguments based on coupling with the stationary distribution. As concrete applications, by combining our new lower bound with known spectral independence computations and known coupling arguments: (1) We show that for a triangle-free graph G = (V,E) with maximum degree Δ≥ 3, the Glauber dynamics for the uniform distribution on proper k-colorings with k ≥ (1.763… + δ)Δ colors has spectral gap Ω̃_δ(|V|^-1). Previously, such a result was known either if the girth of G is at least 5 [Dyer et. al, FOCS 2004], or under restrictions on Δ [Chen et. al, STOC 2021; Hayes-Vigoda, FOCS 2003]. (2) We show that for a regular graph G = (V,E) with degree Δ≥ 3 and girth at least 6, and for any ε, δ > 0, the partition function of the hardcore model with fugacity λ≤ (1-δ)λ_c(Δ) may be approximated within a (1+ε)-multiplicative factor in time Õ_δ(n^2ε^-2). Previously, such a result was known if the girth is at least 7 [Efthymiou et. al, SICOMP 2019]. (3) We show for the binomial random graph G(n,d/n) with d = O(1), with high probability, an approximately uniformly random matching may be sampled in time O_d(n^2+o(1)). This improves the corresponding running time of Õ_d(n^3) due to [Jerrum-Sinclair, SICOMP 1989; Jerrum, 2003].
READ FULL TEXT