Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Progress and exact child accounting in tight-boundary decomposition search

Proved
StableMSR.Recovery.DecompositionSearch.tight_block_progress

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

Let a finite graph have a width-www tree decomposition. Let CCC be a component of G−SG-SG−S with exact external boundary S=NG(C)S=N_G(C)S=NG​(C), and suppose some bag contains SSS. There is a candidate bag S⊆B⊆S∪CS\subseteq B\subseteq S\cup CS⊆B⊆S∪C with at most w+1w+1w+1 vertices that meets CCC and is contained in an original bag. Its recursive child regions, the components DDD of G−BG-BG−B contained in CCC, satisfy the exact accounting identity

∣B∩C∣+∑D∣D∣=∣C∣.|B\cap C|+\sum_D |D|=|C|.∣B∩C∣+D∑​∣D∣=∣C∣.

Each child is a component after deleting its own exact boundary, that boundary is contained in BBB and in an original bag, and

∣NG(D)∣≤w,∣D∣<∣C∣.|N_G(D)|\le w,\qquad |D|<|C|.∣NG​(D)∣≤w,∣D∣<∣C∣.

Also ∣S∣≤w|S|\le w∣S∣≤w. This proves closure and strict progress of the intended finite-state decomposition search. The complete search recurrence, its reconstructed tree, and its instruction-level implementation are separate obligations.

Preamble
import Definitions.Def_StableMSR_TightBlockSearch
open StableMSR.Recovery.DecompositionSearch StableMSR.Recovery.Havens
open scoped BigOperators
Formal statement
theorem StableMSR.Recovery.DecompositionSearch.tight_block_progress {V : Type} [Fintype V] [DecidableEq V] {T : Type} [Fintype T] [DecidableEq T]
    {G : SimpleGraph V} {tree : SimpleGraph T} {bags : T → Finset V}
    (htd : RobertsonSeymour1986.GM5.IsTreeDecomposition G tree bags)
    (S C : Finset V) (w : ℕ) (hC : IsFlap G S C)
    (htight : boundary G C = S) (hroot : ∃ r, S ⊆ bags r)
    (hwidth : ∀ t, (bags t).card ≤ w+1) :
    ∃ B : Finset V,
      S ⊆ B ∧ B ⊆ S ∪ C ∧ B.card ≤ w+1 ∧ (B ∩ C).Nonempty ∧ S.card ≤ w ∧
      (∃ t, B ⊆ bags t) ∧
      (B ∩ C).card + (∑ D ∈ children G B C, D.card) = C.card ∧
      ∀ D ∈ children G B C,
        IsFlap G (boundary G D) D ∧ boundary G D ⊆ B ∧
        (boundary G D).card ≤ w ∧ D.card < C.card ∧
        ∃ r, boundary G D ⊆ bags r := by sorry
Source
Supporting lemma for Prove2Me Exact Sum-of-Radii Clustering under Any Constant Stability; tight-boundary connected-component decomposition search and finite cardinality charging.

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