Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The full measure and every Appendix D constraint

Definition
FasterExactColoring_ThreeColor_Supplement_Measure

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

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

The five stored real weights are ω1,ω2,ωc3,ωk3,ωk4\omega_1,\omega_2,\omega_{c3},\omega_{k3},\omega_{k4}ω1​,ω2​,ωc3​,ωk3​,ωk4​; the remaining degree weights are ω0=0\omega_0=0ω0​=0 and ωi=1\omega_i=1ωi​=1 for i≥3i\ge3i≥3. All weights are nonnegative. If C(P)\mathcal C(P)C(P) comprises components of G[U]G[U]G[U] other than complete triangles and four-cliques, the measure is

μ(P)=ωc3∣S∣+ωk3nK3+ωk4nK4+∑C∈C(P)∑v∈Cωdeg⁡C(v).\mu(P)=\omega_{c3}|S|+\omega_{k3}n_{K_3}+\omega_{k4}n_{K_4} +\sum_{C\in\mathcal C(P)}\sum_{v\in C}\omega_{\deg_C(v)}.μ(P)=ωc3​∣S∣+ωk3​nK3​​+ωk4​nK4​​+C∈C(P)∑​v∈C∑​ωdegC​(v)​.

The linear constraints are 0≤ωc3≤ω1≤ω2≤10\le\omega_{c3}\le\omega_1\le\omega_2\le10≤ωc3​≤ω1​≤ω2​≤1, 1−ω2≤ω2−ω1≤ω11-\omega_2\le\omega_2-\omega_1\le\omega_11−ω2​≤ω2​−ω1​≤ω1​, ωk3≤3ω2\omega_{k3}\le3\omega_2ωk3​≤3ω2​, and ωk4≤4\omega_{k4}\le4ωk4​≤4. Every multiset DDD in Table 1 imposes

∑(α,β)∈Dαr−β≤1.\sum_{(\alpha,\beta)\in D}\alpha r^{-\beta}\le1.(α,β)∈D∑​αr−β≤1.

All five instances j=4,…,8j=4,\ldots,8j=4,…,8 of row (7a) are included, using (M4,…,M8)=(2,5,5,7,10)(M_4,\ldots,M_8)=(2,5,5,7,10)(M4​,…,M8​)=(2,5,5,7,10) and δω=ω2−ωc3\delta_\omega=\omega_2-\omega_{c3}δω​=ω2​−ωc3​. Identical rows (13)/(14) and (17a)/(18b) share a constraint. These are conditional premises for the branching and composition lemmas, with no feasibility assumption in any headline theorem.

Definition code
import Mathlib
import Definitions.Def_FasterExactColoring_ThreeColor_Supplement_Restricted

set_option autoImplicit false

namespace FasterExactColoring.ThreeColor.Supplement

structure Weights where
  one : ℝ
  two : ℝ
  c3 : ℝ
  k3 : ℝ
  k4 : ℝ

def Weights.vertex (w : Weights) (i : ℕ) : ℝ :=
  if i = 0 then 0 else if i = 1 then w.one else if i = 2 then w.two else 1

def Weights.linearConstraints (w : Weights) : Prop :=
  0 ≤ w.c3 ∧ w.c3 ≤ w.one ∧ w.one ≤ w.two ∧ w.two ≤ 1 ∧
  1-w.two ≤ w.two-w.one ∧ w.two-w.one ≤ w.one ∧
  0 ≤ w.k3 ∧ 0 ≤ w.k4 ∧ w.k3 ≤ 3*w.two ∧ w.k4 ≤ 4

/-- Every Table 1 row, including all five j instances of (7a).
Repeated identical rows (13)/(14) and (17a)/(18b) share one constraint. -/
def branchingRows (w : Weights) : List (List (ℝ × ℝ)) :=
  let δ := w.two-w.c3
  [[(2,2*w.one-w.c3)],
   [(2,4*δ+2*w.c3)], [(5,5*δ+2*w.c3)], [(5,6*δ+2*w.c3)],
   [(7,7*δ+3*w.c3)], [(10,8*δ+3*w.c3)],
   [(1,3*δ+w.c3),(1,4*δ+w.c3),(1,5*δ+w.c3)],
   [(1,1+2*δ),(2,1+3*δ)],
   [(2,1+2*δ),(1,1+4*δ)],
   [(1,2+δ-w.c3),(1,1+3*δ),(1,2+3*δ-w.c3)],
   [(1,2+δ-w.c3),(1,1+3*δ),(1,2+2*δ-w.c3)],
   [(1,2+5*δ+w.c3-2*w.one),(1,2+2*δ+w.c3-w.k3)],
   [(1,2+4*δ+w.c3-2*w.one),(2,2+4*δ+2*w.c3-w.k3)],
   [(1,4+2*δ-w.c3-2*w.one),(1,2+2*δ-w.c3),(2,3+4*δ-2*w.one)],
   [(1,1+5*δ),(1,1-w.c3)],
   [(1,4-3*w.c3),(3,5-4*w.c3)],
   [(1,4-3*w.c3),(1,5-w.c3-w.k4)],
   [(2,5-4*w.c3),(1,6-2*w.c3-w.k4)],
   [(2,4-3*w.c3),(1,5-4*w.c3),(1,6-4*w.c3)],
   [(2,4-3*w.c3),(1,5-4*w.c3),(2,8-6*w.c3)],
   [(3,4-3*w.c3)],
   [(3,4-3*w.c3),(1,7-5*w.c3)],
   [(2,4-3*w.c3+6*(1-w.two)),(1,5-4*w.c3+3*(1-w.two)),(1,6-5*w.c3)],
   [(3,5-4*w.c3),(1,6-5*w.c3),(1,7-5*w.c3)],
   [(2,5-4*w.c3),(2,6-5*w.c3),(1,7-6*w.c3)]]

noncomputable def appendixD (r : ℝ) (w : Weights) : Prop :=
  w.linearConstraints ∧
  ∀ D ∈ branchingRows w, (D.map (fun p => p.1*r^(-p.2))).sum ≤ 1

noncomputable def measure {n : ℕ} (w : Weights) (P : Restricted n) : ℝ := by
  classical
  exact w.c3*P.S.card + w.k3*P.nClique 3 + w.k4*P.nClique 4 +
    ∑ C ∈ P.components.filter (fun C => ¬ clique P.G C 3 ∧ ¬ clique P.G C 4),
      ∑ v ∈ C, w.vertex (degreeIn P.G C v)

end FasterExactColoring.ThreeColor.Supplement
Source
Ryosuke Yamano, Tetsuo Shibuya, STOC 2027 submission #727 (October 2026), Section 5.7, Appendix D, Eqs. (10)–(11), Table 1, pp. 14–15, 23–24 (PDF pp. 16–17, 25–26)

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