Proposition 9 — second-order minimization property of
ProvedRandomOrderCRS.proposition_9attenuationcontention-resolutionp2o-gran-per-chapterp2o-plan-paperp2o-v1real-analysis
For and ,
Equality holds at . This is the property that makes a single neighbour the worst case in Lemma 3.
Differences from the source:
- encoding: for all → for all ; reason: the printed expression is at , and the argument needs only the points below 1
Preamble
import Mathlib import Definitions.Def_RandomOrderCRS_Attenuation open Real
Formal statement
namespace RandomOrderCRS
/-- Proposition 9 (Second-order minimization), MacRury, Ma & Grammel, arXiv:2209.07520v2, p.20, for
`a = a₁`: `a′(x)/a(x) + 4/(1 − x) − 2(1 − exp(x − 1))/(exp(x − 1) − x) ≤ 0`.
**Formalization Note.** Stated on `[0, 1)`. The paper prints `x ∈ [0, 1]`, but the expression is
`0/0` at `x = 1`, and its use in the proof of Lemma 3 (ec16–ec17) needs only `z_h > 0`. -/
theorem proposition_9 :
∀ t ∈ Set.Ico (0 : ℝ) 1,
deriv a₁ t / a₁ t + 4 / (1 - t) - 2 * (1 - exp (t - 1)) / (exp (t - 1) - t) ≤ 0 := by sorry
end RandomOrderCRS
Source
MacRury, Ma & Grammel, On (Random-order) Online Contention Resolution Schemes for the Matching Polytope of (Bipartite) Graphs, arXiv:2209.07520v2, Proposition 9, p.20; §C.5, ec17
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.