Lemma 14 — partition and lower-tail estimates
OpenLocalOccupancyIS.Glauber.Supplement.lemma_14graph-theoryindependent-setsp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Use the appendix parameters , integer , , . Assume and . Let be any finite graph on vertices of -density at most , and let for . If , then
If , then
These are finite bounds, including and the real cutoff , with no asymptotic assumption or independence assumption on the occupancy indicators. They supply the quantile estimates for chromatic local occupancy.
Differences from the source: none.
Preamble
import Definitions.Def_LocalOccupancyIS_Glauber_Supplement_AppendixParameters
Formal statement
namespace LocalOccupancyIS.Glauber.Supplement
/-- Lemma 14, pp.23–24: a finite statement, including the empty graph. -/
theorem lemma_14 (Δ : ℝ) (t : ℕ) (b : ℝ)
(hΔ : 3 ≤ Δ) (ht : 1 ≤ t) (hb : 0 ≤ b)
(hH : 1 ≤ appH Δ t b)
(hH₂ : 8 * Real.exp 1 * t / (4 * Real.exp 1)^(1/(t : ℝ)) ≤ appH Δ t b ^ 2)
{V : Type} [Fintype V] [DecidableEq V]
(F : SimpleGraph V) [DecidableRel F.Adj] (hdensity : Density F t b) :
let k : ℝ := Fintype.card V
let lam := appLam Δ t b
let c := appC Δ t b
(k ≤ appM Δ t b →
Real.log (partition F lam) ≥ c * lam * k ∧
∀ η : ℝ, 0 < η → η < 1 →
sizeLE F lam ((1-η)*c*lam*k) ≤ Real.exp (-η^2*c*lam*k/2)) ∧
(appM Δ t b < k → sizeLE F lam (appL Δ) ≤ (2 : ℝ)^(-appL Δ)) := by sorry
end LocalOccupancyIS.Glauber.Supplement
Source
Ewan Davies, Brian Tan, STOC 2027 submission #982 (October 2026), pp.23–24, Lemma 14, equations (32)–(34)