Entropy compression versus Lovász Local Lemma.

Nenhuma Miniatura disponível
Data
2021
Título da Revista
ISSN da Revista
Título de Volume
Editor
Resumo
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 Lovász Local Lemma criterion and, in particular, with the improved criterion based on cluster expansion.
Descrição
Palavras-chave
Probabilistic method in combinatorics, Randomized algorithms
Citação
ALVES, R. G.; PROCACCI, A.; SANCHIS, R. P. Entropy compression versus Lovász Local Lemma. Advances in Applied Mathematics, v. 125, artigo 102163, 2021. Disponível em: <https://www.sciencedirect.com/science/article/abs/pii/S0196885821000014?via%3Dihub>. Acesso em: 25 ago. 2021.