Measurability of the query counter and almost sure regularity of exponential ranks
ProvedRGMISFast.query_measurable_rank_regularFor a finite ordered vertex set and a simple graph, the fresh-call counter Q of Procedure 1.1 is measurable as a function of the real ranks. Under independent Exp(1) ranks, almost surely all ranks are distinct and nonnegative.
This supplies the measure-theoretic interface for applying deterministic query-tree bounds. The measurability clause also covers ties, which are resolved by the fixed vertex order.
Preamble
import Mathlib import Definitions.Def_RGMISFast_run import Definitions.Def_RGMISFast_rankLaw open MeasureTheory ProbabilityTheory open scoped ENNReal set_option autoImplicit false
Formal statement
theorem RGMISFast.query_measurable_rank_regular {V : Type} [Fintype V] [LinearOrder V]
(G : SimpleGraph V) [DecidableRel G.Adj] (u : V) :
Measurable (fun r : V → ℝ => RGMISFast.Q G u r) ∧
(∀ᵐ r ∂(RGMISFast.rankLaw V), Function.Injective r ∧ ∀ v, 0 ≤ r v) := by sorrySource
Randomized Greedy MIS Is Fast at Every Node, Procedure 1.1 pp.2–3; standing rank assumptions §2 p.10; proof of Theorem 1.1 p.17. Auxiliary formalization lemma making those assumptions explicit.