Lemma 21 — with probability all empirical local-maximum frequencies are within , hence on
ProvedGaussLocalMaxColoring.Main.lemma_21gaussian-roundinggraph-coloringp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1randomized-algorithmssemidefinite-programming
Consider one trial of Algorithm 2 on a graph with vectors , , any target and samples per level, . With probability at least over its i.i.d. standard Gaussian samples: for every level at which is constructed (no sampled set of size at levels ) and every , ; and (in particular) for every such and every .
Differences from the source:
- generalization: §4 high-degree setting (Table 2 parameters, strict vector 3-coloring) → any graph, any vectors, any δ ∈ (0, 1), any T, with R = ⌈32δ⁻²log(8nℓ)⌉ ("by the choice of R"); reason: the proof uses only Hoeffding and the formula for R; Table 2 (high degree), Table 3 and Appendix A are instances
- encoding: "with probability at least 3/4 over the samples used to construct the cores … in particular …" → the product Gaussian law (trialLaw) of the event "first claim ∧ second claim"; reason: the second claim follows from the first on every sample; stating both inside the event keeps both
- 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
Preamble
import Mathlib import Definitions.Def_GaussLocalMaxColoring_Main_Iterative open scoped RealInnerProductSpace open Filter MeasureTheory ProbabilityTheory open RecGaussColoring.Main open Classical
Formal statement
namespace GaussLocalMaxColoring.Main
/-- **Lemma 21** (p. 19, PDF 21), for one trial of Algorithm 2 with any graph, any vectors, any
`δ ∈ (0, 1)`, any `T` and `R = ⌈32 δ^{−2} log(8nℓ)⌉`: with probability at least `3/4` over the
`ℓR` Gaussian samples, `|p̂_j(x) − p_{F_{j−1}}(x)| ≤ δ/8` for every level `j` at which `F_j` is
constructed and every `x ∈ F_{j−1}`, and (in particular) `p_{F_{j−1}}(x) < δ` for every such `j`
and every `x ∈ F_j`. -/
theorem lemma_21 {n d : ℕ} (G : SimpleGraph (Fin n)) (v : Fin n → Space d) (δ : ℝ)
(hδ0 : 0 < δ) (hδ1 : δ < 1) (T : ℕ) :
(trialLaw n d ⌈32 * δ⁻¹ ^ 2 * Real.log (8 * n * (numLevels n : ℝ))⌉₊).real
{ω | ∀ j, 1 ≤ j → j ≤ numLevels n → Constructed G v δ T ω j →
(∀ x ∈ cores G v δ ω (j - 1),
|phat G v δ ω j x - pLocal G v (cores G v δ ω (j - 1)) x| ≤ δ / 8) ∧
(∀ x ∈ cores G v δ ω j, pLocal G v (cores G v δ ω (j - 1)) x < δ)} ≥ 3 / 4 := 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 21, printed p. 19 (PDF 21)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.