Lovász local lemma
Statement
Probabilistic method; graph algorithms; LLL and constructive versions. Proved in ZFC.
Proof sketch
ZFC → probability (Kolmogorov). Dependency graph; if each event has few neighbors and low prob, all can be avoided. Moser–Tardos gives constructive proof.
Source
Donald E. Knuth Prize 1999. Probabilistic method; graph algorithms; LLL and constructive versions. Proved in ZFC.
Domains
computer-science