Lemma 5.3: active extensions with prescribed starting ranks,
ProvedRGMISFast.lemma_5_3graph-theorylocal-computationp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1probabilityrandomized-greedy-mis
Fix and condition on ; let be a nonempty connected vertex set of . Assign the ranks of all vertices of arbitrarily in ; outside , the revealed ranks stay fixed and the unrevealed ranks are independent with distribution . Let be the number of -sets attached to for which is active at time . For each ,
This is the count behind the conditional bounds of Lemma 6.1. It holds on every finite simple graph.
Formalization Note The conditional expectation is the Lebesgue integral of under the explicit conditional law, stated together with the measurability of .
Differences from the source:
- reading: conditioning on F_θ and r(A) (Lemma 5.3) → the measure
condLaw r₀ θ A rAfor every history r₀ at θ and every prescribed rA with values in [a, ∞) on A; reason: the explicit conditional law described in Lemma 5.3 and on p.18; holding for every history is the pointwise form of the conditional statement - generalization: E[N_k(A; G_a) | F_θ, r(A)] ≤ (e/(a − θ))^k → measurability of N_k, and its lower Lebesgue integral ≤ (e/(a − θ))^k; reason: the added measurability clause is true and makes the lower integral the expectation; dropping it gives (22)
Preamble
import Mathlib import Definitions.Def_RGMISFast_Y import Definitions.Def_RGMISFast_condLaw set_option autoImplicit false open MeasureTheory ProbabilityTheory open scoped ENNReal
Formal statement
namespace RGMISFast
/-- Lemma 5.3 (Active extensions with prescribed starting ranks; Dalirrooyfard, Makarychev, Mitrović, Ramachandran, *Randomized Greedy MIS Is Fast at Every Node*,
STOC 2027 submission (manuscript sha256 e93cdfec…), p.20): fix `0 ≤ θ < a`,
condition on `F_θ`, and suppose that `A` is a non-empty connected vertex set of `G_θ`. Assign the
ranks of all vertices of `A` arbitrarily in `[a, ∞)`; outside `A`, the ranks revealed by `F_θ`
remain fixed, and the unrevealed ranks remain independent with distribution `θ + Exp(1)`. Then for
each `k ≥ 0`, `E[N_k(A; G_a) | F_θ, r(A)] ≤ (e/(a − θ))^k` (22).
**Formalization Note** The conditional law is `condLaw r₀ θ A rA`, and the statement holds for
every history `r₀` at time `θ` and every prescribed `rA`. `G_θ` is computed from the history.
The expectation is the lower Lebesgue integral of `N_k` plus a measurability clause. No degree
bound is assumed. -/
theorem lemma_5_3 {V : Type*} [Fintype V] [LinearOrder V] (G : SimpleGraph V)
[DecidableRel G.Adj] (θ a : ℝ) (hθ : 0 ≤ θ) (hθa : θ < a) (r₀ : V → ℝ)
(hr₀ : IsHistory r₀ θ) (A : Finset V) (hA : IsConnectedSet G A)
(hAθ : ActiveAt G r₀ θ A) (rA : V → ℝ) (hrA : ∀ v ∈ A, a ≤ rA v) (k : ℕ) :
Measurable (fun r : V → ℝ => Ncount G A k a r) ∧
∫⁻ r, (Ncount G A k a r : ℝ≥0∞) ∂(condLaw r₀ θ A rA) ≤
ENNReal.ofReal ((Real.exp 1 / (a - θ)) ^ k) := by sorry
end RGMISFast
Source
Dalirrooyfard, Makarychev, Mitrović, Ramachandran, Randomized Greedy MIS Is Fast at Every Node, STOC 2027 submission (manuscript sha256 e93cdfecc03618969d5f2ecf8171c6f84c528edcc473b2f864299e555f823664), Lemma 5.3, eq. (22), p.20 (PDF p.22)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.