The local cut lemma

DOI10.1016/j.ejc.2017.03.005zbMath1365.05288arXiv1601.05481OpenAlexW2345918188WikidataQ124834335 ScholiaQ124834335MaRDI QIDQ2357223

Anton Bernshteyn

Publication date: 19 June 2017

Published in: European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

Lovász local lemmaentropy compression method

Mathematics Subject Classification ID

Combinatorial probability (60C05) Measures of information, entropy (94A17) Graph algorithms (graph-theoretic aspects) (05C85) Extremal combinatorics (05D99)

Related Items (12)

New bounds for the acyclic chromatic index ⋮ The asymptotic behavior of the correspondence chromatic number ⋮ A General Framework for Hypergraph Coloring ⋮ Single‐conflict colouring ⋮ Colorings, transversals, and local sparsity ⋮ Graphs of low average degree without independent transversals ⋮ Another approach to non-repetitive colorings of graphs of bounded degree ⋮ Moser-Tardos resampling algorithm, entropy compression method and the subset gas ⋮ The lonely runner problem for lacunary sequences ⋮ Progress on the Adjacent Vertex Distinguishing Edge Coloring Conjecture ⋮ Entropy compression versus Lovász local lemma ⋮ An Algorithmic Proof of the Lovász Local Lemma via Resampling Oracles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• New bounds for the acyclic chromatic index
• Improved bounds on coloring of graphs
• Nonrepetitive colouring via entropy compression
• Nonrepetitive vertex colorings of graphs
• Lopsided Lovász Local lemma and Latin transversals
• Sparse colour-critical hypergraphs
• Nonrepetitive colorings of graphs -- a survey
• Acyclic edge-coloring using entropy compression
• The asymptotic behavior of the correspondence chromatic number
• Acyclic edge colorings of graphs
• Nonrepetitive list colourings of paths
• An Improvement of the Lovász Local Lemma via Cluster Expansion
• An Extension of the Moser--Tardos Algorithmic Local Lemma
• A constructive proof of the general lovász local lemma
• Acyclic coloring of graphs
• Sparse color‐critical graphs and hypergraphs with no short cycles
• Nonrepetitive colorings of graphs
• New approach to nonrepetitive sequences
• Improved bounds and algorithms for hypergraph 2-coloring
• Deterministic Algorithms for the Lovász Local Lemma
• Acyclic colorings of planar graphs
• On the number of edges in colour-critical graphs and hypergraphs

This page was built for publication: The local cut lemma