Documentation

RumorSpread.Saturation

Saturation phase #

Once the informed set has size ≥ n/2 (which persists by monotonicity), the expected number of uninformed nodes contracts by a factor 2/3 per round (avg_uninformed_le); iterating gives saturation. Combined with Markov's inequality — which here is just a pointwise bound pushed through expList_le_expList — this finishes the proof in Main.lean.

theorem RumorPush.saturation {n : ℕ} (hn : 2 ≤ n) (T : ℕ) (I : Finset (Fin n)) :
n ≤ 2 * I.card → (Dynamics.expList (Tgt n) T fun (l : List (Tgt n)) => ↑n - ↑(run I l).card) ≤ (2 / 3) ^ T * (↑n - ↑I.card)

Phase 2: starting above half, the expected number of uninformed nodes after T further rounds is at most (2/3)^T · (n - |I|).