Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-16T21:14:56.388Z Has data issue: false hasContentIssue false

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

Published online by Cambridge University Press:  20 June 2011

RODRIGO BISSACOT
Affiliation:
Departamento de Matemática–ICEx, Universidade Federal de Minas Gerais, CP 702 Belo Horizonte, MG, 30161-970Brazil, and Laboratoire de Mathématiques Raphaël Salem, Université de Rouen, 76801, France (e-mail: rodrigo.bissacot@gmail.com)
ROBERTO FERNÁNDEZ
Affiliation:
Department of Mathematics, Utrecht University, PO Box 80010, 3508 TA Utrecht, The Netherlands (e-mail: R.Fernandez1@uu.nl)
ALDO PROCACCI
Affiliation:
Departamento de Matemática–ICEx, Universidade Federal de Minas Gerais, CP 702 Belo Horizonte, MG, 30161-970Brazil (e-mail: aldo@mat.ufmg.br)
BENEDETTO SCOPPOLA
Affiliation:
Dipartimento di Matematica, Universita Tor Vergata di Roma, 00133 Roma, Italy (e-mail: scoppola@mat.uniroma2.it)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Paper
Copyright
Copyright © Cambridge University Press 2011