Lemma 3, p. 797 — partition into components of radius ≤ Δ cutting at most 4W log n/Δ capacity
ProvedLeightonRao.Uniform.lemma_3Let be any network on nodes with arbitrary capacities, let be a distance function with total weight , and let . Then can be partitioned into components, each of radius at most , such that the total capacity of the edges connecting nodes in different components is at most
Here .
This region-growing decomposition is the main combinatorial tool of the paper: it trades the radius of the pieces against the capacity cut between them.
Formalization Note The radius is measured inside the component: each component has a centre from which every node of the component is reached by a walk inside the component of -length at most . No connectivity of and no lower bound on is assumed, as on the page ("any graph G").
import Definitions.Def_LeightonRao_Uniform_Dual set_option autoImplicit false open scoped BigOperators
namespace LeightonRao.Uniform
/-- Lemma 3, p. 797: a bounded-radius partition with controlled crossing capacity. -/
theorem lemma_3 {V : Type} [Fintype V] [DecidableEq V]
(N : Network V) (d : V → V → ℝ) (hd : IsDistanceFunction d)
(Δ : ℝ) (hΔ : 0 < Δ) :
∃ P : Finpartition (Finset.univ : Finset V),
(∀ S ∈ P.parts, HasRadiusLE N d S Δ) ∧
crossCap N P ≤ 4 * totalWeight N d * Real.logb 2 (Fintype.card V : ℝ) / Δ := by sorry
end LeightonRao.Uniform
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.