Lemma 5.2: expected number of active root-connected sets,
ProvedRGMISFast.lemma_5_2graph-theorylocal-computationp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1probabilityrandomized-greedy-mis
Let be a finite simple graph with root and i.i.d. Exp(1) ranks. For every and every integer ,
where is the number of root-connected sets active at time with exactly vertices other than .
The bound replaces the worst-case count of root-connected sets by ; it holds on every finite simple graph.
Formalization Note The expectation is the Lebesgue integral of under the product Exp(1) law, stated together with the measurability of .
Differences from the source:
- generalization: E[Y_k(t)] ≤ (e/t)^k → measurability of Y_k(t), and its lower Lebesgue integral ≤ (e/t)^k; reason: the added measurability clause is true and makes the lower integral the expectation; dropping it gives (19)
Preamble
import Mathlib import Definitions.Def_RGMISFast_Y import Definitions.Def_RGMISFast_rankLaw set_option autoImplicit false open MeasureTheory ProbabilityTheory open scoped ENNReal
Formal statement
namespace RGMISFast
/-- Lemma 5.2 (Expected Number of Active Root-Connected Sets; Dalirrooyfard, Makarychev, Mitrović, Ramachandran, *Randomized Greedy MIS Is Fast at Every Node*,
STOC 2027 submission (manuscript sha256 e93cdfec…), p.18): for every `t > 0` and
every integer `k ≥ 0`, `E[Y_k(t)] ≤ (e/t)^k` (19).
**Formalization Note** Every finite simple graph and every root, no degree bound. The expectation
is the lower Lebesgue integral of `Y_k(t)` under the i.i.d. Exp(1) rank law, plus a measurability
clause. -/
theorem lemma_5_2 {V : Type*} [Fintype V] [LinearOrder V] (G : SimpleGraph V)
[DecidableRel G.Adj] (u : V) (t : ℝ) (ht : 0 < t) (k : ℕ) :
Measurable (fun r : V → ℝ => Y G u k t r) ∧
∫⁻ r, (Y G u k t r : ℝ≥0∞) ∂(rankLaw V) ≤ ENNReal.ofReal ((Real.exp 1 / t) ^ k) := by sorry
end RGMISFast
Source
Dalirrooyfard, Makarychev, Mitrović, Ramachandran, Randomized Greedy MIS Is Fast at Every Node, STOC 2027 submission (manuscript sha256 e93cdfecc03618969d5f2ecf8171c6f84c528edcc473b2f864299e555f823664), Lemma 5.2, eq. (19), p.18 (PDF p.20)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.