Theorem 4.1 (p. 226) — every multicommodity network has a cut with Cap(S)/Dem(S) ≤ O(log k) · maxflow
ProvedGeometryOfGraphs.FlowCut.theorem_4_1There is an absolute constant with the following property. Let be a multicommodity flow network: a finite vertex set , symmetric capacities (zero on non-edges and on the diagonal), and source–sink pairs with demands . Suppose some commodity has and . Then there is a set with and
Here is the total capacity of the edges leaving , the total demand of the pairs separated by , and the largest such that units of every commodity can be routed simultaneously within the capacities. Since every cut satisfies , the theorem says that the gap between the concurrent maximum multicommodity flow and the sparsest cut is , where is the number of commodities and not the number of vertices.
This is the main theorem of the paper. For a single commodity the max-flow min-cut theorem gives equality; for an expander with all-pairs unit demands the gap is of order , so the logarithmic factor cannot be removed.
Formalization Note The paper asserts a deterministic polynomial-time algorithm that finds ; the statement asserts only the existence of . The paper writes ; the statement asserts an absolute constant , quantified before the network, and uses so that is covered with the same constant. The inequality is cross-multiplied: . The hypothesis on some commodity is what makes some positive and maxflow finite.
import Mathlib import Definitions.Def_GeometryOfGraphs_FlowCut_Network import Definitions.Def_GeometryOfGraphs_FlowCut_Maxflow set_option autoImplicit false
namespace GeometryOfGraphs.FlowCut
/-- Theorem 4.1 (p. 226), existence form: there is an absolute constant `C₀ > 0` such that every
multicommodity flow network with `k` source–sink pairs, at least one of which has positive demand and
distinct endpoints, has a vertex set `S` with `Dem(S) > 0` and
`Cap(S) / Dem(S) ≤ C₀ · log (max k 2) · maxflow` (stated cross-multiplied). The paper's `O(log k)`
is `C₀ · log (max k 2)`; the deterministic polynomial-time algorithm is not stated. -/
theorem theorem_4_1 :
∃ C₀ : ℝ, 0 < C₀ ∧
∀ (V : Type) [Fintype V] [DecidableEq V] (N : Network V),
(∃ μ, 0 < N.D μ ∧ N.s μ ≠ N.t μ) →
∃ S : Finset V, 0 < N.Dem S ∧
N.Cap S ≤ C₀ * Real.log (max (N.k : ℝ) 2) * N.maxflow * N.Dem S := by sorry
end GeometryOfGraphs.FlowCut
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.