Lemma 5.5 — no negative alternating even cycle at any state of non-bipartite VRM
OpenBipartiteVRM.Competitive.Supplement.lemma_5_5competitive-analysismatching-with-delaysnon-bipartite-matchingonline-algorithmsp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix , any tie rule and any MPMD input with in any metric space. At every state of non-bipartite VRM, every simple -alternating even cycle satisfies
where is the TA distance .
By Lemma 5.3 this makes Steps 1–2 compute genuine minimum augmenting paths throughout the run, so the algorithm is valid.
Differences from the source:
- encoding: a finite request set R with |R| = 2m in any metric space, locations and arrival times a_v ≥ 0 that may coincide → the published MatchingDelays.Linear.Instance n X (labels 0..n−1 in nondecreasing arrival order, any MetricSpace X) with Even n, m = n/2; reason: every finite input can be relabeled in arrival order (simultaneous arrivals in any order); labels give the algorithm no future data, and repeated locations and arrival times are allowed
- encoding: an arbitrary but fixed rule for ties among simultaneous events and among the choices of N_uv and v in Steps 1 and 2 → every TieRule, a View-and-history selector over the nonempty finite option sets; reason: the rule sees only received data and its own history; every statement quantifies over all such rules
- encoding: every state of non-bipartite VRM → the state after every step index k of the run; reason: the run's states are exactly these; the statement covers all of them
Preamble
import Definitions.Def_BipartiteVRM_Competitive_Supplement_Specifications set_option autoImplicit false
Formal statement
namespace BipartiteVRM.Competitive.Supplement
open MatchingDelays.Linear (Instance Edge)
/-- Lemma 5.5, p. 16: every reachable state, every tie rule, every input. -/
theorem lemma_5_5 {n : ℕ} {X : Type*} [MetricSpace X] (I : Instance n X) (hn : Even n)
(γ : ℝ) (hγ : 1 < γ) (tie : TieRule) (k : ℕ) :
∀ C : List ℕ, AlternatingEvenCycle (state I γ tie k).off C →
0 ≤ netCost (taDist I) γ (state I γ tie k).off (cycleEdges C) := by sorry
end BipartiteVRM.Competitive.Supplement
Source
Tung-Wei Kuo, STOC 2027 submission #528 (October 2026), p. 16, Lemma 5.5