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:
subset_foldl— the informed set only grows;foldl_mono— more informed nodes at the start give more at the end;foldl_subset_foldl— pathwise domination of a step by a larger monotone step;foldl_append_eq_univ— once everybody is informed, everybody stays informed.
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 α)
:
Once all nodes are informed they stay informed (for an inflationary step).