Corollary 20, p. 808 — a large component with two small radii
ProvedLeightonRao.ShortPaths.corollary_20graph-partitionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1short-path-flowsparsest-cut
Let be a connected capacitated graph with vertices, total capacity , and uniform sparsest cut value . Let be a nonnegative symmetric distance function whose total weight satisfies . Then some component contains at least two thirds of the vertices, and one center reaches each vertex of by a path within with
This is the large low-radius region needed to connect short paths between arbitrary pairs.
Formalization Note The printed fraction is read as , as used in its proof. The additional is necessary because the printed edge radius divides by .
Preamble
import Mathlib import Definitions.Def_LeightonRao_ShortPaths_Setting
Formal statement
namespace LeightonRao.ShortPaths
/-- Corollary 20, p. 808. -/
theorem corollary_20 {V : Type} [Fintype V] [DecidableEq V]
(N : Network V) (hn : 2 ≤ Fintype.card V) (hconn : IsConnectedNet N)
(d : V → V → ℝ) (hd : IsDistanceFunction d)
(hW : 0 < totalWeight N d)
(hWS : totalWeight N d ≤ minCut N /
(36 * Real.logb 2 (Fintype.card V : ℝ))) :
∃ T : Finset V,
2 * (Fintype.card V : ℝ) ≤ 3 * (T.card : ℝ) ∧
HasRadii N d T
(totalCap N / (2 * totalWeight N d * (Fintype.card V : ℝ) ^ 2))
(1 / (2 * (Fintype.card V : ℝ) ^ 2)) := by sorry
end LeightonRao.ShortPaths
Source
Leighton and Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, J. ACM 46 (1999), p. 808, Corollary 20 and footnote 8
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.