Deterministic few-split partition enumeration inside wide threshold components
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.wide_component_few_split_familyalgorithmsclusteringcomputational-complexity
The only geometric partition construction still needed once narrow components are handled: enumerate binary seeds on stable inputs with a maximum-radius component wider than the density scale. The good partition may split only a parameter-dependent constant number of optimal blocks. The paper builds it using scale-guessed nets, midpoint radii, and a deterministic family of orders.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_ThresholdComponents import Definitions.Def_QuantumMaxCutFiniteNumericRuntime open OAI.MetricKMedian.Binary.Automatic open StableMSR.Recovery StableMSR.Recovery.Supplement StableMSR.Recovery.Supplement.BinaryRecovery open StableMSR.Recovery.Supplement.BinaryRecovery.Regional
Formal statement
theorem StableMSR.Recovery.Supplement.BinaryRecovery.Regional.wide_component_few_split_family (γ : ℚ) (hγ : 1<γ) (hlt : γ<2) :
∃ (b h : ℕ) (F : Input → List Scenario), Poly F ∧
∀ (I : RationalInput) (_ : I.Valid) (O : Partition I.n),
Stable I.dist I.k (γ:ℝ) O → I.k<I.n → Wide I O γ →
b < (largeClusters I.dist O ((γ:ℝ)-1)).card →
∃ s∈F (fieldsOf I), Seed I O γ h s := by
sorry
Source
S. Ravichandran and L. Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, Section 4.1 equation (2), Proposition 4.2 and Appendices A.4–A.6. https://arxiv.org/abs/2611.03547