Lemma 5.4 (used in the proof of Theorem 1.3) — CSP terminal algorithm
OpenFasterExactColoring.ThreeColor.Supplement.csp_terminal_algorithmexact-algorithmsgraph-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
There are one deterministic program and constants deciding every valid terminal restricted four-coloring instance with its valid maximal star packings in a polynomial in the encoded input size times
Here are the computed clique counts, , and is the published exact CSP root. All cases are retained:
The explicit from Lemma 5.3 acts on the covered triangles and is uniformly sublinear in the original order, since . The factor is retained. This is the CSP member of the terminal algorithm portfolio.
Differences from the source:
- encoding: terminal instances after the two maximal-star preprocessing steps → valid restricted instances with supplied valid inclusion-maximal star packings, all structural counts computed from them; reason: the explicit finite input includes the graph, restrictions and packings; its size is polynomial in the original vertex count
- encoding: an exp(o(n)) overhead from the triangle-cover construction → exp(h(a_0)) with h the explicit block envelope of Lemma 5.3; reason: exactly a_0 triangles require that cover, and a_0 at most n/3 makes this uniformly subexponential in original order
Preamble
import Mathlib import Definitions.Def_FasterExactColoring_ThreeColor_Supplement_TerminalBounds set_option autoImplicit false
Formal statement
namespace FasterExactColoring.ThreeColor.Supplement
theorem csp_terminal_algorithm :
∃ (A : Program) (C : ℝ) (d : ℕ), 0 < C ∧
terminalSolver .det A C d (fun P K => cspTerminalFactor P K) := by sorry
end FasterExactColoring.ThreeColor.Supplement
Source
Ryosuke Yamano, Tetsuo Shibuya, STOC 2027 submission #727 (October 2026), Lemma 5.4, p. 12 (PDF p. 14)