Combinatorics
Lovasz Local Lemma (LLL)
In probability theory, if a large number of events are all independent of one another and each has probability less than 1, then there is a positive (possibly small) probability that none of the events will occur.
The Lovasz local lemma allows to relax the independence condition slightly:
As long as the events are "mostly" independent from one another and aren't individually too likely, then there will still be a positive probability that none of them occurs.
It is commonly used in the probabilistic method for existence proofs.
For an overview check out:
Slides and lecture notes
Finite algorithmic LLL
- (2008) A constructive proof of the Lovasz Local Lemma
- (2009) A constructive proof of the general Lovasz Local Lemma
- (2015) An alternative proof for the constructive Asymmetric LLL
- (2016) A Simple Algorithmic Proof of the Symmetric Lopsided LLL
- (2016) The Lovasz Local Lemma: A constructive proof
- (2023) Deterministic algorithms for the LLL: Simpler, general and parallel
Computability and LLL
Kolmogorov complexity and LLL
Pattern avoidance and LLL
- (1979) Avoidable patterns in strings of symbols
- (1984) There exists an infinite 01-sequence containing no near identical intervals
- (1989) Growth problems for avoidable words
- (1993) Open Problems in Pattern Avoidance
- (2005) Pattern avoidance: themes and variations
- (2005) Insufficiency of four known necessary conditions on string unavoidability
- (2010) Highly non-repetitive sequences: winning strategies from LLL
- (2023) Formal Probabilistic Methods for Combinatorial Structures using LLL