§2.4 ¶1 — with probability ≥ 1/4 none of ℰ₁, ℰ₂, ℰ₃(2g) occurs, g = 3β₁β₂c²
ProvedEDPHardness.IntegralityGap.good_eventp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1random-hypergraphunion-bound
Let be the random hypergraph of the mission ( vertices, independent uniform -subsets), and let .
There are absolute constants and such that for every and every integer with ,
where is the event that has more than cycles of length at most .
This is the step where the probabilistic part ends: a hypergraph with all three good properties exists, and the rest of the analysis is deterministic.
Formalization Note "Sufficiently large " and the range of are the constants and , chosen before and ; is rounded up to an integer.
Preamble
import Mathlib import Definitions.Def_EDPHardness_IntegralityGap_GapInstance
Formal statement
namespace EDPHardness.IntegralityGap
theorem good_event :
∃ α : ℝ, 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)) →
1 / 4 ≤ hypProb n (numEdges n c) c
(fun H => ¬ E1 n c H ∧ ¬ E2 n c H ∧ ¬ E3 n c (2 * gParam n c) H) := by sorry
end EDPHardness.IntegralityGap
Source
Andrews, Chuzhoy, Guruswami, Khanna, Talwar, Zhang, Inapproximability of Edge-Disjoint Paths and Low Congestion Routing on Undirected Graphs, Combinatorica 30 (2010), p. 495, Section 2.4, first paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.