Computer Science/Discrete Mathematics Seminar I

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.