Spatial mixing and the connective constant: Optimal bounds

Understand

We study the problem of deterministic approximate counting of matchings and independent sets in graphs of bounded connective constant.

• More generally, we consider the problem of evaluating the partition functions of the monomer-dimer model (which is defined as a weighted sum over all matchings where each matching is given a weight $\gamma^{|V| - 2 |M|}$ in terms of a fixed parameter gamma called the monomer activity) and the hard core model (which is defined as a weighted sum over all independent sets where an independent set I is given a weight $\lambda^{|I|}$ in terms of a fixed parameter lambda called the vertex activity).
• The connective constant is a natural measure of the average degree of a graph which has been studied extensively in combinatorics and mathematical physics, and can be bounded by a constant even for certain unbounded degree graphs such as those sampled from the sparse Erd\H{o}s-R\'enyi model $G(n, d/n)$.
• Our main technical contribution is to prove the best possible rates of decay of correlations in the natural probability distributions induced by both the hard core model and the monomer-dimer model in graphs with a given bound on the connective constant.