Lemma A.2: at most root-connected sets with non-root vertices
ProvedRGMISFast.lemma_A_2graph-theorylocal-computationp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilityrandomized-greedy-mis
Let be a finite simple graph with all degrees at most and root . For every , the number of root-connected sets with exactly vertices other than is at most
This standard count drives the union bound of Lemma A.1.
Formalization Note The sets are counted as vertex sets with and connected.
Differences from the source: none.
Preamble
import Mathlib import Definitions.Def_RGMISFast_IsRootConnected set_option autoImplicit false open MeasureTheory ProbabilityTheory open scoped ENNReal
Formal statement
namespace RGMISFast
/-- Lemma A.2 (Dalirrooyfard, Makarychev, Mitrović, Ramachandran, *Randomized Greedy MIS Is Fast at Every Node*,
STOC 2027 submission (manuscript sha256 e93cdfec…), p.29): for every `j ≥ 0`, there are at most `(4∆)^j` root-connected sets with
exactly `j` vertices other than `u∗`.
**Formalization Note** `∆` is any bound on all degrees; no lower bound on `∆` is needed. The
sets are finsets `A` with `|A| = j + 1`, counted by `Set.ncard` (the family is finite). -/
theorem lemma_A_2 {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (Δ : ℕ)
(hdeg : ∀ v, G.degree v ≤ Δ) (u : V) (j : ℕ) :
{A : Finset V | IsRootConnected G u A ∧ A.card = j + 1}.ncard ≤ (4 * Δ) ^ j := by sorry
end RGMISFast
Source
Dalirrooyfard, Makarychev, Mitrović, Ramachandran, Randomized Greedy MIS Is Fast at Every Node, STOC 2027 submission (manuscript sha256 e93cdfecc03618969d5f2ecf8171c6f84c528edcc473b2f864299e555f823664), Lemma A.2, p.29 (PDF p.31)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.