Lemma 10, p. 802 — if π(T) ≥ 2p/3 and Σ_{u∈𝒫−T} π(u)d(T,u) ≥ 1/2p, there is a cut of weighted ratio cost ≤ 6W
ProvedLeightonRao.Product.lemma_10Let be a connected capacitated network on , let be a PMFP node weighting with and , and let be a distance function with total weight . Suppose satisfies and
Then there is a cut with , and weighted ratio cost
This is the "heavy core" case of Lemma 11: when a heavy set is far, on average, from the remaining weight, a level cut around is cheap.
Formalization Note The page writes "ratio cost "; its proof (which defines as the weighted ratio cost) and its use in Lemma 11 make clear that the weighted ratio cost is meant, and that is what is stated. The constant is the one obtained by the computation in the proof of Lemma 5 (p. 800), to which the proof of Lemma 10 refers. The sum over is written over ; the extra terms vanish because off . Connectivity makes the graph distances meaningful.
import Mathlib import Definitions.Def_LeightonRao_Product_Setting
namespace LeightonRao.Product
theorem lemma_10 {V : Type} [Fintype V] [DecidableEq V] (N : Network V) (hconn : IsConnectedNet N)
(π : V → ℝ) (hπ : IsPMFPWeight π) (hp : 2 ≤ (support π).card) (d : V → V → ℝ)
(hd : IsDistanceFunction d) (T : Finset V)
(hT : 2 * ((support π).card : ℝ) ≤ 3 * piSum π T)
(hsum : 1 / (2 * ((support π).card : ℝ)) ≤ ∑ u ∈ Tᶜ, π u * distFrom N d T u) :
∃ U : Finset V, 0 < piSum π U ∧ 0 < piSum π Uᶜ ∧
weightedRatio N π U ≤ 6 * totalWeight N d := by sorry
end LeightonRao.Product
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.