Compatible tree labelings represent precisely the allowed assignments on all bags
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.MenuTree.tree_labels_and_global_assignmentsalgorithmsclusteringdynamic-programming
Choose matching menu indices independently for a global plan. Conversely, edge compatibility and running intersection make the value read at the first bag independent of the occurrence. That readback is allowed and agrees on every bag.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_BagMenuEncoding open StableMSR.Recovery.Supplement.BinaryRecovery.Regional open StableMSR.Recovery.Supplement.BinaryRecovery.Regional.MenuTree
Formal statement
theorem StableMSR.Recovery.Supplement.BinaryRecovery.Regional.MenuTree.tree_labels_and_global_assignments (t : ℕ) (z : Data) (ids : Block) (scope : ℕ→Block) (emit : ℕ→Plan→Pack) (cost : Block→ℚ)
(hl : GoodLayout z.1 (ids.map scope) t z.2.2) :
(∀ s, AllowedPlan z.1 z.2.1 s → ∃ x, Legal (encodeMenus t z ids scope emit cost) x ∧ RepresentsPlan t z x s) ∧
∀ x, Legal (encodeMenus t z ids scope emit cost) x →
AllowedPlan z.1 z.2.1 (unpack t z x) ∧ RepresentsPlan t z x (unpack t z x) := by
sorry
Source
Ravichandran and Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, arXiv:2611.03547, Appendix A.6, tree-decomposition dynamic program. Explicit binary witness formulation.