Theorem 6 — chromatic number, optimal coloring and chromatic polynomial in time on a rank-decomposition
OpenSubspaceConv.Supplement.theorem_6fine-grained-complexitygraph-coloringp2o-gran-per-chapterp2o-plan-paperp2o-v1rank-width
Let be the number of subspaces of (so ). Given an -vertex graph and a rank-decomposition of of width at most , one can compute
- the chromatic number ,
- an optimal coloring (a proper coloring with colors), and
- the chromatic polynomial (its ordinary integer coefficients)
in
bit operations.
This improves the exponent of Ganian, Hliněný and Obdržálek; Theorem 8 shows that, under ETH, the leading coefficient cannot be lowered.
Formalization Note Bit operations are steps of the published multi-tape CookLevin machine, with input the code of followed by the code of the decomposition. is for one constant , plus for the input length . Rank-decompositions are the published BranchDecomp, with width at most in the published WidthLE sense; they exist only for .
Differences from the source:
- reading: N^{O(N_2(r))} bit operations, for a rank-decomposition (a subcubic tree, of any size) → (N+1)^{c·N_2(r)} + (|x|+1)^c machine steps, |x| the input length; reason: a subcubic tree may carry any number of degree-two nodes, which the algorithm suppresses first (p.16), so reading the input can exceed every function of N; for decompositions with O(N) nodes the added term is (N+1)^{O(1)} and is absorbed, which is the paper's bound
- encoding: bit operations (no machine named) → steps of the published multi-tape CookLevin machine on fixed bit codes; reason: N^{O(N_2(r))} is robust under polynomial simulation between standard models
- reading: an N-vertex graph with a rank-decomposition (subcubic tree, leaves in bijection with V(G)) → the published BranchDecomp, a tree with at least two nodes, so graphs with N ≤ 1 have no rank-decomposition and are not inputs; reason: the standard convention (Oum) defines rank-decompositions for |V| ≥ 2 only; N ≤ 1 graphs are constant-size and trivially coloured
- encoding: N^{O(N_2(r))} → (N+1)^{c·N_2(r)}; reason: N ≥ 2 on every input, where N ≤ (N+1) ≤ N^2; same class of bounds
Preamble
import Mathlib import Definitions.Def_CookLevin_Basic import Definitions.Def_SubspaceConv_Mq import Definitions.Def_ApproxCliqueWidth_Certificate_CutRank import Definitions.Def_ApproxCliqueWidth_Certificate_BranchDecomp import Definitions.Def_SubspaceConv_Supplement_chromPoly import Definitions.Def_SubspaceConv_Supplement_graphCode import Definitions.Def_DetParamSVP_RunsWithin import Definitions.Def_HiddenPartition_Supplement_encodeLabels set_option autoImplicit false
Formal statement
namespace SubspaceConv.Supplement
/-- **Theorem 6** (Coloring on a supplied rank-decomposition), Perles–Weinstein, *A Fast Algorithm for Subspace Convolution*, STOC 2027 submission manuscript (sha256 a8ffb1b4…604ab2), p.16 (PDF p.17). Given an
`N`-vertex graph and a rank-decomposition of width at most `r`, its chromatic number, an optimal
coloring, and its chromatic polynomial can be computed in `N^{O(N_2(r))} = N^{2^{r²/4+O(1)}}` bit
operations.
**Formalization Note** Bit operations are steps of the published multi-tape `CookLevin` machine.
The input is `graphCode G ++ rdCode D` (unary `N`, adjacency bits, then the decomposition).
`N_2(r)` is the number of subspaces of `F_2^r`, the published `Mq (ZMod 2) r r`. `N^{O(N_2(r))}` is
`(N + 1)^{c · N_2(r)}` with one constant `c`. Three machines output, within that time plus
`(|x| + 1)^c` for the input length `|x|` (published `HiddenPartition.Supplement.OutputsWithin`): `χ(G)`
in binary; the code (published `encodeLabels`) of some proper coloring with exactly `χ(G)` colors; the integer coefficients of degrees `0, …, N` of `P_G`. The extra term
`(|x| + 1)^c` is the cost of reading the supplied decomposition: a subcubic tree may have any number
of degree-two nodes, which the paper's algorithm suppresses first (p.16); for decompositions with
`O(N)` nodes it is at most `(N + 1)^{c'}` and is absorbed into `N^{O(N_2(r))}`. A rank-decomposition
is a published `BranchDecomp`, which needs `N ≥ 2`. Width at most `r` is the published
`WidthLE (cutrk G) r`. -/
theorem theorem_6 :
∃ c : ℕ, ∃ (M₁ M₂ M₃ : CookLevin.Machine) (k₁ k₂ k₃ g₁ g₂ g₃ : ℕ),
CookLevin.TuringMachine k₁ g₁ M₁ ∧ CookLevin.TuringMachine k₂ g₂ M₂ ∧
CookLevin.TuringMachine k₃ g₃ M₃ ∧
∀ (N : ℕ) (G : SimpleGraph (Fin N)) [DecidableRel G.Adj]
(D : ApproxCliqueWidth.Certificate.BranchDecomp (Fin N)) (r : ℕ),
D.WidthLE (ApproxCliqueWidth.Certificate.cutrk G) (r : ℤ) →
HiddenPartition.Supplement.OutputsWithin M₁ k₁ (graphCode G ++ rdCode D)
(((N : ℝ) + 1) ^ (c * SubspaceConv.Mq (ZMod 2) r r) +
(((graphCode G ++ rdCode D).length : ℝ) + 1) ^ c)
(Nat.bits (chromNum G)) ∧
(∃ col : Fin N → Fin (chromNum G), (∀ u v, G.Adj u v → col u ≠ col v) ∧
HiddenPartition.Supplement.OutputsWithin M₂ k₂ (graphCode G ++ rdCode D)
(((N : ℝ) + 1) ^ (c * SubspaceConv.Mq (ZMod 2) r r) +
(((graphCode G ++ rdCode D).length : ℝ) + 1) ^ c)
(HiddenPartition.Supplement.encodeLabels col)) ∧
HiddenPartition.Supplement.OutputsWithin M₃ k₃ (graphCode G ++ rdCode D)
(((N : ℝ) + 1) ^ (c * SubspaceConv.Mq (ZMod 2) r r) +
(((graphCode G ++ rdCode D).length : ℝ) + 1) ^ c)
(polyCode N (chromPoly G)) := by sorry
end SubspaceConv.Supplement
Source
Perles, Weinstein, A Fast Algorithm for Subspace Convolution, STOC 2027 submission manuscript (sha256 a8ffb1b4e583122875209a3e25ee95aa3a7af933526e165d47c274634e604ab2), Theorem 6, p.16 (PDF p.17); running time p.17