Every vertex has a unique bounded introduction depth
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.BlockSearch.unique_introduction_depthsalgorithmsclusteringdynamic-programming
Along a live trace the cardinality of the nonempty interior decreases at each descent. Its final live level is the unique level at which the traced vertex is introduced, and is strictly below the input-list length.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_BlockTraceSemantics open StableMSR.Recovery StableMSR.Recovery.Supplement.BinaryRecovery open StableMSR.Recovery.Supplement.BinaryRecovery.Regional open StableMSR.Recovery.Supplement.BinaryRecovery.Regional.BlockSearch open StableMSR.Recovery.DecompositionSearch RobertsonSeymour1986.GM5
Formal statement
theorem StableMSR.Recovery.Supplement.BinaryRecovery.Regional.BlockSearch.unique_introduction_depths (z : GraphInput) (rs : List Rule) (h : TraceFacts z rs) : ∃ level : Vertex z→ℕ,HomeLevels z rs level := by sorry
Source
Constructive binary implementation of the tight-block recurrence in StableMSR.Recovery.DecompositionSearch.finite_decomposition_search, https://prove2.me/theorems/d4f2a14a-b18f-44f7-966a-d1411797cf17.