Measurability of the active-set destruction-rate sum
ProvedRGMISFast.dsSum_measurableprobabilityrandomized-greedy-mis
For every finite graph, fixed root , size , and time , the finite count is measurable as a function of the ranks. The sum ranges over -sets for which is root-connected and active at ; is computed in the graph active at . This is the second measurability clause of Equation (20), stated independently of a probability law.
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.dsSum_measurable {V : Type*} [Fintype V] [LinearOrder V]
(G : SimpleGraph V) [DecidableRel G.Adj] (u : V) (k : ℕ) (s : ℝ) :
Measurable (fun r : V → ℝ => dsSum G u k s r) := by sorrySource
Dalirrooyfard, Makarychev, Mitrović, Ramachandran, Randomized Greedy MIS Is Fast at Every Node, §5.1, proof of Lemma 5.2, printed pp.18–19 (PDF pp.20–21), polynomial-in-exp(-s) observation and the short-window destruction calculation yielding Equation (20). Auxiliary finite exponential-basis reformulation.