Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Triangle two-list assignments and the explicit sublinear envelope

Definition
FasterExactColoring_ThreeColor_Supplement_TriangleLists

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

exact-algorithmsgraph-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1

Label the vertices of nnn disjoint triangles by (i,v)(i,v)(i,v), with i∈{0,…,n−1}i\in\{0,\ldots,n-1\}i∈{0,…,n−1} and v∈{0,1,2}v\in\{0,1,2\}v∈{0,1,2}. A two-list assignment gives each vertex a two-element subset of the four colors. Compatibility means membership at every vertex. The covered colorings are injective on each triangle and use the distinguished fourth color on every triangle. For c∈[3]c\in[3]c∈[3] and a triangle vertex xxx, the nine local candidates give [3]∖{c}[3]\setminus\{c\}[3]∖{c} at xxx and {c,4}\{c,4\}{c,4} elsewhere.

For n>0n>0n>0, put m=⌈ln⁡(n+2)⌉m=\lceil\ln(n+2)\rceilm=⌈ln(n+2)⌉, b=⌈n/m⌉b=\lceil n/m\rceilb=⌈n/m⌉, and

Bj=⌈(9/2)jjln⁡18⌉,h(n)=bln⁡(mln⁡18+1),h(0)=0.B_j=\lceil(9/2)^j j\ln18\rceil,\qquad h(n)=b\ln(m\ln18+1),\qquad h(0)=0.Bj​=⌈(9/2)jjln18⌉,h(n)=bln(mln18+1),h(0)=0.

The predicate of sublinearity requires h≥0h\ge0h≥0 and, for every ϵ>0\epsilon>0ϵ>0, a threshold NNN such that h(n)≤ϵnh(n)\le\epsilon nh(n)≤ϵn for all n≥Nn\ge Nn≥N. Finite list families and their complete encodings allow construction, coverage, size, and enumeration work to be asserted together in Lemma 5.3.

Formalization Note Natural ceilings and division implement the block sizes. The expression for mmm is guarded by max⁡(1,⋅)\max(1,\cdot)max(1,⋅), which changes no value because ⌈ln⁡(n+2)⌉≥1\lceil\ln(n+2)\rceil\ge1⌈ln(n+2)⌉≥1. The argument nnn counts triangles in this module.

Definition code
import Mathlib
import Definitions.Def_FasterExactColoring_ThreeColor_Execution

set_option autoImplicit false

namespace FasterExactColoring.ThreeColor.Supplement

abbrev TriangleVertex (n : ℕ) := Fin n × Fin 3
abbrev TwoLists (n : ℕ) := TriangleVertex n → Finset (Fin 4)

def localChoice (c x : Fin 3) (v : Fin 3) : Finset (Fin 4) :=
  if v = x then (Finset.univ.filter (fun a : Fin 4 => a.val < 3 ∧ a.val ≠ c.val))
  else {⟨c.val, Nat.lt_trans c.isLt (by decide)⟩, 3}

def triangleColoring {n : ℕ} (f : TriangleVertex n → Fin 4) : Prop :=
  ∀ i, Function.Injective (fun v => f (i,v)) ∧ ∃ v, f (i,v) = 3

def twoListsValid {n : ℕ} (L : TwoLists n) : Prop := ∀ v, (L v).card = 2
def compatible {n : ℕ} (f : TriangleVertex n → Fin 4) (L : TwoLists n) : Prop :=
  ∀ v, f v ∈ L v

def twoListsCode {n : ℕ} (L : TwoLists n) : List ℕ :=
  ((List.finRange n).flatMap (fun i => (List.finRange 3).flatMap (fun v =>
    vertexList (L (i,v)))))
where vertexList (X : Finset (Fin 4)) := X.card :: (X.sort (· ≤ ·)).map Fin.val

def triangleFamilyCode {n : ℕ} (F : List (TwoLists n)) : List ℕ :=
  F.length :: F.flatMap twoListsCode

noncomputable def coverBlockSize (n : ℕ) : ℕ := max 1 ⌈Real.log (n+2 : ℕ)⌉₊
noncomputable def coverBlockCount (n : ℕ) : ℕ :=
  (n + coverBlockSize n - 1) / coverBlockSize n
noncomputable def greedyBlockBound (j : ℕ) : ℕ :=
  ⌈(9/2 : ℝ)^j * j * Real.log 18⌉₊

/-- Explicit logarithmic envelope from the block construction, with its empty case. -/
noncomputable def coverEnvelope (n : ℕ) : ℝ :=
  if n = 0 then 0 else
    coverBlockCount n * Real.log ((coverBlockSize n : ℝ)*Real.log 18 + 1)

def sublinear (h : ℕ → ℝ) : Prop :=
  (∀ n, 0 ≤ h n) ∧ ∀ ε : ℝ, 0 < ε → ∃ N : ℕ, ∀ n ≥ N, h n ≤ ε*n

end FasterExactColoring.ThreeColor.Supplement
Source
Ryosuke Yamano, Tetsuo Shibuya, STOC 2027 submission #727 (October 2026), Lemma 5.3 and its proof, pp. 11–12 (PDF pp. 13–14)

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