Lemma 4.12 — The non-increasing recursion F_i(ε) ≤ a log(1/ε) F_{i−1}(ε^a) has the exact triangular-exponent solution.
ProvedGreedyColoringLCA969.LowerBound.Supplement.lemma_4_12graph-theorylocal-computationp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be an integer and a real number. For each , let be non-increasing. For every in this domain assume
Then, throughout the same domain,
The exponent is the exact triangular integer, and is real exponentiation. This solves the recurrence used in the finite-label query analysis.
Differences from the source:
- encoding: indices 1 through t and recurrence evaluated at epsilon^a → indices Fin t and recurrence quantified over domain elements epsilon,eta with eta=epsilon^a; reason: index i denotes source index i+1; for a>=1 and 0<epsilon<=1/2 the real power epsilon^a is in the domain, so every required recurrence evaluation occurs
Preamble
import Definitions.Def_GreedyColoringLCA969_LowerBound_GraphBasics open scoped ENNReal BigOperators open MeasureTheory Classical set_option autoImplicit false
Formal statement
namespace GreedyColoringLCA969.LowerBound.Supplement
theorem lemma_4_12 (t : ℕ) (ht : 1 ≤ t) (a : ℝ) (ha : 1 ≤ a)
(F : Fin t → Set.Ioc (0 : ℝ) (1 / 2) → ℕ+)
(hmono : ∀ i, Antitone (F i))
(hbase : ∀ (i : Fin t), i.val = 0 → ∀ ε, (F i ε : ℝ) ≤ a * log2 (1 / ε.val))
(hrec : ∀ (i j : Fin t), j.val + 1 = i.val →
∀ (ε η : Set.Ioc (0 : ℝ) (1 / 2)), η.val = ε.val ^ a →
(F i ε : ℝ) ≤ a * log2 (1 / ε.val) * (F j η : ℝ)) :
∀ (i : Fin t), i.val + 1 = t → ∀ ε,
(F i ε : ℝ) ≤ a^(t * (t + 1) / 2) * (log2 (1 / ε.val))^t := by sorry
end GreedyColoringLCA969.LowerBound.Supplement
Source
Zi Song Yeoh, Krzysztof Onak, Dragos-Florian Ristache, STOC 2027 submission #969 (October 2026), p. 22 (PDF 23), Lemma 4.12