Lemma 1, Eq.(57): path rounding
OpenQAlgorithms.Papers.Independent.Intakethird100.P35.path_roundingLet be a finite undirected graph with distinct vertices . Fix positive integers and finite nonnegative edge capacities , which may depend on . Let be the number of all simple directed paths from to in , and let be the maximum net source outflow subject to nonnegative oriented flows, the shared constraint , and conservation at other vertices. Replace edge by unit edges. There is a family of edge-disjoint -- paths in this actual multigraph satisfying
This turns fractional single-pair flow into an integral path packing. If no path exists, and the empty family satisfies the statement.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P35
noncomputable section
namespace QAlgorithms.Papers.Independent.Intakethird100.P35
open scoped BigOperators
attribute [local instance] Classical.propDecidable Classical.decEq
/-- PDF p.20, Lemma 1, (57): actual edge-disjoint paths in floor(mkNc).
The source's positive integers m,k are explicit; N is the number of ALL simple
s-to-t paths. Capacities are quantified after m,k and may depend on them. -/
theorem path_rounding {n e : ℕ} (G : EdgeGraph n (Fin e))
(hSimple : IsSimple G) (s t : Fin n) (hst : s ≠ t)
(m k : ℕ) (hm : 0 < m) (hk : 0 < k)
(c : Fin e → ℝ) (hc : ∀ a, 0 ≤ c a) :
∃ P : Packing G (roundedCopies c m k (pathCount G s t))
(fun _ : Fin 1 => s) (fun _ : Fin 1 => t),
((m * k * pathCount G s t : ℕ) : ℝ) *
(singlePairFlowValue G c s t - 1 / (k : ℝ)) ≤ (P.count 0 : ℝ) := by sorry
end QAlgorithms.Papers.Independent.Intakethird100.P35
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For all natural numbers , let have vertex set and edge set , with distinct endpoints for each edge. Assume that whenever two edge labels have the same endpoints in the same or reversed order, those edge labels are equal. Choose vertices with , positive natural numbers , and a function with for every edge. Let count all paths obtained by choosing a length , an injective sequence with , , and edge labels joining consecutive vertices in either orientation. Let be the total real supremum of the set of source outflows over functions satisfying , for every edge, and for every , where . Replace each edge by labeled copies with the same endpoints. Then there exists a packing for the single terminal pair : it has a natural number of selected paths, each with length less than , injective vertex sequence from to , and copied edges joining consecutive vertices in either orientation, such that distinct selected paths share no copied edge, and , with natural numbers interpreted as reals in this inequality. The assumptions force but allow and allow ; if , every , the only possible count is , and the asserted bound is . The inequality itself does not require a positive count when its left side is nonpositive.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.