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

DOI10.1017/S0963548311000253zbMath1233.05196arXiv0910.1824WikidataQ125017458 ScholiaQ125017458MaRDI QIDQ3103621

Benedetto Scoppola, Rodrigo Bissacot, Aldo Procacci, Roberto Fernández

Publication date: 8 December 2011

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0910.1824

zbMATH Keywords

independent set polynomialLovasz local lemmaLatin transversal matrices

Mathematics Subject Classification ID

Graph polynomials (05C31) Statistical mechanics of polymers (82D60) Combinatorial probability (60C05) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items (29)

New bounds for the acyclic chromatic index ⋮ Commutativity in the Algorithmic Lovász Local Lemma ⋮ Virial series for a system of classical particles interacting through a pair potential with negative minimum ⋮ Rainbow Hamilton cycles and lopsidependency ⋮ A General Framework for Hypergraph Coloring ⋮ Deterministic algorithms for the Lovász local lemma: Simpler, more general, and more parallel ⋮ Improved bounds on coloring of graphs ⋮ A new bound on the acyclic edge chromatic number ⋮ Moser-Tardos resampling algorithm, entropy compression method and the subset gas ⋮ Unnamed Item ⋮ New bounds for the Moser‐Tardos distribution ⋮ Shearer's measure and stochastic domination of product measures ⋮ Acyclic edge-coloring using entropy compression ⋮ Abstract polymer gas: a simple inductive proof of the Fernández-Procacci criterion ⋮ Rainbow perfect matchings in \(r\)-partite graph structures ⋮ Sufficient conditions for uniform bounds in abstract polymer systems and explorative partition schemes ⋮ Linear arboricity of regular digraphs ⋮ On the convergence of cluster expansions for polymer gases ⋮ Entropy compression versus Lovász local lemma ⋮ Covering systems with restricted divisibility ⋮ An Algorithmic Proof of the Lovász Local Lemma via Resampling Oracles ⋮ Witness trees in the Moser-Tardos algorithmic Lovász local lemma and Penrose trees in the hard-core lattice gas ⋮ Transversals in generalized Latin squares ⋮ Acyclic edge colourings of graphs with large girth ⋮ Finding independent transversals efficiently ⋮ A Local Lemma for Focused Stochastic Algorithms ⋮ Cluster expansions: necessary and sufficient convergence conditions ⋮ Comparison of two convergence criteria for the variable-assignment Lopsided Lovász Local Lemma ⋮ The local cut lemma

Cites Work

• Lopsided Lovász Local lemma and Latin transversals
• On a problem of Spencer
• Asymptotic lower bounds for Ramsey functions
• Cluster expansion for abstract polymer models. New bounds from an old approach
• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• A Note on Vertex List Colouring
• On Dependency Graphs and the Lattice Gas
• A constructive proof of the general lovász local lemma

This page was built for publication: An Improvement of the Lovász Local Lemma via Cluster Expansion