Entropy compression versus Lovász local lemma

DOI10.1016/j.aam.2021.102163zbMath1461.05233OpenAlexW3119690379WikidataQ124817064 ScholiaQ124817064MaRDI QIDQ2020021

Aldo Procacci, Rogério Gomes Alves, Rémy Sanchis

Publication date: 23 April 2021

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.aam.2021.102163

zbMATH Keywords

randomized algorithmsLovász local lemmaprobabilistic method in combinatorics

Mathematics Subject Classification ID

Randomized algorithms (68W20) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items (2)

A General Framework for Hypergraph Coloring ⋮ Hardness transitions and uniqueness of acyclic colouring

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the facial Thue choice number of plane graphs via entropy compression method
• A note on acyclic vertex-colorings
• Application of entropy compression in pattern avoidance
• Improved bounds on coloring of graphs
• Acyclic edge coloring through the Lovász local lemma
• Nonrepetitive colouring via entropy compression
• Extremal problems for transversals in graphs with bounded degree
• On a problem of Spencer
• The linear arboricity of graphs
• Linear coloring of graphs
• Perfect and separating hash families: new bounds via the algorithmic cluster expansion local lemma
• A new bound on the acyclic edge chromatic number
• The local cut lemma
• Improved upper bound for the degenerate and star chromatic numbers of graphs
• Acyclic edge-coloring using entropy compression
• 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
• Avoiding approximate repetitions with respect to the longest common subsequence distance
• A Note on Vertex List Colouring
• Properly coloured copies and rainbow copies of large graphs with small maximum degree
• 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
• An algorithmic approach to the Lovász local lemma. I
• A parallel algorithmic version of the local lemma
• Transversals of Vertex Partitions in Graphs
• New approach to nonrepetitive sequences
• Finding independent transversals efficiently
• A constructive proof of the Lovász local lemma
• Asymptotic Size of Covering Arrays: An Application of Entropy Compression

This page was built for publication: Entropy compression versus Lovász local lemma