Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 4.4: linear growth of the local interaction graph

Proved
StableMSR.Recovery.interaction_subgraph_radius_growth

by lreyzin · Nov 13, 2026 · Mathlib 0df444a (Lean v4.33.1)

clusteringperturbation-stabilitysum-of-radii

Consider a γ\gammaγ-stable MSR instance with 1<γ<21<\gamma<21<γ<2 and 1≤k<n1\le k<n1≤k<n, and put ε=γ−1\varepsilon=\gamma-1ε=γ−1. Let RRR be the largest optimal radius and ρ=εM/4\rho=\varepsilon M/4ρ=εM/4, where MMM is the sum of the large-cluster radii. Let WWW have diameter at most ρ\rhoρ, and let N⊆WN\subseteq WN⊆W be strictly 2R2R2R-separated. Join net points whose metric distance is at most 8R8R8R.

Let HHH be any nonempty subgraph with vertices in NNN. If there is a vertex x∈Hx\in Hx∈H from which every vertex of HHH is reachable by a walk of length at most an integer j≥1j\ge1j≥1 entirely inside HHH, then

∣V(H)∣≤(1+80ε+80ε2)j.|V(H)|\le\left(1+\frac{80}{\varepsilon}+\frac{80}{\varepsilon^2}\right)j.∣V(H)∣≤(1+ε80​+ε280​)j.

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 WWW 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.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me