Theorem 1.4 (companion theorem; not used in the proof of the goal) — randomized four-coloring
OpenFasterExactColoring.ThreeColor.Supplement.randomized_four_coloringexact-algorithmsgraph-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
There is one one-sided Monte Carlo finite program deciding whether any finite simple undirected graph on vertices admits a proper four-coloring. For fixed , independent of the graph and its order, every coin tape halts within charged time
The program rejects every no-instance and accepts each yes-instance with probability at least . The domain includes empty and disconnected graphs of arbitrary degrees. No certificate feasibility or terminal preprocessing condition is assumed. This is the randomized four-coloring companion result.
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_Certificates set_option autoImplicit false
Formal statement
namespace FasterExactColoring.ThreeColor.Supplement
theorem randomized_four_coloring :
∃ (A : Program) (C : ℝ) (d : ℕ), 0 < C ∧
graphSolver .rand 4 A C d (16933/10000 : ℝ) := by sorry
end FasterExactColoring.ThreeColor.Supplement
Source
Ryosuke Yamano, Tetsuo Shibuya, STOC 2027 submission #727 (October 2026), Theorem 1.4, p. 1 (PDF p. 3)