Lemma 7 — Pr[ℰ₂] ≤ 1/4: at most n/β₁ vertices lie in more than 10β₂c hyperedges
ProvedEDPHardness.IntegralityGap.lemma_7chernoff-boundmarkov-inequalityp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1random-hypergraph
Let be the random hypergraph on vertices with independent hyperedges, each uniform among the -subsets, with as in the definitions ( to base , natural). A vertex is high-degree if it lies in more than hyperedges, and is the event that more than vertices are high-degree.
There are absolute constants and such that for every and every integer with ,
Together with Lemma 6 this controls the vertices whose canonical paths are long, which the analysis of short non-canonical paths has to discard.
Formalization Note "Sufficiently large " and the range are the constants and , chosen before and . The probability is a normalized count over all hyperedge tuples.
Preamble
import Mathlib import Definitions.Def_EDPHardness_IntegralityGap_GapInstance
Formal statement
namespace EDPHardness.IntegralityGap
theorem lemma_7 :
∃ α : ℝ, 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 (E2 n c) ≤ 1 / 4 := 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. 493, Lemma 7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.