A Sharper Local Lemma with Improved Applications

DOI10.1007/978-3-642-32512-0_51zbMath1372.05230OpenAlexW310689670MaRDI QIDQ3167430

Yixin Xu, Kashyap Babu Rao Kolipaka, Mario Szegedy

Publication date: 2 November 2012

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-32512-0_51

zbMATH Keywords

graph coloringLovász local lemmaindependent set polynomialhard-core lattice model

Mathematics Subject Classification ID

Combinatorial probability (60C05) Coloring of graphs and hypergraphs (05C15) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items (7)

A General Framework for Hypergraph Coloring ⋮ Graphs with $\chi=\Delta$ Have Big Cliques ⋮ Unnamed Item ⋮ Nonrepetitive colouring via entropy compression ⋮ An Algorithmic Proof of the Lovász Local Lemma via Resampling Oracles ⋮ Finding independent transversals efficiently ⋮ Comparison of two convergence criteria for the variable-assignment Lopsided Lovász Local Lemma

This page was built for publication: A Sharper Local Lemma with Improved Applications