Lemma 5.1: average neighborhood size of attached sets,
ProvedRGMISFast.lemma_5_1graph-theorylocal-computationp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilityrandomized-greedy-mis
Let be a finite graph containing , let , and let be a nonempty family of distinct -sets attached to the root. Then
where counts the vertices of together with all vertices adjacent to or to , not counting .
Many attached sets force a large average neighbourhood; this is the deterministic input of Lemma 5.2.
Formalization Note is a finite family of vertex sets, each of size and attached to (so it avoids ); is the real power.
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 5.1 (Average Neighborhood Size of Attached Sets; Dalirrooyfard, Makarychev, Mitrović, Ramachandran, *Randomized Greedy MIS Is Fast at Every Node*,
STOC 2027 submission (manuscript sha256 e93cdfec…), p.17, proof in §5.3): let `H` be a
finite graph containing `u∗`, let `k ≥ 1`, and let `S` be a nonempty family of distinct `k`-sets
attached to the root. Then `(1/|S|) Σ_{W∈S} d(W) ≥ (k/e) |S|^{1/k}` (18).
**Formalization Note** `H` is a simple graph on a finite vertex type containing `u`; `S` is a
finset of finsets (so its members are distinct), each of size `k` and attached to `{u}` (in
particular not containing `u`). `|S|^{1/k}` is the real power. Deterministic: no ranks. -/
theorem lemma_5_1 {V : Type*} [Fintype V] [DecidableEq V] (H : SimpleGraph V) (u : V) (k : ℕ)
(hk : 1 ≤ k) (S : Finset (Finset V)) (hS : S.Nonempty)
(hSk : ∀ W ∈ S, W.card = k ∧ IsAttached H {u} W) :
(k / Real.exp 1) * (S.card : ℝ) ^ (1 / (k : ℝ)) ≤
(1 / (S.card : ℝ)) * ∑ W ∈ S, (dW H u W : ℝ) := 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.1, eq. (18), p.17 (PDF p.19); proof in §5.3, pp.21–22
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.