Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Exact size-ordered treewidth table with polynomial enumeration bounds

Proved
StableMSR.Recovery.DecompositionSearch.polynomial_size_table_search

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

For every finite simple graph GGG on nnn vertices and nonnegative integer width bound www, the size-ordered tight-block table recognizes exactly the graphs of treewidth at most www. At size threshold mmm, it contains precisely the tight states (S,C)(S,C)(S,C) with ∣C∣≤m|C|\le m∣C∣≤m accepted by the recurrence at depth ∣C∣|C|∣C∣. The finite state universe satisfies

∣S∣≤n(w+1)(n+1)w.|\mathcal S|\le n(w+1)(n+1)^w.∣S∣≤n(w+1)(n+1)w.

Every state occurs in its unique interior-size layer. Across all nnn layers, count one visit per state, one eligibility test per vertex subset of size at most w+1w+1w+1, and one table probe per child of each eligible bag. This explicit enumeration tally is at most

(w+1)(w+2)(n+1)2w+3.(w+1)(w+2)(n+1)^{2w+3}.(w+1)(w+2)(n+1)2w+3.

The statement includes the empty graph. It gives exact table semantics and polynomial finite-enumeration counts for fixed www. It does not bound the work to construct components or boundaries, implement subset enumeration and indexing, or execute the table in the charged recovery interpreter.

Preamble
import Definitions.Def_StableMSR_DecompositionSearch_Table
import Definitions.Def_RobertsonSeymour1986_GM5_TreewidthLE
open scoped BigOperators
open StableMSR.Recovery.DecompositionSearch
Formal statement
theorem StableMSR.Recovery.DecompositionSearch.polynomial_size_table_search {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (w : ℕ) :
    (sizeTableRecognizes G w ↔ RobertsonSeymour1986.GM5.TreewidthLE G w) ∧
    (searchStates G w).card ≤
      Fintype.card V * (w+1) * (Fintype.card V+1)^w ∧
    (∑ m ∈ Finset.range (Fintype.card V), ∑ p ∈ layerStates G w m,
      (1 + (smallSets (V := V) (w+1)).card +
        ∑ B ∈ candidateBags w p.1 p.2, (children G B p.2).card)) ≤
      (w+1) * (w+2) * (Fintype.card V+1)^(2*w+3) ∧
    ∀ m (S C : Finset V),
      (S,C) ∈ sizeTable G w m ↔
        (S,C) ∈ searchStates G w ∧ C.card ≤ m ∧ accepts G w C.card S C := by sorry
Source
Size-ordered tabulation of the finite tight-block recurrence; follows the proved finite_decomposition_search theorem https://prove2.me/theorems/d4f2a14a-b18f-44f7-966a-d1411797cf17 in the Exact Sum-of-Radii Clustering under Any Constant Stability mission.

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