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 $Delta$. Notably, for several interesting examples, our bound covers the entire regime of $Delta$ 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 $Delta geq 3$, the Glauber dynamics for the uniform distribution on proper $k$-colorings with $k geq (1.763dots + delta)Delta$ colors has spectral gap $tilde{Omega}_{delta}(|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 $Delta$ [Chen et.~al, STOC 2021; Hayes-Vigoda, FOCS 2003]. (2) We show that for a regular graph $G = (V,E)$ with degree $Delta geq 3$ and girth at least $6$, and for any $varepsilon, delta > 0$, the partition function of the hardcore model with fugacity $lambda leq (1-delta)lambda_{c}(Delta)$ may be approximated within a $(1+varepsilon)$-multiplicative factor in time $tilde{O}_{delta}(n^{2}varepsilon^{-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 $tilde{O}_{d}(n^{3})$ due to [Jerrum-Sinclair, SICOMP 1989; Jerrum, 2003].
تحميل البحث