Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.4 — binary-list interpolation in O∗(2n−b/(K2))O^*(2^{n-b/\binom K2})O∗(2n−b/(2K​)) deterministic time

Open
KColoringFaster.ListBootstrap.Supplement.theorem_4_4

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

exponential-time-algorithmslist-coloringp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1

Fix a finite palette P⊆NP\subseteq\mathbb NP⊆N of size K=∣P∣≥2K=|P|\ge 2K=∣P∣≥2. For a list-coloring instance (G,L)(G,L)(G,L) over PPP (every L(v)⊆PL(v)\subseteq PL(v)⊆P) on nnn vertices, let bbb be the number of vertices whose list has size at most two. Then:

  1. list colorability of (G,L)(G,L)(G,L) can be decided deterministically, without error, in time
O∗(2 n−b/(K2));O^*\Big(2^{\,n-b/\binom{K}{2}}\Big);O∗(2n−b/(2K​));
  1. a list coloring of (G,L)(G,L)(G,L), when one exists, can be found deterministically within the same time bound.

The exponent is the real number n−b/(K2)n-b/\binom K2n−b/(2K​). Equivalently the bound is O∗(2n−bqK b)O^*(2^{n-b}q_K^{\,b})O∗(2n−bqKb​) with qK=21−1/(K2)<2q_K=2^{1-1/\binom K2}<2qK​=21−1/(2K​)<2: each vertex with a short list costs a factor qKq_KqK​ instead of 222. In the paper this is the black-box solver of the warm-up reduction (Lemma 4.2) and is stated independently of it.

Formalization Note The program and polynomials may depend on PPP (the palette is fixed first) but not on the instance, on nnn or on bbb. Time O∗(T)O^*(T)O∗(T) means a coin-free run of cost at most ⌈p(σ)⋅T⌉\lceil p(\sigma)\cdot T\rceil⌈p(σ)⋅T⌉ with registers of at most q(σ)q(\sigma)q(σ) bits, σ\sigmaσ the input bit size. The recovered coloring is output as the list of the colors c(0),…,c(n−1)c(0),\dots,c(n-1)c(0),…,c(n−1).

Differences from the source:

  • encoding: O*(·) running time → one coin-free program of the integer RAM with cost at most ⌈p(σ)·2^{n−b/C(K,2)}⌉ and registers of at most q(σ) bits; reason: unit cost with polynomially bounded registers equals bit cost up to polynomial factors
  • encoding: colors of an abstract palette P → P a finite set of natural numbers; reason: any finite palette is numbered
  • encoding: vertex set V(G) → Fin n; reason: any n-vertex graph is relabeled by 0, …, n − 1
  • encoding: "a coloring can be recovered" → the output is the list c(0), …, c(n − 1) of a list coloring whenever one exists; reason: a fixed output format for the recovered coloring
  • generalization: nonempty lists → lists may be empty; reason: instances with an empty list are not colorable, and the source's instances are included
Preamble
import Mathlib
import Definitions.Def_KColoringFaster_ListBootstrap_Instances
import Definitions.Def_KColoringFaster_ListBootstrap_Supplement_DetTime

open Classical
Formal statement
namespace KColoringFaster.ListBootstrap.Supplement

open KColoringFaster.ListBootstrap

/-- Theorem 4.4, p. 19 (Binary-list interpolation). Fix a palette `P` of size `K ≥ 2`. List
coloring of instances over `P` on `n` vertices, `b` of which have lists of size at most two, is
decided deterministically in time `O*(2^{n − b / (K choose 2)})`, and a coloring is recovered
within the same bound. -/
theorem theorem_4_4 (P : Finset ℕ) (hP : 2 ≤ P.card) :
    DetDecides encList (OverPalette P) ListColorable
        (fun I => (2 : ℝ) ^ ((I.n : ℝ) - (binaryCount I : ℝ) / ((P.card.choose 2 : ℕ) : ℝ))) ∧
      DetFinds encList (OverPalette P) IsColoringOutput
        (fun I => (2 : ℝ) ^ ((I.n : ℝ) - (binaryCount I : ℝ) / ((P.card.choose 2 : ℕ) : ℝ))) := by sorry

end KColoringFaster.ListBootstrap.Supplement
Source
Zamir, k-Coloring is Faster than Computing the Chromatic Number, arXiv:2607.25973 (revision of 9 Sep 2026; STOC 2027 submission #73; source.pdf sha256 624fee950171ffcd169c0aa08efcb25b2de77b3219fcbdf9227d838138d1003e), p. 19, Theorem 4.4

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me