JournalsaihpdVol. 9, No. 3pp. 435–471

Moser–Tardos resampling algorithm, entropy compression method and the subset gas

  • Paula M. S. Fialho

    Universidade Federal de Minas Gerais, Belo Horizonte, Brazil

  • Bernardo N.B. de Lima

    Universidade Federal de Minas Gerais, Belo Horizonte, Brazil

  • Aldo Procacci

    Universidade Federal de Minas Gerais, Belo Horizonte, Brazil
Moser–Tardos resampling algorithm, entropy compression method and the subset gas cover
Download PDF

This article is published open access under our Subscribe to Open model.

Abstract

We establish a connection between the entropy compression method and the Moser–Tardos algorithmic version of the Lovász local lemma through the cluster expansion of the subset gas. We also show that the Moser–Tardos resampling algorithm and the entropy compression bactracking algorithm produce identical bounds.

Cite this article

Paula M. S. Fialho, Bernardo N.B. de Lima, Aldo Procacci, Moser–Tardos resampling algorithm, entropy compression method and the subset gas. Ann. Inst. Henri Poincaré Comb. Phys. Interact. 9 (2022), no. 3, pp. 435–471

DOI 10.4171/AIHPD/122