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.
Bissacot, R., Fernandez, R., Procacci, A., Scoppola, B. (2011). An improvement of the Lovász local lemma via cluster expansion. COMBINATORICS PROBABILITY & COMPUTING, 20(5), 707-719 [10.1017/S0963548311000253].
An improvement of the Lovász local lemma via cluster expansion
SCOPPOLA, BENEDETTO
2011-01-01
Abstract
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.| File | Dimensione | Formato | |
|---|---|---|---|
|
bfps.pdf
solo utenti autorizzati
Descrizione: articolo principale
Licenza:
Copyright dell'editore
Dimensione
160.96 kB
Formato
Adobe PDF
|
160.96 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
