University of Nevada - Reno
A Synopsis of the Lovász Local Lemma: Generalizations, Applications, and Algorithms
Abstract
dc:description.abstractThe 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).
Degree
thesis:*- Level thesis:degree_level
- Master's Degree
- Department thesis:degree_department
- Mathematics
- Year dc:date.issued
- 2025
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Foster, Nicholas Benjamin
- Advisor dc:contributor.advisor
-
- Kumbhat, Mohit
- Committee members dc:contributor.committeemember
-
- Quint, Thomas
- Sarantsev, Andrey
- Sengupta, Shamik
Subjects
dc:subject × 4Rights
- Language dc:language.iso
- en_US, English
Identifiers
dc:identifier.*- Repository record dc:identifier.uri
- https://scholarwolf.unr.edu/handle/11714/11764