A Synopsis of the Lovász Local Lemma: Generalizations, Applications, and Algorithms
Loading...
Authors
Foster, Nicholas Benjamin
Issue Date
2025
Type
Thesis
Language
en_US
Keywords
algorithm , combinatorics , Lovász , probability
Alternative Title
Abstract
The Lovász Local Lemma, introduced by Paul Erdős and László Lovász in 1975, stands as one of the most powerful tools in the Probabilistic Method. This thesis traces the historical development of the Lovász Local Lemma from its origins in Erdős’s pioneering probabilistic arguments to its formalization and generalizations by Lovász along with other contributors. Beginning with the motivation rooted in Ramsey theory, hypergraph coloring problems, and others, we explore how the Lovász Local Lemma transformed probabilistic existence proofs in Combinatorics and explore its applications. We also examine some generalizations of the lemma, including the algorithmic versions introduced by Beck (1991) and Moser–Tardos (2010).