Documentation

RumorSpread.PullFoldl

Iterating a monotone, inflationary step #

PULL and PUSH–PULL (PullModel.lean) iterate a one-round step f I a (informed set I, round a) along a list of rounds with List.foldl. This file collects the deterministic facts used for any such step that is inflationary (I ⊆ f I a: informed nodes stay informed) and monotone in the informed set:

theorem RumorPush.subset_foldl {n : ℕ} {α : Type u_1} {f : Finset (Fin n) → α → Finset (Fin n)} (hf : ∀ (I : Finset (Fin n)) (a : α), I ⊆ f I a) (I : Finset (Fin n)) (l : List α) :
I ⊆ List.foldl f I l

An inflationary step only adds informed nodes along a trajectory.

theorem RumorPush.foldl_mono {n : ℕ} {α : Type u_1} {f : Finset (Fin n) → α → Finset (Fin n)} (hf : ∀ (a : α), Monotone fun (I : Finset (Fin n)) => f I a) {I J : Finset (Fin n)} (h : I ⊆ J) (l : List α) :
List.foldl f I l ⊆ List.foldl f J l

Iterating a monotone step is monotone in the initial informed set.

theorem RumorPush.foldl_subset_foldl {n : ℕ} {α : Type u_1} {f g : Finset (Fin n) → α → Finset (Fin n)} (hfg : ∀ (I : Finset (Fin n)) (a : α), f I a ⊆ g I a) (hg : ∀ (a : α), Monotone fun (I : Finset (Fin n)) => g I a) (I : Finset (Fin n)) (l : List α) :
List.foldl f I l ⊆ List.foldl g I l

Pathwise domination: if f ≤ g round by round and g is monotone, then the trajectory of f stays inside the trajectory of g driven by the same rounds.

theorem RumorPush.foldl_append_eq_univ {n : ℕ} {α : Type u_1} {f : Finset (Fin n) → α → Finset (Fin n)} (hf : ∀ (I : Finset (Fin n)) (a : α), I ⊆ f I a) {I : Finset (Fin n)} {l₁ : List α} (h : List.foldl f I l₁ = Finset.univ) (l₂ : List α) :
List.foldl f I (l₁ ++ l₂) = Finset.univ

Once all nodes are informed they stay informed (for an inflationary step).