On sampling two spin models using the local connective constant

This work establishes novel optimum mixing bounds for the Glauber dynamics on the Hard-core and Ising models. These bounds are expressed in terms of the local connective constant of the underlying graph G. This is a notion of effective degree for G.

Our results have some interesting consequences for bounded degree graphs: (a) They include the max-degree bounds as a special case (b) They improve on the running time of the FPTAS considered in [Sinclair, Srivastava, Štefankonič and Yin:

PTRF 2017] for general graphs (c) They allow us to obtain mixing bounds in terms of the spectral radius of the adjacency matrix and improve on [Hayes: FOCS 2006]. We obtain our results using tools from the theory of high-dimensional expanders and, in particular, the Spectral Independence method [Anari, Liu, Oveis-Gharan: FOCS 2020]. We explore a new direction by utilising the notion of the k-non-backtracking matrix H G,k in our analysis with the Spectral Independence. The results with H G,k are interesting in their own right.