Corollary 9, p. 802 — either a component T of radius 1/2p² with π(T) ≥ 2p/3, or a cut of weighted ratio cost ≤ 36W log p
ProvedLeightonRao.Product.corollary_9Let be a capacitated network on , let be a PMFP node weighting with nodes of positive weight and , and let be a distance function with total weight . Then at least one of the following holds:
- there is a vertex set of radius at most with ;
- there is a cut with , and weighted ratio cost
Either outcome feeds Lemma 11: the cut finishes the argument directly, and the heavy small-radius set is the input of Lemma 10.
Formalization Note The page states the bound as . The constant is the one obtained by the computation in the proof of Corollary 4 (p. 799), to which the proof of Corollary 9 refers: in Lemma 8 gives cross capacity , and two sides of weight at least each give . "Find a component" is formalized as the existence of a vertex set with the stated radius and weight. The normalization is the standing assumption of §2.3.
import Mathlib import Definitions.Def_LeightonRao_Product_Setting
namespace LeightonRao.Product
theorem corollary_9 {V : Type} [Fintype V] [DecidableEq V] (N : Network V) (π : V → ℝ)
(hπ : IsPMFPWeight π) (hp : 2 ≤ (support π).card) (d : V → V → ℝ)
(hd : IsDistanceFunction d) :
(∃ T : Finset V, 2 * ((support π).card : ℝ) ≤ 3 * piSum π T ∧
HasRadiusLE N d T (1 / (2 * ((support π).card : ℝ) ^ 2))) ∨
(∃ U : Finset V, 0 < piSum π U ∧ 0 < piSum π Uᶜ ∧
weightedRatio N π U ≤
36 * totalWeight N d * Real.logb 2 ((support π).card : ℝ)) := by sorry
end LeightonRao.Product
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.