Documentation

Epidemics.SmallWorld

Subcritical percolation on one-dimensional small-world graphs (EPI-6) #

L. Becchetti, A. Clementi, R. Denni, F. Pasquale, L. Trevisan, I. Ziccardi, Percolation and epidemic processes in one-dimensional small-world networks, arXiv:2103.16398 [BCDPTZ22], Theorems 2.1 and 2.2, claim 2.

Bond percolation with parameter p on a random one-dimensional small-world graph (definitions in Epidemics.SmallWorldDefs), probabilities being taken over both the graph and the percolation:

The paper's "with high probability" (≥ 1 - n^{-Ω(1)}) is made quantitative as "with probability at least 1 - C / n", the rate its proofs give; O_ε(log n) is β log n (natural logarithm) with constants depending only on c and ε, uniformly in p. The edge probability of the bridges q = c / n is written q * n = c (as p * n = 1 + ε in EPI-3).

theorem Epidemics.swg_subcritical (c : ℝ) (hc : 0 < c) (ε : ℝ) (hε : 0 < ε) :
∃ (β : ℝ) (C : ℝ), ∀ (n : ℕ), 3 ≤ n → ∀ (q : ℝ) (hq0 : 0 ≤ q) (hq1 : q ≤ 1), q * ↑n = c → ∀ (p : ℝ) (hp0 : 0 ≤ p) (hp1 : p ≤ 1), p < swgThreshold c - ε → 1 - C / ↑n ≤ (coins q hq0 hq1).expect fun (b : Sym2 (Fin n) → Bool) => (coins p hp0 hp1).prob fun (ω : Sym2 (Fin n) → Bool) => ∀ (K : (perc (swg n b) ω).ConnectedComponent), ↑K.supp.ncard ≤ β * Real.log ↑n

Subcritical SWG(n, c/n) ([BCDPTZ22] Theorem 2.1, claim 2, proved in Appendix C, Lemma C.1): for every c > 0 and ε > 0 there are β and C such that, for n ≥ 3, bridge probability q = c / n and percolation probability p < p* − ε, with probability at least 1 - C / n over the graph swg n b (b ~ coins q) and the percolation ω ~ coins p, every connected component of perc (swg n b) ω has at most β log n nodes. Here β = 64 / δ² with δ = 1 - p₀ - c p₀ (1 + p₀), p₀ = p* - ε, and C = 2.

theorem Epidemics.swg3_subcritical (ε : ℝ) (hε : 0 < ε) :
∃ (β : ℝ) (C : ℝ), ∀ (n : ℕ), 4 ≤ n → ∀ (hn : Even n) (p : ℝ) (hp0 : 0 ≤ p) (hp1 : p ≤ 1), p < 1 / 2 - ε → 1 - C / ↑n ≤ (uniformMatching n hn).expect fun (M : PerfectMatching (Fin n)) => (coins p hp0 hp1).prob fun (ω : Sym2 (Fin n) → Bool) => ∀ (K : (perc (swg3 n M) ω).ConnectedComponent), ↑K.supp.ncard ≤ β * Real.log ↑n

Subcritical 3-SWG(n) ([BCDPTZ22] Theorem 2.2, claim 2, a consequence of Theorem 2.3): for every ε > 0 there are β and C such that, for even n ≥ 4 and percolation probability p < 1/2 − ε, with probability at least 1 - C / n over the uniformly random perfect matching M and the percolation ω ~ coins p, every connected component of perc (swg3 n M) ω has at most β log n nodes.