Appendix A fixed-size tail for low-rank extensions
ProvedRGMISFast.low_rank_fixed_size_tailgraph-theoryprobabilityrandomized-greedy-mis
Let the graph have maximum degree at most , with a fixed root and independent exponential ranks of mean one. For integers and , the probability that some root-connected seed of size has at least reachable low-rank vertices outside it is bounded by
This is the fixed-size estimate in the proof of Lemma A.1. The seed is allowed to depend on the ranks and need not be active.
Preamble
import Definitions.Def_RGMISFast_GoodEvent import Definitions.Def_RGMISFast_rankLaw open MeasureTheory ProbabilityTheory RGMISFast open scoped ENNReal set_option autoImplicit false
Formal statement
theorem RGMISFast.low_rank_fixed_size_tail {V : Type*} [Fintype V] [LinearOrder V]
(G : SimpleGraph V) [DecidableRel G.Adj] (Δ : ℕ) (hΔ : 2 ≤ Δ)
(hdeg : ∀ v, G.degree v ≤ Δ) (u : V) (j k : ℕ) (hk : 1 ≤ k) :
rankLaw V {r | ∃ A : Finset V, IsRootConnected G u A ∧ A.card = j+1 ∧
k ≤ (GammaLow G r Δ A).card} ≤
ENNReal.ofReal ((8*(Δ:ℝ))^j*(1/2:ℝ)^k) := by sorrySource
Dalirrooyfard, Makarychev, Mitrović, Ramachandran, Randomized Greedy MIS Is Fast at Every Node, Appendix A, proof of Lemma A.1, “A fixed size”, printed pp.29–30 (PDF pp.31–32), manuscript sha256 e93cdfecc03618969d5f2ecf8171c6f84c528edcc473b2f864299e555f823664. The displayed probability bound immediately before “All sizes”.