Version history

Submission versions

  1. lax-296731current versionviewing

    Constructive Lovász Local Lemma

    GitHub sourceShown on this page
  2. lax-41

    Constructive Lovász Local Lemma

Constructive Lovász Local Lemma

lax-296731·formalized by Édouard Bonnet, Codex 5.6 and 6 @EdouardBonnet·registered·created ·GitHub @96597ce·Lean v4.33.0 epoch · mathlib db584cd6d46c·

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this submission may be incorrect.

No flags have been submitted.

    Community review

    Flag this submission

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    Abstract

    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

    Concept map
    4 concepts
    100%
    Proven claimDefinitionThis submissionA → B: B builds on A

    Proofs

    Proof networkview on GitHub

    100%
    assumptions conclusionProven claimClaim from this submissionProof — open large view for details
    Proof list

    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

    No other submission in the archive builds on this one, and this one builds on none.

    Cite this

    This is only the formalizers. The authors of the formalized results may be different (see References).

    @misc{lax-296731,
      author = {Édouard Bonnet, Codex 5.6 and 6},
      title = {Constructive Lovász Local Lemma},
      year = {2026},
      howpublished = {Lax Archive, lax-296731},
      url = {https://laxarchive.org/lax-296731/},
    }

    References

    1. 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
    2. 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

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…