Exact size-ordered treewidth table with polynomial enumeration bounds
ProvedStableMSR.Recovery.DecompositionSearch.polynomial_size_table_searchFor every finite simple graph on vertices and nonnegative integer width bound , the size-ordered tight-block table recognizes exactly the graphs of treewidth at most . At size threshold , it contains precisely the tight states with accepted by the recurrence at depth . The finite state universe satisfies
Every state occurs in its unique interior-size layer. Across all layers, count one visit per state, one eligibility test per vertex subset of size at most , and one table probe per child of each eligible bag. This explicit enumeration tally is at most
The statement includes the empty graph. It gives exact table semantics and polynomial finite-enumeration counts for fixed . 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.
import Definitions.Def_StableMSR_DecompositionSearch_Table import Definitions.Def_RobertsonSeymour1986_GM5_TreewidthLE open scoped BigOperators open StableMSR.Recovery.DecompositionSearch
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