Theorem 16 — correspondence coloring with constant one
OpenLocalOccupancyIS.Glauber.Supplement.theorem_16Let , integer and vary along any family, and put
There is an absolute , independent of every family, and graph, such that if and , then eventually every finite graph of degree at most and hereditary neighborhood -density at most satisfies
Both specializations are included: if is fixed and , or if is fixed and , then, for every , eventually
All eventual bounds quantify over every graph satisfying the hypotheses, including empty graphs and graphs with low-degree vertices. Correspondence coloring quantifies over arbitrary partial matchings and independent list relabelings. There is no minimum-degree assumption, no supplied coloring framework axiom, and no assumed chromatic bound. The finite colorable list size in the conclusion also guarantees the bound is attained by a valid integer size.
Differences from the source:
- encoding: the absolute uniform upper O-bound and both o(1) specializations for χ_c → an absolute A preceding all admissible sequences, and eventual finite colorable-list-size bounds; each specialization is quantified for every ζ>0; reason: the list-size witness is equivalent to the upper bound for the least universally colorable size and avoids converting an infinite infimum to zero
import Definitions.Def_LocalOccupancyIS_Glauber_Supplement_Correspondence
namespace LocalOccupancyIS.Glauber.Supplement
/-- Theorem 16, pp.24–25, including both leading-constant-one specializations.
The error constant is chosen before all families; ColoringBound quantifies over
all partial-matching correspondence assignments, and asserts an actual finite bound. -/
theorem theorem_16 :
(∃ A : ℝ, 0 < A ∧
∀ (Δ : ℕ → ℝ) (t : ℕ → ℕ) (b : ℕ → ℝ), AppAdmissible Δ t b →
∀ᶠ i in Filter.atTop,
∀ {V : Type} [Fintype V] [DecidableEq V],
∀ (G : SimpleGraph V) [DecidableRel G.Adj],
RealDegreeBound G (Δ i) → HereditaryDensity G (t i) (b i) →
ColoringBound G ((1 + A * appError (Δ i) (t i) (b i)) *
Δ i / appH (Δ i) (t i) (b i))) ∧
(∀ (b : ℝ), 0 ≤ b → ∀ (Δ : ℕ → ℝ) (t : ℕ → ℕ),
(∀ i, 3 ≤ Δ i ∧ 1 ≤ t i) →
Filter.Tendsto Δ Filter.atTop Filter.atTop →
Filter.Tendsto (fun i => (t i : ℝ) * Real.log (Real.log (Δ i)) /
Real.log (Δ i)) Filter.atTop (nhds 0) →
∀ ζ : ℝ, 0 < ζ → ∀ᶠ i in Filter.atTop,
∀ {V : Type} [Fintype V] [DecidableEq V],
∀ (G : SimpleGraph V) [DecidableRel G.Adj],
RealDegreeBound G (Δ i) → HereditaryDensity G (t i) b →
ColoringBound G ((1+ζ) * Δ i / Real.log (Δ i))) ∧
(∀ (t : ℕ), 1 ≤ t → ∀ (Δ b : ℕ → ℝ),
(∀ i, 3 ≤ Δ i ∧ 0 ≤ b i) →
Filter.Tendsto Δ Filter.atTop Filter.atTop →
Filter.Tendsto (fun i => Real.log (b i + 1) / Real.log (Δ i))
Filter.atTop (nhds 0) →
∀ ζ : ℝ, 0 < ζ → ∀ᶠ i in Filter.atTop,
∀ {V : Type} [Fintype V] [DecidableEq V],
∀ (G : SimpleGraph V) [DecidableRel G.Adj],
RealDegreeBound G (Δ i) → HereditaryDensity G t (b i) →
ColoringBound G ((1+ζ) * Δ i / Real.log (Δ i))) := by sorry
end LocalOccupancyIS.Glauber.Supplement