Documentation

Epidemics.CobraCoverBips

BIPS as a growth process (EPI-4, Theorems 1 and 2) #

BIPS with source v satisfies the hypotheses (H1)–(H5) of GrowthProcess with rate c = 1 - λ: the source is persistent (source_mem_bipsStep), the moment generating function bound is bips_mgf_le, Lemma 1 (bips_expected_growth) gives growth with 1 - λ² ≥ 1 - λ, and BIPS is monotone with V absorbing. Theorems 1 and 2 are then the generic GrowthProcess.fail_le, GrowthProcess.tail_sum_le_log, cover_fail_le_log and cover_tail_sum_le_log with c = 1 - λ.

theorem Epidemics.growth_of_rate_le {V : Type u_1} [Fintype V] {c c' X : ℝ} (hcc : c ≤ c') (A : Finset V) (h : ↑A.card * (1 + c' * (1 - ↑A.card / ↑(Fintype.card V))) ≤ X) :
↑A.card * (1 + c * (1 - ↑A.card / ↑(Fintype.card V))) ≤ X

Lowering the rate c weakens the growth bound |A| (1 + c (1 - |A|/n)) ≤ X.

theorem Epidemics.bips_growthProcess {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {k r : ℕ} (hreg : G.IsRegularOfDegree r) (hr : 0 < r) (hk : 2 ≤ k) (hlam : Dynamics.lambdaG G r < 1) (v : V) :

BIPS is a growth process with rate 1 - λ (for k ≥ 2 and λ < 1).

theorem Epidemics.lambdaG_lt_one_of_gap {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] [Nonempty V] {r : ℕ} (hreg : G.IsRegularOfDegree r) (hr : 0 < r) (hgap : 128 * √(Real.log ↑(Fintype.card V) / ↑(Fintype.card V)) ≤ 1 - Dynamics.lambdaG G r) :

The gap hypothesis 128 √(log n/n) ≤ 1 - λ gives λ < 1 and 1 - λ ≤ 1 (n ≥ 2).