Constructive Lovász Local Lemma
No public endorsements yet.
Loading review…
Sign in with ORCIDAbstract
This submission formalizes Theorem 1.2 of Moser and Tardos, A Constructive Proof of the General Lovász Local Lemma, and Theorem 2.2 of Haeupler, Saha, and Srinivasan, New Constructive Aspects of the Lovász Local Lemma. For finitely many measurable bad events determined by mutually independent random variables, it proves the asymmetric local-lemma conclusion and the resampling algorithm's expected per-event and total resampling bounds. It also proves that any observed event is true at some stage—and hence in the output distribution—with probability at most its original probability times the inverse local-lemma product over its dependency neighborhood. The proofs use resampling tables, proper witness trees, branching-process weight estimates, and a finite-termination argument.
Concepts
- def
Lax41.HaeuplerSahaSrinivasanDefinitions - thm✓
Lax41.HaeuplerSahaSrinivasanTheorem22 - thm✓
Lax41.MoserTardos - def
Lax41.MoserTardosDefinitions
Concept map
Proofs
Proof networkview on GitHub
Lean sources for these proofs: proofs/ on GitHub
Proof code is not displayed; the archive records each proof's checked relationship between claims.
Related submissions
Submission map
Cite this
@misc{lax-41,
author = {Édouard Bonnet},
title = {Constructive Lovász Local Lemma},
year = {2026},
howpublished = {Lax Archive, lax-41},
url = {https://laxarchive.org/lax-41/},
}
References
- Robin A. Moser and Gábor Tardos. A Constructive Proof of the General Lovász Local Lemma. Journal of the ACM 57(2):11:1–11:15, 2010. doi:10.1145/1667053.1667060 · doi.org/10.1145/1667053.1667060
- Bernhard Haeupler, Barna Saha and Aravind Srinivasan. New Constructive Aspects of the Lovász Local Lemma. Journal of the ACM 58(6):28:1–28:28, 2011. doi:10.1145/2049697.2049702 · doi.org/10.1145/2049697.2049702
Community review
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above; your ORCID profile must share a public name.
0 comments