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

Source 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 an application we obtain tighter bounds on conditions for the existence of Latin transversal matrices.