Lemma 8, p. 802 — partition G so that components meeting 𝒫 have radius ≤ Δ and the cut capacity is at most 4W log p/Δ
ProvedLeightonRao.Product.lemma_8Let be a capacitated network on , let be a distance function with total weight , let be a node weighting whose support has nodes, and let . Then can be partitioned into components so that
- every component containing a node of has radius at most (measured by walks inside the component), and
- the total capacity of the edges joining different components is at most
This is the region-growing decomposition of Lemma 3 with replaced by the number of weighted nodes; it is the source of the (hence ) factor in Theorem 7.
Formalization Note The page says "any ", but the bound divides by ; as in Lemma 3 we require . The page allows any , but for the bound is and the statement fails on a single edge (its weighted endpoint must have a component of small radius, so the edge is cut); we require , which is the only case Theorem 7 uses. is (footnote 3). The existence of the partition is formalized; its polynomial-time construction is not.
import Mathlib import Definitions.Def_LeightonRao_Product_Setting
namespace LeightonRao.Product
theorem lemma_8 {V : Type} [Fintype V] [DecidableEq V] (N : Network V) (d : V → V → ℝ)
(hd : IsDistanceFunction d) (π : V → ℝ) (hp : 2 ≤ (support π).card) (Δ : ℝ) (hΔ : 0 < Δ) :
∃ P : Finpartition (Finset.univ : Finset V),
(∀ S ∈ P.parts, (∃ x ∈ S, π x ≠ 0) → HasRadiusLE N d S Δ) ∧
crossCap N P ≤ 4 * 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.