Lemma 5.2 (used in the proof of Theorem 1.3) — reduction to three-coloring
OpenFasterExactColoring.ThreeColor.Supplement.three_color_terminal_reductionFix a three-coloring solver with uniform charged worst-case time on all finite simple graphs. If it is deterministic, the following terminal solver is deterministic; if it is one-sided Monte Carlo, the terminal solver is one-sided Monte Carlo. There are one finite program and constants , fixed for this solver and its base, deciding every valid terminal restricted four-coloring instance within a polynomial in its full encoded size times
Here count the clique components of . The base is not specialized inside this lemma. Randomized success is at least , with no false positives and charged amplification of subcalls. This reduction supplies the terminal alternative using either the published Theorem 1.1 or the new Theorem 1.2.
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
- generalization: deterministic three-coloring solver and terminal reduction → the implication is stated both for deterministic and for one-sided Monte Carlo solvers; reason: the deterministic case is the full printed lemma; Section 5.7 also applies this reduction with Theorem 1.2, with charged amplification as required by Section 2
import Mathlib import Definitions.Def_FasterExactColoring_ThreeColor_Supplement_TerminalBounds set_option autoImplicit false
namespace FasterExactColoring.ThreeColor.Supplement
theorem three_color_terminal_reduction (mode : Mode) (τ : ℝ)
(h : ∃ (A : Program) (C : ℝ) (d : ℕ), 0 < C ∧ graphSolver mode 3 A C d τ) :
∃ (A : Program) (C : ℝ) (d : ℕ), 0 < C ∧
terminalSolver mode A C d (fun P _K => threeColorFactor P τ) := by sorry
end FasterExactColoring.ThreeColor.Supplement