Lemma 4.4: linear growth of the local interaction graph
ProvedStableMSR.Recovery.interaction_subgraph_radius_growthclusteringperturbation-stabilitysum-of-radii
Consider a -stable MSR instance with and , and put . Let be the largest optimal radius and , where is the sum of the large-cluster radii. Let have diameter at most , and let be strictly -separated. Join net points whose metric distance is at most .
Let be any nonempty subgraph with vertices in . If there is a vertex from which every vertex of is reachable by a walk of length at most an integer entirely inside , then
This proves the linear-growth input in Lemma 4.4, with graph radius measured inside the subgraph. Applying Campbell's treewidth theorem is a separate obligation. Alignment of and maximality of the separated net are not needed for this growth estimate.
Preamble
import Definitions.Def_StableMSR_Recovery_Geometry import Definitions.Def_StableMSR_Recovery_Parameters set_option autoImplicit false open scoped Classical
Formal statement
namespace StableMSR.Recovery
theorem interaction_subgraph_radius_growth {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)
(W N : Cluster n) (hNW : N ⊆ W)
(hdiam : diameter d W ≤ densityScale d O (γ - 1))
(hsep : ∀ a ∈ N, ∀ b ∈ N, a ≠ b → 2 * largestRadius d O < d a b)
(H : (thresholdGraph d (8 * largestRadius d O) N).Subgraph)
(hHN : H.verts ⊆ (N : Set (Point n)))
(x : H.verts) (j : ℕ) (hj : 1 ≤ j)
(hwalk : ∀ y : H.verts, ∃ p : H.coe.Walk x y, p.length ≤ j) :
((Finset.univ.filter (fun y => y ∈ H.verts)).card : ℝ) ≤
growthConstant (γ - 1) * (j : ℝ) := by sorry
end StableMSR.Recovery
Source
Ravichandran and Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, https://arxiv.org/html/2611.03547v1, Section 4.3, Lemma 4.4, density-to-linear-growth portion of the proof; Lemma 3.9; Table 2 for the growth constant.