§2.4 ā |š«ā²| ⤠4n/βā: if none of ā°ā, ā°ā, ā°ā(2g) occurs, every congestion-(cā1) routing routes ⤠4n/βā pairs
ProvedEDPHardness.IntegralityGap.routed_pairs_boundedge-disjoint-pathsintegrality-gapp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let . There are absolute constants and such that for every , every integer with , and every hypergraph on vertices with hyperedges of size for which none of , , occurs, every integral routing in with congestion at most routes at most
pairs ( to base in and in the range of ).
This combines the three bounds on , , with the estimate , valid for large in this range of .
Formalization Note "Sufficiently large " and the range of are the constants and , chosen before , and . The page writes the final estimate as a chain whose "" is not an identity; only the conclusion is stated.
Preamble
import Mathlib import Definitions.Def_EDPHardness_IntegralityGap_FlowRelaxation import Definitions.Def_EDPHardness_IntegralityGap_GapInstance
Formal statement
namespace EDPHardness.IntegralityGap
theorem routed_pairs_bound :
ā α : ā, 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)) ā
ā H : Hyp n (numEdges n c) c, ¬ E1 n c H ā ¬ E2 n c H ā ¬ E3 n c (2 * gParam n c) H ā
ā R : IntRouting (gapGraph H) (src n (numEdges n c)) (snk n (numEdges n c)) (c - 1),
(R.routed.card : ā) ⤠4 * (n : ā) / beta1 n c := 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. 496, Section 2.4 (the chain for |Pā²3| and "In total, |Pā²| ⩽ 4n/β1")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.