Lemma 6.1 — unbounded clique embedding power makes - W[1]-hard
OpenSparseIncidenceHom.WidthComparison.Supplement.lemma_6_1clique-embeddingsp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1parameterized-complexityw1-hardness
Let be a recursively enumerable hypergraph class of unbounded clique embedding power, i.e. for every some has . Then - is -hard under FPT many-one reductions: every parameterized problem in reduces to - by a deterministic FPT many-one reduction mapping yes-instances to yes-instances and no-instances to no-instances of the promise problem.
The lemma is unconditional. It is the first half of the hardness clause of Theorem 1.4.
Formalization Note is the definition item SparseIncidenceHom.WidthComparison.Supplement.Widths; promise W[1]-hardness is the published DetParamSVP.PromiseW1Hard.
Differences from the source:
- generalization: every member of a hypergraph class is nonempty and connected (p. 7: "We assume input hypergraphs are nonempty and connected") → classes may contain empty or disconnected hypergraphs (every H_A of a structure, published FiniteHypergraph without InputHypergraph); reason: on a class of nonempty connected hypergraphs the Lean statement is the source's; widths, incidence degeneracy, boundedness of α and Hom decompose over connected components, and the empty hypergraph has every width 0
- encoding: a recursively enumerable hypergraph class with membership up to isomorphism → a set of hypergraph codes (n, edge lists) that is an r.e. predicate, H belonging to it when some code describes H up to isomorphism; reason: Lean convention for classes; the same classes
- encoding: W[1]-hard under FPT many-one reductions → published DetParamSVP.PromiseW1Hard; every problem FPT-reducible to p-Clique reduces by a deterministic FPT many-one promise reduction on Cook–Levin machines; reason: standard definition on a fixed machine model
- encoding: ‖H_A‖, the length of the list of edges as vertex lists → Σ_e (|e|+1); reason: each is bounded by a computable function of the other, so W[1]-hardness 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, Lemma 6.1, p. 21. Unconditional. -/
theorem lemma_6_1 (𝓗 : HypergraphClass) (hre : IsREClass 𝓗)
(hunb : ¬ BoundedWidth 𝓗 (fun _ H => cliqueEmbeddingPower H)) :
DetParamSVP.PromiseW1Hard (pHomHyp 𝓗) := by sorry
end SparseIncidenceHom.WidthComparison.Supplement
Source
Matthias Lanzinger, STOC 2027 submission #662 (October 2026), p. 21, Lemma 6.1; proof pp. 21–23