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:
SWG(n, c/n), thresholdp* = swgThreshold c = (√(c² + 6c + 1) − c − 1) / (2c):swg_subcritical(Theorem 2.1, claim 2: belowp* − ε, all components haveO(log n)nodes), from Lemma C.1 (swg_components_small);3-SWG(n), threshold1/2:swg3_subcritical(Theorem 2.2, claim 2), a consequence of Theorem 2.3 (EPI-2'sprob_components_small) since3-SWG(n)has maximum degree3.
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).
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.
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.