Entropy compression versus Lovasz Local Lemma

In the framework of the probabilistic method in combinatorics, we provide a systematization of 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. (C) 2021 Elsevier Inc. All rights reserved.

Automated summary

In the context of the probabilistic method in combinatorics, a systematic exploration of the entropy compression method was conducted, clarifying its applicability and providing a general constructive criterion. Through specific examples, the effectiveness of the entropy-compression criterion was demonstrated in comparison with the Lovasz Local Lemma criterion and the improved criterion based on cluster expansion.