The query counter equals the number of fresh trace events
ProvedRGMISFast.count_eq_fresh_traceFor every finite ordered graph, root u and real rank vector r,
This is an equality of the operational counter with the length of the fresh-event list, including multiplicity. It does not assert distinctness of fresh callees. It supplies the counting clause of Observation 2.2.
Preamble
import Definitions.Def_RGMISFast_tau open RGMISFast set_option autoImplicit false
Formal statement
theorem RGMISFast.count_eq_fresh_trace {V : Type*} [Fintype V] [LinearOrder V]
(G : SimpleGraph V) [DecidableRel G.Adj] (u : V) (r : V → ℝ) :
(((run G r u).2.trace.filter (fun e => e.fresh)).map (fun e => e.callee)).length = Q G u r := by sorrySource
Randomized Greedy MIS Is Fast at Every Node, Observation 2.2 p.11, Appendix B p.30; explicit operational correctness/counting clause. Generalized by omitting unused distinctness and nonnegativity assumptions.