Theorem 3.3 — Lovász Local Lemma, asymmetric version
ProvedUncrowdedColoring.theorem_3_3hypergraph-coloringlist-coloringp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilistic-method
Let be events in a probability space, and for each let be such that is mutually independent of . If and for all , then
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.