A local lemma via entropy compression
arXiv:1509.04638
Abstract
In the framework of the probabilistic method in combinatorics, we revisit the entropy compression method clarifying the setting in which it can be applied and providing a theorem yielding a general constructive criterion. We finally elucidate, through topical examples, the effectiveness of the entropy-compression criterion in comparison with the Lovasz Local Lemma criterion and, in particular, with the improved criterion based on cluster expansion.
References in corpus (6)
- The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
- Acyclic edge-coloring using entropy compression
- Nonrepetitive Colouring via Entropy Compression
- Entropy compression method applied to graph colorings
- The Local Cut Lemma
- On the facial Thue choice index via entropy compression