An Improvement of the Lovász Local Lemma via Cluster Expansion

Details An Improvement of the Lovász Local Lemma via Cluster Expansion An Improvement of the Lovász Local Lemma via Cluster Expansion

2009-10-09

arxiv.org/abs/0910.1824v2

Mathematics

Combinatorics

In this new version the abstract has been extended, an introduction has been added and a new application on k-sat has been giv

Scientific paper

An old result by Shearer relates the Lov\'asz Local Lemma with the independent set polynomial on graphs, and consequently, as observed by Scott and Sokal, with the partition function of the hard core lattice gas on graphs. We use this connection and a recent result on the analyticity of the logarithm of the partition function of the abstract polymer gas to get an improved version of the Lov\'asz Local Lemma. As applications we obtain tighter bounds on conditions for the existence of latin transversal matrices and the satisfiability of k-SAT forms.

Affiliated with

Also associated with

No associations

Rating

An Improvement of the Lovász Local Lemma via Cluster Expansion 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 An Improvement of the Lovász Local Lemma via Cluster Expansion, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Improvement of the Lovász Local Lemma via Cluster Expansion will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-52060