other · Centre International de Rencontres Mathématiques · 2024

Probabilistic methods: entropy compression

Kardoš, František

Cited by 0Open access

Abstract

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/

Cite this paper

APA 7

Kardoš, F. (2024). Probabilistic methods: entropy compression. Centre International de Rencontres Mathématiques. https://doi.org/10.24350/cirm.v.20151003

MLA 9

Kardoš, František. “Probabilistic methods: entropy compression.” Centre International de Rencontres Mathématiques, 2024, https://doi.org/10.24350/cirm.v.20151003.

Chicago

Kardoš, František. 2024. “Probabilistic methods: entropy compression.” Centre International de Rencontres Mathématiques. https://doi.org/10.24350/cirm.v.20151003.

Harvard

Kardoš, F. (2024) ‘Probabilistic methods: entropy compression’, Centre International de Rencontres Mathématiques. Available at: https://doi.org/10.24350/cirm.v.20151003.

BibTeX

@misc{kardos2024probabilistic,
  title = {{Probabilistic methods: entropy compression}},
  author = {Kardoš, František},
  journal = {Centre International de Rencontres Mathématiques},
  year = {2024},
  doi = {10.24350/cirm.v.20151003}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.