Lemma 17 — and
ProvedGaussLocalMaxColoring.Main.lemma_17gaussian-roundinggraph-coloringp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1randomized-algorithmssemidefinite-programming
Let be a strict vector 3-coloring of a graph (unit vectors in , on edges), and . Then for every ,
where , ( for an empty neighborhood, with ) and is the standard normal upper tail.
Differences from the source:
- generalization: §4 standing assumptions: G is the 3-colorable input graph with every degree ≤ n^β, with a strict vector 3-coloring → any graph G on Fin n with a strict vector 3-coloring, any dimension d; reason: the proof uses only Equation (3); the §4 setting is an instance
- encoding: vertex set V with a fixed total order breaking ties → V = Fin n with its order; reason: Lean convention; every finite ordered vertex set is relabelled this way
- encoding: vectors in R^d, g ∼ N(0, I_d), P_g → Space d = EuclideanSpace ℝ (Fin d), any d, Mathlib stdGaussian (gaussProb); reason: Lean convention; same instances
- encoding: M_F(x) = −∞ when N_F(x) = ∅ → nbrMax in WithBot ℝ (⊥), tailOver c ⊥ = 1 = Φ̄(−∞); reason: an empty maximum must not default to 0
Preamble
import Mathlib import Definitions.Def_RecGaussColoring_Main_Rounding import Definitions.Def_GaussLocalMaxColoring_Main_Basic open scoped RealInnerProductSpace open Filter MeasureTheory ProbabilityTheory open RecGaussColoring.Main open Classical
Formal statement
namespace GaussLocalMaxColoring.Main
/-- **Lemma 17** (p. 17, PDF 19). Let `{v_x}` be a strict vector 3-coloring of `G`, `F ⊆ V` and
`x ∈ F`. Then for every `a ∈ ℝ`, `p_F(x) = E_g[Φ̄(M_F(x)/√3)]` and
`P_g[M_F(x) ≤ a] ≤ p_F(x)/Φ̄(a/√3)`; `M_F(x) = −∞` (`⊥`) and `Φ̄(−∞) = 1` when `N_F(x) = ∅`. -/
theorem lemma_17 {n d : ℕ} (G : SimpleGraph (Fin n)) (v : Fin n → Space d)
(hv : StrictVectorColoring G v) (F : Finset (Fin n)) (x : Fin n) (hx : x ∈ F) (a : ℝ) :
pLocal G v F x =
∫ g, tailOver (Real.sqrt 3) (nbrMax G v F x g) ∂(stdGaussian (Space d)) ∧
gaussProb {g : Space d | nbrMax G v F x g ≤ ((a : ℝ) : WithBot ℝ)} ≤
pLocal G v F x / PhiTail (a / Real.sqrt 3) := by sorry
end GaussLocalMaxColoring.Main
Source
Deguchi, Kawarabayashi, Yoneda, Yoneda (2026), An O(n^0.1537)-Coloring Algorithm for 3-Colorable Graphs, arXiv:2610.35859 (SHA-256 9917b0a1…), Lemma 17, printed p. 17 (PDF 19)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.