Theorem 3.2 — Lovász Local Lemma, symmetric version
ProvedUncrowdedColoring.theorem_3_2hypergraph-coloringlist-coloringp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilistic-method
Let be events in a probability space and with for all . Suppose each is mutually independent of a set of all but at most of the other events. If , then
The symmetric Local Lemma glues the bad events of one nibble step in Lemma 4.7.
Formalization Note Mutual independence of from a set of events is independence from the σ-algebra they generate.
Differences from the source:
- encoding: A_i mutually independent of a set of events → Indep of generateFrom {A i} and generateFrom (A '' S i), with the events measurable; reason: the standard meaning of mutual independence
Preamble
import Mathlib open MeasureTheory ProbabilityTheory
Formal statement
namespace UncrowdedColoring
/-- **Theorem 3.2 (Lovász Local Lemma, symmetric version)**, p.14.
Dhawan, Methuku, Vo, *List Coloring Uncrowded Hypergraphs at the Shattering Threshold*, STOC 2027
submission (manuscript sha256 2e7243ce…), Theorem 3.2, p.14.
**Formalization Note.** A general probability space with measurable events. "`A_i` is mutually
independent of a set of events" is independence of `A_i` from the σ-algebra generated by that set. `S i`
is that set; at most `dLLL` of the other events lie outside it. `dLLL = 0` and `p = 0` are allowed. -/
theorem theorem_3_2 {Ω : Type*} [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ]
(n : ℕ) (A : Fin n → Set Ω) (hA : ∀ i, MeasurableSet (A i))
(p : ℝ) (hp₀ : 0 ≤ p) (hp₁ : p < 1) (hpA : ∀ i, μ.real (A i) ≤ p)
(dLLL : ℕ) (S : Fin n → Finset (Fin n)) (hS : ∀ i, i ∉ S i)
(hcard : ∀ i, ((Finset.univ.erase i) \ S i).card ≤ dLLL)
(hind : ∀ i, Indep (MeasurableSpace.generateFrom {A i})
(MeasurableSpace.generateFrom (A '' (S i : Set (Fin n)))) μ)
(h4 : 4 * p * (dLLL : ℝ) ≤ 1) :
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.2, p.14
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.