Abstract:

We present a novel tree representation for the hard-core lattice
gas model (weighted independent sets) on a general graph.
We use this representation to show that for any graph of
maximum degree D, the Gibbs measure is unique (the
influence of any boundary condition decays with distance)
provided that the activity parameter \lambda < \lambda_c,
where \lambda_c is the critical activity for the regular tree of
degree D. This resolves an open conjecture in statistical physics.
Also, since \lambda_c is known, this extends the known
uniqueness regime for many interesting graphs, including the
square integer lattice Z^2.  Our proof is algorithmic in nature,
consisting of an elegant recursive procedure for calculating the
probabilities that a given vertex is occupied. This procedure
yields an efficient deterministic approximation scheme for
counting independent sets of any graph of maximum degree D
in the above regime of \lambda.  This extends the regime
of \lambda for which an efficient approximation scheme is
known to exist, and includes the interesting case of \lambda=1
(all independent sets are equally weighted) and maximum
degree D=5.