Lovász local lemma
Lema local de Lovász
- Date
- 1975 · confidence low
- Place
- Budapest, Hungary
- Credited to
- Paul Erdős and László Lovász (1975)
- Field
- Knowledge & symbols
What was discovered
Probability-theory result that relaxes full independence between events, guaranteeing a positive probability that none occurs when they are 'mostly' independent; a key tool of the probabilistic method.
What it led to
- development of the probabilistic method in combinatorics
- graph coloring algorithms
- constructive algorithmic version of the lemma (Moser–Tardos)
- applications in Ramsey theory