Lemma 3.8 — global components of small clusters
ProvedStableMSR.Recovery.small_cluster_componentsclusteringp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1perturbation-stabilitysum-of-radii
Assume , , and that is the unique optimum of a -stable instance. Put , , and . Then
Every other global component contains only points in large optimal clusters, whose radii are at least . Singleton small clusters are included. This separates the forced small-cluster components from the components left for candidate coverage.
Differences from the source:
- encoding: An arbitrary finite real metric space with fixed input order and unordered clusters → Points are Fin n; clusters and unordered partitions are finite sets; metric arrays are Mathlib metric distances; reason: Relabelling preserves every finite ordered instance, all distance values, and every unordered partition
Preamble
import Definitions.Def_StableMSR_Recovery_Geometry set_option autoImplicit false open scoped Classical
Formal statement
namespace StableMSR.Recovery
theorem small_cluster_components {n : ℕ} (d : Point n → Point n → ℝ) (hd : IsMetricArray d)
(k : ℕ) (hk : 1 ≤ k ∧ k ≤ n) (γ : ℝ) (hγ : 1 < γ ∧ γ < 2) (hkn : k < n)
(O : Partition n) (hO : Stable d k γ O) :
(∀ C ∈ smallClusters d O (γ - 1),
C ∈ components d (2 * smallThreshold d O (γ - 1)) Finset.univ) ∧
(∀ K ∈ components d (2 * smallThreshold d O (γ - 1)) Finset.univ,
K ∉ smallClusters d O (γ - 1) → K ⊆ (largeClusters d O (γ - 1)).biUnion id) := by sorry
end StableMSR.Recovery
Source
Shyam Ravichandran, Lev Reyzin, STOC 2027 submission #1010 (October 2026), Lemma 3.8, p. 6; PDF SHA256 8bb34b0b6d31458fe6fc0848c1fc82a6083f3e9ae672e748d24cf82d5289e53e
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.