Lemma 6 — Pr[ℰ₁] ≤ 1/4: with probability ≥ 3/4 every set of n/β₁ vertices contains a hyperedge
ProvedEDPHardness.IntegralityGap.lemma_6Let be the random hypergraph on vertices with independent hyperedges, each uniform among the -subsets, where , ( to base , natural). A set of vertices is bad if it contains none of the hyperedges, and is the event that a bad set exists.
There are absolute constants and such that for every and every integer with ,
This is the property that makes canonical routings expensive: if no bad set exists, any pairs routed on their canonical paths include all members of some hyperedge, which then share its special edge.
Formalization Note The paper states the lemma for "sufficiently large " in the regime of Theorem 5; these two asymptotic qualifiers are the constants and , chosen before and . The probability is the fraction of all -tuples of -subsets that satisfy the event. Bad sets have size .
import Mathlib import Definitions.Def_EDPHardness_IntegralityGap_GapInstance
namespace EDPHardness.IntegralityGap
theorem lemma_6 :
∃ α : ℝ, 0 < α ∧ ∃ N₀ : ℕ, ∀ n : ℕ, N₀ ≤ n → ∀ c : ℕ, 2 ≤ c →
(c : ℝ) ≤ α * Real.logb 2 (Real.logb 2 n) / Real.logb 2 (Real.logb 2 (Real.logb 2 n)) →
hypProb n (numEdges n c) c (E1 n c) ≤ 1 / 4 := by sorry
end EDPHardness.IntegralityGap
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.