Theorem 1.2 (companion theorem; not used in the proof of the goal) — randomized three-coloring
OpenFasterExactColoring.ThreeColor.Supplement.randomized_three_coloringexact-algorithmsgraph-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
There is one one-sided Monte Carlo program deciding whether any finite simple undirected graph on vertices is three-colorable. There are constants and , independent of and , for which every coin tape halts with charged work at most
The program never accepts a graph without a proper three-coloring and accepts each three-colorable graph with probability at least . Input and output costs are included. This is the randomized companion to the published deterministic goal, with no degree, connectivity, preprocessing or certificate hypothesis.
Differences from the source:
- encoding: arbitrary finite simple undirected graphs and O* running time → Fin n graph inputs and one charged finite program with C>0 and d in Nat before every n and G; reason: finite labels and uniform polynomial overhead express the same decision bound; empty graphs are included
- encoding: one-sided Monte Carlo with a fixed positive input-independent success probability → one-sided acceptance probability at least 1/2 with the charged worst-case bound on all coin tapes; reason: independent constant repetition normalizes success; further charged polynomial amplification handles all subcalls without changing an exponential base
Preamble
import Mathlib import Definitions.Def_FasterExactColoring_ThreeColor_Supplement_TerminalBounds import Definitions.Def_FasterExactColoring_ThreeColor_Supplement_Certificates set_option autoImplicit false
Formal statement
namespace FasterExactColoring.ThreeColor.Supplement
theorem randomized_three_coloring :
∃ (A : Program) (C : ℝ) (d : ℕ), 0 < C ∧
graphSolver .rand 3 A C d (13159/10000 : ℝ) := by sorry
end FasterExactColoring.ThreeColor.Supplement
Source
Ryosuke Yamano, Tetsuo Shibuya, STOC 2027 submission #727 (October 2026), Theorem 1.2, p. 1 (PDF p. 3)