Lemma 5.3 (used in the proof of Theorem 1.3) — constructive triangle two-list cover
OpenFasterExactColoring.ThreeColor.Supplement.triangle_two_list_coverexact-algorithmsgraph-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
For every nonnegative integer , let be the vertices of pairwise disjoint triangles. There is one deterministic finite program constructing and enumerating a finite family of assignments of a two-element color list to every vertex. For every proper coloring that uses color on each triangle, some satisfies for every vertex. With , , and , for ,
The same program outputs the whole family, without repetitions, in charged time at most for fixed . Every list has exactly two colors. At this is the singleton family of the empty assignment. This is the deterministic covering tool needed for the CSP terminal bound.
Differences from the source:
- encoding: arbitrary vertex labels on disjoint triangles, with size (9/2)^n exp(o(n)) → canonical labels Fin n times Fin 3, duplicate-free encoded families and the explicit block envelope h; reason: finite relabeling changes no coloring or list; the proof supplies this same envelope and its sublinearity, and charged total enumeration implies the stated O* bound
Preamble
import Mathlib import Definitions.Def_FasterExactColoring_ThreeColor_Supplement_TriangleLists set_option autoImplicit false
Formal statement
namespace FasterExactColoring.ThreeColor.Supplement
theorem triangle_two_list_cover :
sublinear coverEnvelope ∧
∃ (A : Program) (C : ℝ) (d : ℕ), 0 < C ∧ deterministic A ∧
∀ n : ℕ, ∃ F : List (TwoLists n),
F.Nodup ∧ (∀ L ∈ F, twoListsValid L) ∧
(∀ f : TriangleVertex n → Fin 4, triangleColoring f → ∃ L ∈ F, compatible f L) ∧
(F.length : ℝ) ≤ (9/2 : ℝ)^n * Real.exp (coverEnvelope n) ∧
runWithin A [n] (C*(n+1 : ℕ)^d*(F.length+1 : ℕ))
(fun y => y = triangleFamilyCode F) := by sorry
end FasterExactColoring.ThreeColor.Supplement
Source
Ryosuke Yamano, Tetsuo Shibuya, STOC 2027 submission #727 (October 2026), Lemma 5.3, p. 11 (PDF p. 13)