Theorem 9 — under ETH no algorithm for -colorability on supplied layouts or rank-decompositions
OpenSubspaceConv.Supplement.theorem_9fine-grained-complexitygraph-coloringp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1rank-width
Assume the Exponential Time Hypothesis, and fix . Deciding whether an -vertex graph is -colorable has no algorithm running in time
on graphs supplied with a linear layout of width at most . The same exclusion holds for supplied rank-decompositions.
This matches the exponent order of the algorithm of Bui-Xuan, Telle and Vatshelle for a fixed number of colors.
Formalization Note Algorithms are published multi-tape CookLevin machines on the input (code of , code of the layout or decomposition), deciding in the published DecidesIn sense; -colorability is Mathlib's SimpleGraph.Colorable c. The exclusion is for every function with and all constants : no machine runs within steps, the width of the supplied structure.
Differences from the source:
- encoding: ETH [IP01]; an algorithm and its running time (no machine named) → SubspaceConv.Supplement.ETH as a hypothesis; algorithms are published CookLevin multi-tape machines on fixed bit codes, time is their step count; reason: the standard 2^{δn} form of ETH; the paper leaves the machine model unspecified (p.4)
- generalization: 2^{o(r²)}N^{O(1)} time with a layout (resp. decomposition) of width at most r → for every g with g(r) ≤ ε r² eventually for each ε > 0, and every d, C: no machine within C·2^{g(w)}·(N+1)^d steps, w the actual width; reason: measuring time at the actual width w excludes every algorithm whose bound holds for all r ≥ w, and more; a one-sided o(r²) condition on g covers every two-sided one
- generalization: algorithms on all N-vertex graphs with a rank-decomposition → the excluded algorithm need only work on the inputs that carry a published BranchDecomp (N ≥ 2); reason: rank-decompositions are defined for |V| ≥ 2 only; excluding algorithms correct on fewer inputs is stronger and implies the paper's statement
Preamble
import Mathlib import Definitions.Def_CookLevin_Basic import Definitions.Def_CookLevin_Cost import Definitions.Def_CookLevin_Satisfiability import Definitions.Def_ApproxCliqueWidth_Certificate_CutRank import Definitions.Def_ApproxCliqueWidth_Certificate_BranchDecomp import Definitions.Def_SubspaceConv_Supplement_layoutWidth import Definitions.Def_SubspaceConv_Supplement_rdWidth import Definitions.Def_SubspaceConv_Supplement_graphCode import Definitions.Def_SubspaceConv_Supplement_ETH set_option autoImplicit false open Classical
Formal statement
namespace SubspaceConv.Supplement
/-- **Theorem 9**, Perles–Weinstein, *A Fast Algorithm for Subspace Convolution*, STOC 2027 submission manuscript (sha256 a8ffb1b4…604ab2), App. H, p.30 (PDF p.31). Assuming ETH, for every fixed `c ≥ 3`, deciding
`c`-colorability has no `2^{o(r²)} N^{O(1)}`-time algorithm on `N`-vertex graphs supplied with a
linear layout of width at most `r`. The same exclusion holds for supplied rank-decompositions.
**Formalization Note** ETH is `SubspaceConv.Supplement.ETH` (a hypothesis); algorithms, time and
"deciding" are as in `theorem_8` (published `CookLevin` machine, `DecidesIn` with verdict
`[G is c-colorable]`, Mathlib `SimpleGraph.Colorable`). `2^{o(r²)} N^{O(1)}` is excluded for every
`g : ℕ → ℝ` with `g(r)/r² → 0` (written: for every `ε > 0`, eventually `g(r) ≤ ε r²`) and every
`d, C`: no machine runs within `C · 2^{g(r)} · (N + 1)^d` steps, where `r` is the width of the supplied
layout (`layoutWidth`) or decomposition (`rdWidth`). The input is `graphCode G ++ layoutCode π`
(resp. `graphCode G ++ rdCode D`). -/
theorem theorem_9 (hETH : ETH) (c : ℕ) (hc : 3 ≤ c) (g : ℕ → ℝ)
(hg : ∀ ε : ℝ, 0 < ε → ∀ᶠ r : ℕ in Filter.atTop, g r ≤ ε * (r : ℝ) ^ 2) (d : ℕ) (C : ℝ) :
(¬ ∃ (M : CookLevin.Machine) (k γ : ℕ), CookLevin.TuringMachine k γ M ∧
∀ (N : ℕ) (G : SimpleGraph (Fin N)) [DecidableRel G.Adj] (π : Fin N ≃ Fin N), ∃ t : ℕ,
(t : ℝ) ≤ C * (2 : ℝ) ^ g (layoutWidth G π) * ((N : ℝ) + 1) ^ d ∧
CookLevin.DecidesIn M k (CookLevin.boolsToSymbols (graphCode G ++ layoutCode π)) [] t
(decide (G.Colorable c))) ∧
(¬ ∃ (M : CookLevin.Machine) (k γ : ℕ), CookLevin.TuringMachine k γ M ∧
∀ (N : ℕ) (G : SimpleGraph (Fin N)) [DecidableRel G.Adj]
(D : ApproxCliqueWidth.Certificate.BranchDecomp (Fin N)), ∃ t : ℕ,
(t : ℝ) ≤ C * (2 : ℝ) ^ g (rdWidth G D) * ((N : ℝ) + 1) ^ d ∧
CookLevin.DecidesIn M k (CookLevin.boolsToSymbols (graphCode G ++ rdCode D)) [] t
(decide (G.Colorable c))) := by sorry
end SubspaceConv.Supplement
Source
Perles, Weinstein, A Fast Algorithm for Subspace Convolution, STOC 2027 submission manuscript (sha256 a8ffb1b4e583122875209a3e25ee95aa3a7af933526e165d47c274634e604ab2), App. H, Theorem 9, p.30 (PDF p.31)