Lemma 4.4 — local interaction treewidth
ProvedStableMSR.Recovery.Supplement.local_treewidthclusteringp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1perturbation-stability
Let be the stable optimum of a finite metric instance with and . Put , , and , where is the sum of the large-cluster radii. For every aligned region with , its prescribed greedy-net interaction graph satisfies
for one absolute . Here and are the published parameters. This provides the local treewidth bound for randomized recovery.
Differences from the source:
- encoding: Finite ordered metric input and unordered exact-k partitions → Fin n points, real metric arrays, and finite sets of nonempty disjoint blocks; reason: Input-order relabelling preserves every source instance and partition; base published definitions are reused without extra conditions
- encoding: tw(H_W) at the greedy net and O(epsilon^-4) → TreewidthLE on the induced graph with vertex subtype N_W, and one positive constant before every epsilon and instance; reason: The graph has exactly the finite net vertices; a bounded-width finite decomposition is the finite-graph definition of treewidth, with no empty real infimum
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_Partitions import Definitions.Def_RobertsonSeymour1986_GM5_TreewidthLE set_option autoImplicit false open scoped Classical
Formal statement
namespace StableMSR.Recovery.Supplement
theorem local_treewidth :
∃ C : ℝ, 0 < C ∧
(∀ ε : ℝ, 0 < ε → ε < 1 → (widthBound ε : ℝ) ≤ C / ε ^ 4) ∧
∀ (n k : ℕ) (d : Point n → Point n → ℝ) (γ : ℝ) (O : Partition n),
1 ≤ k → k < n → IsMetricArray d → 1 < γ → γ < 2 → Stable d k γ O →
∀ W : Cluster n, Aligned O W → diameter d W ≤ densityScale d O (γ - 1) →
RobertsonSeymour1986.GM5.TreewidthLE
(interactionGraph d (largestRadius d O) W) (widthBound (γ - 1)) := by sorry
end StableMSR.Recovery.Supplement
Source
Shyam Ravichandran, Lev Reyzin, STOC 2027 submission #1010 (October 2026), Lemma 4.4, p. 11; PDF SHA256 8bb34b0b6d31458fe6fc0848c1fc82a6083f3e9ae672e748d24cf82d5289e53e