Résumé : We will overview two probabilistic methods used to prove the existence of diverse combinatorial objects with desired properties: First, we will introduce Lovász Local Lemma as a classical tool to prove that, informally speaking, with non-zero probability none of the “bad” events occur if those bad events are of low probability and somewhat essentially independent from each other. Next, we will move on to its algorithmic counterpart, the Entropy Compression Method, used to ensure that a randomized algorithm eventually finds a solution with desired properties. The two methods will be illustrated by applying them to various settings in graph theory, combinatorics, and geometry.
https://www.labri.fr/perso/fkardos/

Mots-Clés : probabilistic method; Lovász Local Lemma; entropy compression method