Back to search

University of Nevada - Reno

A Synopsis of the Lovász Local Lemma: Generalizations, Applications, and Algorithms

Abstract

dc:description.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).

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 × 4

Rights

Language dc:language.iso
en_US, English

Identifiers

dc:identifier.*
Repository record dc:identifier.uri
https://scholarwolf.unr.edu/handle/11714/11764

Chain of custody

source
Harvested from
University of Nevada - Reno
Base URL
scholarwolf.unr.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Foster, Nicholas Benjamin. A Synopsis of the Lovász Local Lemma: Generalizations, Applications, and Algorithms. Master's Degree thesis, 2025. https://scholarwolf.unr.edu/handle/11714/11764