Improved mixing condition on the grid for counting and sampling independent sets

Abstract

ABSTRACT: The hard-core model has received much attention in the past couple of decades as a lattice gas model with hard constraints in statistical physics, a multicast model of calls in communication networks, and as a weighted independent set problem in combinatorics, probability and theoretical computer science. In this model, each independent set I in a graph G is weighted proportionally to λ|I|, for a positive real parameter λ. For large λ, computing the partition function (namely, the normalizing constant which makes the weighting a probability distribution on a finite graph) on graphs of maximum degree ≥ 3, is a well known computationally challenging problem. More concretely, let λc(T) denote the critical value for the so-called uniqueness