Eq. (29):
ProvedRGMISFast.eq_29graph-theorylocal-computationp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1probabilityrandomized-greedy-mis
Let be a finite simple graph with root , let , , , and let be a root-connected set. Let be either the growth event or a boundary event with , and let . Conditionally on (the ranks below ),
Summed over root-connected sets with Lemma 5.2, this gives Lemma 3.1.
Formalization Note Conditioning on is the explicit law in which the revealed ranks (below ) of a history are fixed and all other ranks are independent ; the statement holds for every history. is computed from the history. Both events (the boundary event for every ) and both inequalities are stated.
Differences from the source:
- reading: Pr[· | F_{a/2}], a conditional probability → the measure under
condLaw r₀ (a/2) ∅ _for every history r₀ (revealed ranks fixed, others i.i.d. a/2 + Exp(1)); reason: the explicit conditional law stated on p.18 and used by the proof; holding for every history is the pointwise form of the conditional bound - generalization: a = a_m with 1 ≤ m ≤ M → a = a_m for every m ≥ 1; reason: the bound uses only 0 < a_m ≤ a₀ and i < m; restricting to m ≤ M gives the printed range
Preamble
import Mathlib import Definitions.Def_RGMISFast_Gamma import Definitions.Def_RGMISFast_gammaA import Definitions.Def_RGMISFast_condLaw set_option autoImplicit false open MeasureTheory ProbabilityTheory open scoped ENNReal
Formal statement
namespace RGMISFast
/-- Eq. (29) (Dalirrooyfard, Makarychev, Mitrović, Ramachandran, *Randomized Greedy MIS Is Fast at Every Node*,
STOC 2027 submission (manuscript sha256 e93cdfec…), Proof of Lemma 3.1, p.25): fix `a = a_m`, `m ≥ 1`, and a root-connected `A`, and
let `B_A` be either of the events `|Γ_{a,ca}(A)| > 2S(A, a) + L` or
`K_{m,i}(A) > 32c^{1+m−i}(2S(A, a) + L)` (`0 ≤ i < m`). Conditionally on `F_{a/2}`,
`Pr[B_A | F_{a/2}] ≤ 1{A⊆V(G_{a/2})} Pr[E_a(A) | F_{a/2}] e^{−L}γ(a)^{|A|} ≤ 1{A⊆V(G_{a/2})} e^{−L}γ(a)^{|A|}`,
where `E_a(A) = {r(v) ≥ a for every v ∈ A}`.
**Formalization Note** The conditional probability given `F_{a/2}` is the explicit law
`condLaw r₀ (a/2) ∅ _` for an arbitrary history `r₀` (revealed ranks below `a/2` fixed, all others
i.i.d. `a/2 + Exp(1)`; no prescribed set), and the statement holds for every history. The
indicator `1{A ⊆ V(G_{a/2})}` is computed from the history. `L ≥ 8`. Both events (the boundary
event for every `i < m`) and both inequalities are stated. -/
theorem eq_29 {V : Type*} [Fintype V] [LinearOrder V] (G : SimpleGraph V) [DecidableRel G.Adj]
(u : V) (L : ℝ) (hL : 8 ≤ L) (m : ℕ) (hm : 1 ≤ m) (r₀ : V → ℝ)
(hr₀ : IsHistory r₀ (am m / 2)) (A : Finset V) (hA : IsRootConnected G u A) :
(condLaw r₀ (am m / 2) ∅ (fun _ => 0)
{r | 2 * S r A (am m) + L < ((GammaAB G r (am m) ((c * am m : ℝ) : WithTop ℝ) A).card : ℝ)} ≤
(if ActiveAt G r₀ (am m / 2) A then 1 else 0) *
condLaw r₀ (am m / 2) ∅ (fun _ => 0) {r | ∀ v ∈ A, am m ≤ r v} *
ENNReal.ofReal (Real.exp (-L) * gammaA (am m) ^ A.card) ∧
(if ActiveAt G r₀ (am m / 2) A then 1 else 0) *
condLaw r₀ (am m / 2) ∅ (fun _ => 0) {r | ∀ v ∈ A, am m ≤ r v} *
ENNReal.ofReal (Real.exp (-L) * gammaA (am m) ^ A.card) ≤
(if ActiveAt G r₀ (am m / 2) A then 1 else 0) *
ENNReal.ofReal (Real.exp (-L) * gammaA (am m) ^ A.card)) ∧
∀ i : ℕ, i < m →
condLaw r₀ (am m / 2) ∅ (fun _ => 0)
{r | 32 * c ^ (1 + m - i) * (2 * S r A (am m) + L) < (Kmi G r m i A : ℝ)} ≤
(if ActiveAt G r₀ (am m / 2) A then 1 else 0) *
condLaw r₀ (am m / 2) ∅ (fun _ => 0) {r | ∀ v ∈ A, am m ≤ r v} *
ENNReal.ofReal (Real.exp (-L) * gammaA (am m) ^ A.card) ∧
(if ActiveAt G r₀ (am m / 2) A then 1 else 0) *
condLaw r₀ (am m / 2) ∅ (fun _ => 0) {r | ∀ v ∈ A, am m ≤ r v} *
ENNReal.ofReal (Real.exp (-L) * gammaA (am m) ^ A.card) ≤
(if ActiveAt G r₀ (am m / 2) A then 1 else 0) *
ENNReal.ofReal (Real.exp (-L) * gammaA (am m) ^ A.card) := by sorry
end RGMISFast
Source
Dalirrooyfard, Makarychev, Mitrović, Ramachandran, Randomized Greedy MIS Is Fast at Every Node, STOC 2027 submission (manuscript sha256 e93cdfecc03618969d5f2ecf8171c6f84c528edcc473b2f864299e555f823664), Proof of Lemma 3.1, eq. (29), p.25 (PDF p.27)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.