The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma

Details The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma

2003-09-15

arxiv.org/abs/cond-mat/0309352v2

J. Stat. Phys. 118, 1151-1261 (2005)

Physics

Condensed Matter

Statistical Mechanics

LaTex2e, 97 pages. Version 2 makes slight changes to improve clarity. To be published in J. Stat. Phys

Scientific paper

We elucidate the close connection between the repulsive lattice gas in equilibrium statistical mechanics and the Lovasz local lemma in probabilistic combinatorics. We show that the conclusion of the Lovasz local lemma holds for dependency graph G and probabilities {p_x} if and only if the independent-set polynomial for G is nonvanishing in the polydisc of radii {p_x}. Furthermore, we show that the usual proof of the Lovasz local lemma -- which provides a sufficient condition for this to occur -- corresponds to a simple inductive argument for the nonvanishing of the independent-set polynomial in a polydisc, which was discovered implicitly by Shearer and explicitly by Dobrushin. We also present some refinements and extensions of both arguments, including a generalization of the Lovasz local lemma that allows for "soft" dependencies. In addition, we prove some general properties of the partition function of a repulsive lattice gas, most of which are consequences of the alternating-sign property for the Mayer coefficients. We conclude with a brief discussion of the repulsive lattice gas on countably infinite graphs.

Affiliated with

Also associated with

No associations

Rating

The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-511011