Eq. (20):
ProvedRGMISFast.eq_20graph-theorylocal-computationp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1probabilityrandomized-greedy-mis
Let be a finite simple graph with root , fix , and a root rank , and let the other ranks be i.i.d. Exp(1). For let
Then for every ,
where ranges over the sets for which is counted by and is computed in the active graph .
With Lemma 5.1 this yields the differential inequality (21) that proves Lemma 5.2.
Formalization Note The conditional law fixes the root's rank at . and the right-hand side are integrals of real-valued counts, and the measurability of both counts at every time is stated. The derivative is the derivative of within at (one-sided at ).
Differences from the source:
- reading: E[· | r(u∗) = ρ] → integral under
rootLaw u ρ(root rank ρ, other ranks i.i.d. Exp(1)); reason: the conditional law stated in the proof (p.18) - reading: f′(s) for s < t (f differentiable on [0, t]) → HasDerivWithinAt f (−g s) on [0, t] at every s ∈ [0, t); reason: the proof computes the derivative at s < t inside [0, t]; at s = 0 it is one-sided
- generalization: the expectations f(s) and E[Σ_W d_s(W)] → Bochner integrals plus measurability of Y_k(s) and Σ_W d_s(W) for every s; reason: the added measurability clauses are true and exclude a junk value of the integrals; dropping them gives (20)
Preamble
import Mathlib import Definitions.Def_RGMISFast_Y import Definitions.Def_RGMISFast_condLaw set_option autoImplicit false open MeasureTheory ProbabilityTheory open scoped ENNReal
Formal statement
namespace RGMISFast
/-- Eq. (20) (Dalirrooyfard, Makarychev, Mitrović, Ramachandran, *Randomized Greedy MIS Is Fast at Every Node*,
STOC 2027 submission (manuscript sha256 e93cdfec…), Proof of Lemma 5.2, pp.18–19): fix `k ≥ 1`, `t > 0` and a root rank
`ρ ≥ t`; conditionally on `r(u∗) = ρ`, let `f(s) = E[Y_k(s) | r(u∗) = ρ]` for `0 ≤ s ≤ t`. Then
`f′(s) = −E[Σ_W d_s(W) | r(u∗) = ρ]`, where `W` ranges over the sets for which `{u∗} ∪ W` is
counted by `Y_k(s)` and `d_s(W)` is `d(W)` computed in `G_s`.
**Formalization Note** The conditional law is `rootLaw u ρ` (root rank `ρ`, other ranks i.i.d.
Exp(1)). `f` and `s ↦ E[Σ_W d_s(W)]` are Bochner integrals of real-valued counts; measurability
of both integrands at every time is stated, so neither integral can be a junk value. The
derivative is taken within `[0, t]` at every `s ∈ [0, t)` (the proof's short-window computation
fixes `s < t`; at `s = 0` it is one-sided). -/
theorem eq_20 {V : Type*} [Fintype V] [LinearOrder V] (G : SimpleGraph V) [DecidableRel G.Adj]
(u : V) (k : ℕ) (hk : 1 ≤ k) (t ρ : ℝ) (ht : 0 < t) (htρ : t ≤ ρ) :
(∀ s : ℝ, Measurable (fun r : V → ℝ => (Y G u k s r : ℝ))) ∧
(∀ s : ℝ, Measurable (fun r : V → ℝ => (dsSum G u k s r : ℝ))) ∧
∀ s ∈ Set.Ico (0 : ℝ) t,
HasDerivWithinAt (fun s' : ℝ => ∫ r, (Y G u k s' r : ℝ) ∂(rootLaw u ρ))
(-(∫ r, (dsSum G u k s r : ℝ) ∂(rootLaw u ρ))) (Set.Icc 0 t) s := by sorry
end RGMISFast
Source
Dalirrooyfard, Makarychev, Mitrović, Ramachandran, Randomized Greedy MIS Is Fast at Every Node, STOC 2027 submission (manuscript sha256 e93cdfecc03618969d5f2ecf8171c6f84c528edcc473b2f864299e555f823664), Proof of Lemma 5.2, eq. (20), pp.18–19 (PDF pp.20–21)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.