Proposition 4.2 — bounded-fhw cores and bounded incidence degeneracy give
OpenSparseIncidenceHom.WidthComparison.Supplement.proposition_4_2coresfractional-hypertree-widthhomomorphismsp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a class of finite relational structures of bounded incidence degeneracy, i.e. . If has bounded fractional hypertree width, i.e. , then
Here asks, for finite relational structures over the same signature with , whether . The proposition is unconditional and requires no recursive enumerability; it gives the implication (i)⇒(iv) of Theorem 4.3.
Formalization Note The core condition is required for every core map of every member, i.e. for every endomorphic image of minimum domain cardinality; cores are unique up to isomorphism and exist for every finite structure.
Differences from the source:
- encoding: a class of finite relational structures, A ∈ 𝒜 → a set of explicit structures, the promise A ∈ 𝒜 read up to isomorphism with a well-formed member, and every class condition read over the well-formed members (an ill-formed code denotes no structure); reason: Lean convention for classes; width and degeneracy conditions are isomorphism invariant
- encoding: PTIME → deterministic multi-tape machines of the published Cook–Levin cost model, correct on promise instances within c·(|x|+1)^d steps; reason: standard machine model
- encoding: ‖A‖, explicit tuple lists → a self-delimiting unary encoding of signature, domain size and tuple lists; reason: polynomially related to any standard encoding, so PTIME is unchanged
Preamble
import Mathlib import Definitions.Def_SparseIncidenceHom_WidthComparison_Supplement_Problems
Formal statement
namespace SparseIncidenceHom.WidthComparison.Supplement
open SparseIncidenceHom.WidthComparison
/-- Lanzinger, STOC 2027 submission #662, Proposition 4.2, p. 16. Unconditional; no recursive
enumerability. -/
theorem proposition_4_2 (𝒜 : StructureClass) (hdeg : BoundedStructureDegeneracy 𝒜)
(hcore : CoreBoundedFhw 𝒜) :
InPTIME (homStruct 𝒜) := by sorry
end SparseIncidenceHom.WidthComparison.Supplement
Source
Matthias Lanzinger, STOC 2027 submission #662 (October 2026), p. 16, Proposition 4.2; proof p. 16