Lemma A.1 — inner and outer net counts
ProvedStableMSR.Recovery.Supplement.net_countsclusteringp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1perturbation-stability
Let be a -stable optimum, , , , and . Suppose , where and . For every wide -component and , the input-order greedy net satisfies
Both bounds concern the same prescribed net. They control the number of inner centers and potentially relevant outer centers in the splitting estimate.
Differences from the source:
- encoding: Finite ordered metric input and unordered exact-k partitions → Fin n points, real metric arrays, and finite sets of nonempty disjoint blocks; reason: Input-order relabelling preserves every source instance and partition; base published definitions are reused without extra conditions
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_Partitions set_option autoImplicit false open scoped Classical
Formal statement
namespace StableMSR.Recovery.Supplement
theorem net_counts {n k : ℕ} (d : Point n → Point n → ℝ) (γ L : ℝ) (O : Partition n)
(hk : 1 ≤ k) (hkn : k < n) (hd : IsMetricArray d) (hγ : 1 < γ ∧ γ < 2)
(hO : Stable d k γ O)
(hL : sigma * largestRadius d O ≤ L ∧ L ≤ densityScale d O (γ - 1))
(U : Cluster n) (hU : U ∈ wideComponents d (largestRadius d O) L)
(x : Point n) (hx : x ∈ U) :
L / (sigma * largestRadius d O) ≤
((greedyNet d (largestRadius d O) U ∩ ball d x (L / 32)).card : ℝ) ∧
((greedyNet d (largestRadius d O) U ∩ ball d x (L / 4)).card : ℝ) ≤
12 * L / ((γ - 1) ^ 2 * largestRadius d O) := by sorry
end StableMSR.Recovery.Supplement
Source
Shyam Ravichandran, Lev Reyzin, STOC 2027 submission #1010 (October 2026), Lemma A.1, p. 16; PDF SHA256 8bb34b0b6d31458fe6fc0848c1fc82a6083f3e9ae672e748d24cf82d5289e53e