flow_rate_lt_of_strict_metric_bound
If a fractional multicommodity flow supports common rate r on net with sessions sess, and d is a nonnegative, symmetric, triangle-satisfying function on V with d(u,u) = 0 and positive total session length sum_k d(src k, tgt k), and the capacity-weighted total length is strictly less than 2*c times the total session length, then r < c.
Statement
theorem flow_rate_lt_of_strict_metric_bound {V : Type} [Fintype V] [DecidableEq V] {K : Type} [Fintype K] [DecidableEq K] (net : CapacitatedNetwork V) (sess : UnicastSessions V K) {r c : ℝ} (h : FlowSupportsRate net sess r) (d : V → V → ℝ) (h_nonneg : ∀ u v, 0 ≤ d u v) (h_symm : ∀ u v, d u v = d v u) (h_diag : ∀ u, d u u = 0) (h_tri : ∀ u v w, d u v ≤ d u w + d w v) (hpos : 0 < ∑ k, d (sess.src k) (sess.tgt k)) (hlt : ∑ u, ∑ v, net.cap s(u, v) * d u v < 2 * c * (∑ k, d (sess.src k) (sess.tgt k))) : r < c
- Source
- step towards undirected_binary_linear_unicast_advantage
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- flow_rate_mul_two_le_sum_cap_mul_distIf a fractional multicommodity flow on net supports the common rate r, and d is a symmetric, nonnegative, triangle-satisfying function on…
- FlowSupportsRateA common rate r is supported by fractional multicommodity flow on a capacitated network net with unicast sessions sess if there exists a…
- CapacitatedNetworkAn undirected capacitated network on a finite vertex set V given by a simple graph G where each edge in G has strictly positive capacity…
- UnicastSessionsA collection of unicast communication sessions indexed by a type K on an arbitrary vertex type V, consisting of a source map src : K → V,…
The proof, explained
The theorem is proved by applying the metric inequality for multicommodity flows. First, the pseudometric properties of d guarantee that twice the flow rate times the total session distance is at most the capacity-weighted distance. Combining this upper bound with the strict assumption that the capacity-weighted distance is strictly less than 2 * c times the total session distance, and using the positivity of the total session distance, immediately yields r < c.
2 * r * ∑ k, d (sess.src k) (sess.tgt k) ≤ ∑ u, ∑ v, net.cap s(u, v) * d u v
By flow_rate_mul_two_le_sum_cap_mul_dist, any pseudometric d (satisfying nonnegativity, symmetry, d(u,u) = 0, and the triangle inequality) yields an upper bound on the rate r: twice the rate times the sum of distances between session endpoints is at most the total capacity-weighted distance across all pairs of vertices.
uses
flow_rate_mul_two_le_sum_cap_mul_disthave hmain := flow_rate_mul_two_le_sum_cap_mul_dist net sess h d h_nonneg h_symm h_diag h_trir < c automation
Chaining the metric bound 2 * r * D ≤ ∑ u, ∑ v, net.cap s(u, v) * d u v with the strict assumption ∑ u, ∑ v, net.cap s(u, v) * d u v < 2 * c * D yields 2 * r * D < 2 * c * D, where D = ∑ k, d (sess.src k) (sess.tgt k). Since D > 0 by assumption, nonlinear arithmetic concludes r < c.
nlinarith
flow_rate_mul_two_le_sum_cap_mul_dist- If a multicommodity flow supports rate r and d is a pseudometric (nonnegative, symmetric, vanishing on the diagonal, and satisfying the triangle inequality), then 2 * r * ∑ k, d (src k) (tgt k) ≤ ∑ u, ∑ v, cap(u, v) * d(u, v).
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- A strict pseudometric certificate caps every fractional flow rate strictly below c. -/theorem flow_rate_lt_of_strict_metric_bound {V : Type} [Fintype V] [DecidableEq V] {K : Type} [Fintype K] [DecidableEq K] (net : CapacitatedNetwork V) (sess : UnicastSessions V K) {r c : ℝ} (h : FlowSupportsRate net sess r) (d : V → V → ℝ) (h_nonneg : ∀ u v, 0 ≤ d u v) (h_symm : ∀ u v, d u v = d v u) (h_diag : ∀ u, d u u = 0) (h_tri : ∀ u v w, d u v ≤ d u w + d w v) (hpos : 0 < ∑ k, d (sess.src k) (sess.tgt k)) (hlt : ∑ u, ∑ v, net.cap s(u, v) * d u v < 2 * c * (∑ k, d (sess.src k) (sess.tgt k))) : r < c := by have hmain := flow_rate_mul_two_le_sum_cap_mul_dist net sess h d h_nonneg h_symm h_diag h_tri nlinarith