Lemma 4.4 structural input: hereditary balanced separators within the width budget
ProvedStableMSR.Recovery.interaction_balanced_separatorsConsider a -stable MSR instance with and , and put . Let be the largest optimal radius, the canonical density scale, and , where . Let be strictly -separated and let . The interaction graph on joins distinct points at metric distance at most .
There is one integer , with , such that every vertex set has a partition into three pairwise disjoint parts satisfying
and there is no interaction edge between and .
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 and maximality of 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 , 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.
import Definitions.Def_StableMSR_Recovery_Geometry import Definitions.Def_StableMSR_Recovery_Parameters set_option autoImplicit false open scoped Classical
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