Independent exponential ranks are almost surely distinct and nonnegative
ProvedRGMISFast.ae_rank_regularFor any finite vertex set V, sample the ranks independently from Exp(1). Then
This supplies the rank-regularity clause needed when passing from deterministic query-tree estimates to probability bounds. No graph or vertex ordering is required.
Preamble
import Definitions.Def_RGMISFast_rankLaw open MeasureTheory ProbabilityTheory set_option autoImplicit false
Formal statement
theorem RGMISFast.ae_rank_regular (V : Type) [Fintype V] :
∀ᵐ r ∂(RGMISFast.rankLaw V), Function.Injective r ∧ ∀ v, 0 ≤ r v := by sorrySource
Randomized Greedy MIS Is Fast at Every Node, §2 p.10 (standing assumptions on ranks), and proof of Theorem 1.1 p.17. Explicit measure-theoretic justification of the almost-sure rank assumptions.