Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 4.4 structural input: hereditary balanced separators within the width budget

Proved
StableMSR.Recovery.interaction_balanced_separators

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

clusteringgraph-theoryperturbation-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, ρ=εM/4\rho=\varepsilon M/4ρ=εM/4 the canonical density scale, and ωε=⌈49cε2+30cε⌉\omega_\varepsilon=\lceil49c_\varepsilon^2+30c_\varepsilon\rceilωε​=⌈49cε2​+30cε​⌉, where cε=1+80/ε+80/ε2c_\varepsilon=1+80/\varepsilon+80/\varepsilon^2cε​=1+80/ε+80/ε2. Let N⊆WN\subseteq WN⊆W be strictly 2R2R2R-separated and let diam⁡(W)≤ρ\operatorname{diam}(W)\le\rhodiam(W)≤ρ. The interaction graph on NNN joins distinct points at metric distance at most 8R8R8R.

There is one integer a≥0a\ge0a≥0, with 15a≤ωε15a\le\omega_\varepsilon15a≤ωε​, such that every vertex set U⊆NU\subseteq NU⊆N has a partition into three pairwise disjoint parts L,S,TL,S,TL,S,T satisfying

U=L∪S∪T,∣S∣≤a,3∣L∣≤2∣U∣,3∣T∣≤2∣U∣,U=L\cup S\cup T,\qquad |S|\le a,\qquad 3|L|\le2|U|,\quad3|T|\le2|U|,U=L∪S∪T,∣S∣≤a,3∣L∣≤2∣U∣,3∣T∣≤2∣U∣,

and there is no interaction edge between LLL and TTT.

This proves the hereditary balanced-separator conclusion in the linear-growth argument underlying Lemma 4.4. It includes empty vertex sets and disconnected induced subgraphs. Alignment of WWW and maximality of NNN are unnecessary for this structural conclusion. The statement does not assert the remaining separator-to-treewidth theorem or an executable decomposition algorithm.

Formalization Note. The formal statement explicitly gives the partition, absence of crossing edges, and natural-number cardinality inequalities. Balance is measured on the exclusive sides L,TL,TL,T, as in the proofs of Campbell et al., Lemmas 4–6. All clustering parameters use the existing canonical definitions; no new definition is required to state the theorem.

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_balanced_separators {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 : ∀ x ∈ N, ∀ y ∈ N, x ≠ y → 2 * largestRadius d O < d x y) :
    ∃ a : ℕ, 15 * a ≤ widthBound (γ - 1) ∧
      ∀ U : Finset N, ∃ L S T : Finset N,
        (Disjoint L S ∧ Disjoint L T ∧ Disjoint S T ∧ L ∪ S ∪ T = U) ∧
        (∀ x ∈ L, ∀ y ∈ T, ¬ (thresholdGraph d (8 * largestRadius d O) N).Adj x y) ∧
        S.card ≤ a ∧ 3 * L.card ≤ 2 * U.card ∧ 3 * T.card ≤ 2 * U.card := by sorry

end StableMSR.Recovery
Source
Ravichandran and Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, arXiv:2611.03547v1, https://arxiv.org/html/2611.03547v1, Section 4.3, Lemma 4.4 and Theorem 4.3; Table 2. Campbell, Distel, Gollin, Harvey, Hendrey, Hickingbotham, Mohar and Wood, Graphs of Linear Growth have Bounded Treewidth, Electronic Journal of Combinatorics 30(3) (2023), P3.1, DOI 10.37236/11657, https://www.combinatorics.org/ojs/index.php/eljc/article/download/v30i3p1/pdf/, Section 2, Lemmas 4–6 and the numerical part of the proof of Theorem 1 (pp. 3–5). This theorem proves the separator consequence; Dvorak–Norin's Theorem 3 is not assumed or claimed.

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