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

R. Bissacot; R. Fernandez; A. Procacci; B. Scoppola

doi:10.1017/S0963548311000253

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

R. Bissacot
, R. Fernandez
, A. Procacci
, B. Scoppola

extern

Research output: Contribution to journal › Article › Academic › peer-review

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.

Original language	English
Pages (from-to)	709-719
Number of pages	11
Journal	Combinatorics, Probability and Computing
Volume	20
DOIs	https://doi.org/10.1017/S0963548311000253
Publication status	Published - 2011

Access to Document

10.1017/S0963548311000253

Cite this

@article{98c2c56703fa4919ac61535c6a9e75e6,

title = "An Improvement of the Lov{\'a}sz Local Lemma via Cluster Expansion",

abstract = "An old result by Shearer relates the Lov{\'a}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{\'a}sz local lemma. As an application we obtain tighter bounds on conditions for the existence of Latin transversal matrices.",

author = "R. Bissacot and R. Fernandez and A. Procacci and B. Scoppola",

year = "2011",

doi = "10.1017/S0963548311000253",

language = "English",

volume = "20",

pages = "709--719",

journal = "Combinatorics, Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

}

TY - JOUR

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

AU - Bissacot, R.

AU - Fernandez, R.

AU - Procacci, A.

AU - Scoppola, B.

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

U2 - 10.1017/S0963548311000253

DO - 10.1017/S0963548311000253

M3 - Article

SN - 0963-5483

VL - 20

SP - 709

EP - 719

JO - Combinatorics, Probability and Computing

JF - Combinatorics, Probability and Computing

ER -

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

Abstract

Access to Document

Fingerprint

Cite this