Proposition 7 — survival and blocked neighbours imply selection
ProvedRandomOrderCRS.proposition_7contention-resolutiononline-matchingp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilityrandom-order
Let have distinct coordinates. If survives, , and each satisfies , then .
This is the event that the lower bound on the selection probability counts.
Differences from the source:
- encoding: the statement on the sample space → pathwise, for injective ; reason: with a tie , the edge is not relevant for and yet may arrive first; ties have probability 0
Preamble
import Mathlib import Definitions.Def_RandomOrderCRS_ArrivalModel import Definitions.Def_RandomOrderCRS_SimpleBlocker
Formal statement
namespace RandomOrderCRS
variable {V : Type} [Fintype V] [DecidableEq V]
/-- Proposition 7, MacRury, Ma & Grammel, arXiv:2209.07520v2, p.19: "If e survives, |ℛ_e| ≤ 1, and
each f ∈ ℛ_e satisfies sbl_f, then e ∈ ℳ."
**Formalization Note.** Pathwise, for injective `Y`, i.e. almost surely. With a tie `Y_f = Y_e`, the
edge `f` is not relevant for `e` and yet may arrive first. -/
theorem proposition_7 (G : SimpleGraph V) [DecidableRel G.Adj] (Y : G.edgeSet → ℝ)
(S : G.edgeSet → Bool) (hY : Function.Injective Y) (e : G.edgeSet) (he : S e = true)
(hcard : (relevantSet G Y S e).card ≤ 1)
(hsbl : ∀ f ∈ relevantSet G Y S e, HasSimpleBlocker G Y S e f) :
e ∈ greedy G (arrivalOrder G Y) S := by sorry
end RandomOrderCRS
Source
MacRury, Ma & Grammel, On (Random-order) Online Contention Resolution Schemes for the Matching Polytope of (Bipartite) Graphs, arXiv:2209.07520v2, Proposition 7, p.19
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.