Lemma 45 — uniform improved Gaussian cover threshold drift
ProvedGaussLocalMaxColoring.Main.lemma_45Let ν=437/2000 and ψ(s)=√3√(1−s²) for s≤ν, and ψ(s)=√3(1−νs)/√(1−ν²) for s≥ν. For every 0≤U≤√H, (√3/2)ψ(√(H−U²))≥U/2+1/1500, with the exact Section 5 constant H. Differences from the source: none; ν and ψ are expanded as local let-bindings in the formal statement.
Preamble
import Mathlib import Definitions.Def_GaussLocalMaxColoring_Main_Section5
Formal statement
namespace GaussLocalMaxColoring.Main
theorem lemma_45 (U : ℝ) (hU0 : 0 ≤ U) (hUH : U ≤ Real.sqrt H5) :
let ν : ℝ := 437 / 2000
let ψ : ℝ → ℝ := fun s =>
if s ≤ ν then Real.sqrt 3 * Real.sqrt (1-s^2)
else Real.sqrt 3 * (1-ν*s) / Real.sqrt (1-ν^2)
U / 2 + 1 / 1500 ≤ Real.sqrt 3 / 2 * ψ (Real.sqrt (H5-U^2)) := by sorry
end GaussLocalMaxColoring.Main
Source
Deguchi, Kawarabayashi, Yoneda (2026), An O(n^0.1537)-Coloring Algorithm for 3-Colorable Graphs, fixed STOC paper 155, SHA-256 9917b0a118555de058fe15a67d4540cda7e2214a8968b4c5dbf0e01f93e65b4b, Lemma 45, printed pp.48–49 (PDF50–51).