§2.4 — |𝒫₃| ≤ n/β₁ + 2gc(6β₂c²)^{2g+2} when ℰ₂ and ℰ₃(2g) fail
ProvedEDPHardness.IntegralityGap.short_paths_boundLet , assume , , and let with . Let be a hypergraph on vertices with hyperedges of size for which neither (more than vertices of degree ) nor (more than cycles of length at most in ) occurs. In every integral routing in with congestion at most , the set of pairs routed on a non-canonical path with fewer than edges satisfies
The term accounts for the high-degree vertices; the remaining set has , because a short non-canonical path and the canonical path of a low-degree vertex together close a short cycle of .
Formalization Note The page bounds the discarded high-degree pairs by and separately; the statement is their sum. The hypothesis is the page's "". Lengths are counted in .
import Mathlib import Definitions.Def_EDPHardness_IntegralityGap_FlowRelaxation import Definitions.Def_EDPHardness_IntegralityGap_GapInstance
namespace EDPHardness.IntegralityGap
theorem short_paths_bound (n c : ℕ) (hc : 2 ≤ c) (hβ₁ : 0 < beta1 n c) (hβ₂ : 0 < beta2 n c)
(hg : 10 * beta2 n c * c ≤ (gParam n c : ℝ))
(H : Hyp n (numEdges n c) c) (hE₂ : ¬ E2 n c H) (hE₃ : ¬ E3 n c (2 * gParam n c) H)
(R : IntRouting (gapGraph H) (src n (numEdges n c)) (snk n (numEdges n c)) (c - 1)) :
((Finset.univ.filter
(fun v : R.routed => (R.path v).support ≠ canonicalSupport H v ∧
(R.path v).length < gParam n c)).card : ℝ)
≤ (n : ℝ) / beta1 n c +
2 * gParam n c * c * (6 * beta2 n c * (c : ℝ) ^ 2) ^ (2 * gParam n c + 2) := by sorry
end EDPHardness.IntegralityGap
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.