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

Abstract

An old result by Shearer relates the Lovász 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ász Local Lemma. As applications we obtain tighter bounds on conditions for the existence of latin transversal matrices and the satisfiability of k-SAT forms.

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

References in corpus (1)

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

Cited by in corpus (8)

• The Local Cut Lemma
• New Bounds for the Acyclic Chromatic Index
• Improved bounds on coloring of graphs
• Entropy Compression Method and Legitimate Colorings in Projective Planes
• The Local Action Lemma
• Fundamentals of Partial Rejection Sampling
• Short proofs for generalizations of the Lovász Local Lemma: Shearer's condition and cluster expansion
• Properly coloured copies and rainbow copies of large graphs with small maximum degree