期刊
COMBINATORICS PROBABILITY & COMPUTING
卷 20, 期 5, 页码 709-719出版社
CAMBRIDGE UNIV PRESS
DOI: 10.1017/S0963548311000253
关键词
-
资金
- Conselho Nacional de Desenvolvimento Cientifico e Tecnologico (CNPq)
- CAPES (Coordenacao de Aperfeicoamento de Pessoal de Nivel Superior, Brasil)
- FAPEMIG (Fundacao de Amparo a Pesquisa do Estado de Minas Gerais)
An old result by Shearer relates the Lovasz 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 Lovasz local lemma. As an application we obtain tighter bounds on conditions for the existence of Latin transversal matrices.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据