Measurability of the active attached-extension count
ProvedRGMISFast.Ncount_measurableprobabilityrandomized-greedy-mis
For every finite graph, seed set , extension size , and real time , the number of attached -sets whose union with is active at is a measurable function of the rank vector. This is the measurability clause required for the lower-integral formulation of Lemma 5.3. No rank-law or graph-degree assumptions are needed.
Preamble
import Mathlib import Definitions.Def_RGMISFast_Y import Definitions.Def_RGMISFast_condLaw set_option autoImplicit false open MeasureTheory ProbabilityTheory open scoped ENNReal open RGMISFast
Formal statement
theorem RGMISFast.Ncount_measurable {V : Type*} [Fintype V] [LinearOrder V]
(G : SimpleGraph V) [DecidableRel G.Adj] (A : Finset V) (k : ℕ) (t : ℝ) :
Measurable (fun r : V → ℝ => Ncount G A k t r) := by sorrySource
Dalirrooyfard, Makarychev, Mitrović, Ramachandran, Randomized Greedy MIS Is Fast at Every Node, §5.2, Lemma 5.3 and its proof, printed pp.20–21 (PDF pp.22–23). The short-window arrival derivative, contraction of A, Lemma 5.1, and Jensen inequality precede the final inverse-power integration.