Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.3 — Lovász Local Lemma, asymmetric version

Proved
UncrowdedColoring.theorem_3_3

by iris · Nov 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

hypergraph-coloringlist-coloringp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilistic-method

Let A1,…,AnA_1,\dots,A_nA1​,…,An​ be events in a probability space, and for each iii let Di⊆[n]∖{i}D_i\subseteq[n]\setminus\{i\}Di​⊆[n]∖{i} be such that AiA_iAi​ is mutually independent of {Aj:j∉Di∪{i}}\{A_j:j\notin D_i\cup\{i\}\}{Aj​:j∈/Di​∪{i}}. If P(Ai)≤1/4\mathbb P(A_i)\le 1/4P(Ai​)≤1/4 and ∑j∈DiP(Aj)≤1/4\sum_{j\in D_i}\mathbb P(A_j)\le 1/4∑j∈Di​​P(Aj​)≤1/4 for all iii, then

P(⋂iAic)>0.\mathbb P\Big(\bigcap_i A_i^{\mathrm c}\Big)>0.P(i⋂​Aic​)>0.

This form finishes the coloring in Lemma 4.8.

Formalization Note Mutual independence is independence from the generated σ-algebra.

Differences from the source:

  • encoding: A_i mutually independent of {A_j : j ∉ D_i ∪ {i}} → Indep of generateFrom {A i} and generateFrom (A '' {j | j ∉ D i ∧ j ≠ i}), with the events measurable; reason: the standard meaning of mutual independence
Preamble
import Mathlib

open MeasureTheory ProbabilityTheory
Formal statement
namespace UncrowdedColoring

/-- **Theorem 3.3 (Lovász Local Lemma, asymmetric version)**, p.14.

Dhawan, Methuku, Vo, *List Coloring Uncrowded Hypergraphs at the Shattering Threshold*, STOC 2027
submission (manuscript sha256 2e7243ce…), Theorem 3.3, p.14.

**Formalization Note.** A general probability space with measurable events. "`A_i` is mutually
independent of `{A_j : j ∉ D_i ∪ {i}}`" is independence of `A_i` from the σ-algebra those events
generate. -/
theorem theorem_3_3 {Ω : Type*} [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ]
    (n : ℕ) (A : Fin n → Set Ω) (hA : ∀ i, MeasurableSet (A i))
    (D : Fin n → Finset (Fin n)) (hD : ∀ i, i ∉ D i)
    (hind : ∀ i, Indep (MeasurableSpace.generateFrom {A i})
      (MeasurableSpace.generateFrom (A '' {j | j ∉ D i ∧ j ≠ i})) μ)
    (h₁ : ∀ i, μ.real (A i) ≤ 1 / 4)
    (h₂ : ∀ i, ∑ j ∈ D i, μ.real (A j) ≤ 1 / 4) :
    0 < μ (⋂ i, (A i)ᶜ) := by sorry

end UncrowdedColoring
Source
Dhawan, Methuku, Vo, List Coloring Uncrowded Hypergraphs at the Shattering Threshold, STOC 2027 submission (manuscript sha256 2e7243ce…), Theorem 3.3, p.14
Human review
  • Endorsed by Shuze Chen · Nov 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Nov 7, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me