Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.1 (p. 226) — every multicommodity network has a cut with Cap(S)/Dem(S) ≤ O(log k) · maxflow

Proved
GeometryOfGraphs.FlowCut.theorem_4_1

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

metric-embeddingsmulticommodity-flowp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1sparsest-cut

There is an absolute constant C0>0C_0 > 0C0​>0 with the following property. Let NNN be a multicommodity flow network: a finite vertex set VVV, symmetric capacities Ci,j≥0C_{i,j} \ge 0Ci,j​≥0 (zero on non-edges and on the diagonal), and kkk source–sink pairs (sμ,tμ)(s_\mu, t_\mu)(sμ​,tμ​) with demands Dμ≥0D_\mu \ge 0Dμ​≥0. Suppose some commodity has Dμ>0D_\mu > 0Dμ​>0 and sμ≠tμs_\mu \ne t_\musμ​=tμ​. Then there is a set S⊆VS \subseteq VS⊆V with Dem(S)>0\mathrm{Dem}(S) > 0Dem(S)>0 and

Cap(S)Dem(S)≤C0log⁡(max⁡(k,2))⋅maxflow(N).\frac{\mathrm{Cap}(S)}{\mathrm{Dem}(S)} \le C_0 \log(\max(k,2)) \cdot \mathrm{maxflow}(N).Dem(S)Cap(S)​≤C0​log(max(k,2))⋅maxflow(N).

Here Cap(S)\mathrm{Cap}(S)Cap(S) is the total capacity of the edges leaving SSS, Dem(S)\mathrm{Dem}(S)Dem(S) the total demand of the pairs separated by SSS, and maxflow(N)\mathrm{maxflow}(N)maxflow(N) the largest λ\lambdaλ such that λDμ\lambda D_\muλDμ​ units of every commodity μ\muμ can be routed simultaneously within the capacities. Since every cut satisfies maxflow≤Cap(S)/Dem(S)\mathrm{maxflow} \le \mathrm{Cap}(S)/\mathrm{Dem}(S)maxflow≤Cap(S)/Dem(S), the theorem says that the gap between the concurrent maximum multicommodity flow and the sparsest cut is O(log⁡k)O(\log k)O(logk), where kkk 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 log⁡n\log nlogn, so the logarithmic factor cannot be removed.

Formalization Note The paper asserts a deterministic polynomial-time algorithm that finds SSS; the statement asserts only the existence of SSS. The paper writes O(log⁡k)O(\log k)O(logk); the statement asserts an absolute constant C0C_0C0​, quantified before the network, and uses log⁡(max⁡(k,2))\log(\max(k,2))log(max(k,2)) so that k=1k = 1k=1 is covered with the same constant. The inequality is cross-multiplied: Cap(S)≤C0log⁡(max⁡(k,2)) maxflow(N) Dem(S)\mathrm{Cap}(S) \le C_0 \log(\max(k,2))\,\mathrm{maxflow}(N)\,\mathrm{Dem}(S)Cap(S)≤C0​log(max(k,2))maxflow(N)Dem(S). The hypothesis on some commodity is what makes some Dem(S)\mathrm{Dem}(S)Dem(S) positive and maxflow finite.

Preamble
import Mathlib
import Definitions.Def_GeometryOfGraphs_FlowCut_Network
import Definitions.Def_GeometryOfGraphs_FlowCut_Maxflow

set_option autoImplicit false
Formal statement
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
Source
N. Linial, E. London, Y. Rabinovich, The geometry of graphs and some of its algorithmic applications, Combinatorica 15 (1995), p. 226, Theorem 4.1
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me