Exponential extinction time of the contact process on finite graphs

1. Introduction

• The finite-tree extinction-time picture was less complete, and the authors knew of no results for finite graphs that are not regular.Earlier finite regular-tree results gave a stretched-exponential lower bound in the supercritical regime.Source: §1 · p. 3
• For λ > λc(Z), extinction-time expectations grow exponentially on bounded-degree trees, and normalized extinction time converges to the unitary exponential distribution.The results extend to graphs with subgraphs in the bounded-degree tree class; in particular, they cover increasingly large connected subsets of Zd.Source: §1 · p. 3
• Theorem 1.4 applies to every nonzero infection parameter λ > 0 and is stated to hold for all degree-exponent values a > 2, although the proof is given only for a > 3.Source: §1 · p. 4
• The tree proof splits a bounded-degree tree into two substantial subtrees and compares the original process with independent Phoenix processes whose activity can restart after extinction.This comparison yields a lower bound on the tree's expected extinction time in terms of the product of the subtrees' expected extinction times, up to a polynomial factor.Source: §1 · p. 4
• For NSW graphs, the proof constructs a discrete-time contact process on a tree mapped to well-connected high-degree vertices, with parameter above the one-dimensional critical value.Persistent infection around high-degree vertices can transmit to other such vertices, supporting the long-survival comparison.Source: §1 · p. 5

2. A reminder on the contact process

• In the Harris construction, infection paths traverse links without touching death marks, and the notation records connections between sets at specified times.Paths can also be required to remain entirely inside a specified vertex set.Source: §2 · p. 5
• The graphical construction couples processes with different initial configurations, yielding attractiveness: inclusion of initial infected sets is preserved over time.The construction has the same distribution as the process defined by the generator.Source: §2 · p. 6
• The dual process has the same distribution as a contact process and satisfies a duality equation.The supplied passage introduces the dual process and states these two properties.Source: §2 · p. 6
• For infection rates above λc(Z), the section recalls classical results on the contact process on finite intervals.These results are cited as a basis for the later arguments.Source: §2 · p. 6

3. Metastability

• For λ > λc(Z), Proposition 3.2 gives bounds for contact processes on bounded-degree trees and graphs having such a tree as a spanning tree.The proposition is stated for sufficiently large n; its displayed bounds are not present in the supplied passages.Source: §3 · p. 7
• For n large enough and any G ∈ G(n,d), if the contact process from an arbitrary non-empty configuration survives until time n^2, it equals the process from full occupancy then with probability at least 1 − e^(−n^(−α/2)).Source: §3 · p. 7
• A bounded-degree tree can be divided into logarithmically many disjoint subtrees, each containing a path of logarithmic length.The construction repeatedly applies the edge-removal lemma; the number of subtrees is 2β log n under the stated restriction on β.Source: §3 · p. 7
• The proof separates trees with diameter at least n^α from those with smaller diameter, using a long interval in the first case and good intervals in the second.For the long-diameter case, infection reaches an interval and then spreads along it; in the small-diameter case, the proof tracks how many intervals are good over time.Source: §3 · pp. 7–9
• In the small-diameter case, the number of good intervals is compared with a random walk that drifts right, which supports the metastability bounds.The proof establishes that good intervals tend to remain good and that a previously non-good interval can become good.Source: §3 · pp. 9–10

4. Comparison with Phoenix contact processes

• The proof splits a tree into two substantial subtrees and compares the true process with independent Phoenix processes on them.With high probability, the true process dominates their union, enabling the extinction-time argument.Source: §4 · pp. 13, 17
• A Phoenix process runs as a contact process until extinction, remains quiescent for a period, and can restart from a specified distribution.Its auxiliary Bernoulli variables and a trustworthy Harris-system interval govern the restart; the process is not Markovian in its original state description.Source: §4 · p. 14
• The authors also establish a uniform exponential upper bound on the expected extinction time for trees in Λ(n, d).The supplied lemma states E[τ] ≤ e^(Cn) for a constant C.Source: §4 · p. 15
• The proof of Theorem 1.1 is completed by establishing a positive lower limit for V_r as r tends to infinity: lim inf_{r→∞} V_r > 0.Source: §4 · pp. 19–20

• The process is introduced as a discrete-time analogue of the contact process for comparison and use in the following section.Source: §5 · p. 21
• The process is attractive, and a threshold p(1)c < 1 exists above which it survives.Source: §5 · p. 21
• For p > p(1)c, the discrete-time process survives from every nonzero initial configuration, and ηr decreases stochastically to a nonzero limit.The process is attractive and has a threshold p(1)c < 1.Source: §5 · p. 21
• The process extends to locally finite graphs and has self-duality, allowing preceding arguments to be carried through.Source: §5 · p. 21

6. Extinction time on Newman-Strogatz-Watts random graphs

• With high probability, the construction aims to find a tree subgraph containing δn focal vertices, whose induced tree structure supports a comparison with a discrete-time growth process.The focal vertices are those in I′, and the tree connects pairs joined by paths containing no other focal vertices.Source: §6 · pp. 22, 28
• The comparison tree T has degree bounded by 4; Property B ensures long infection persistence around each site in I, making the discrete-time growth process infection rate as large as desired.Together with Property A, this permits applying Proposition 5.2 to conclude the growth process has very large extinction time; the contact process on Gn′ also has very large extinction time.Source: §6 · p. 22
• The subgraph is built by successive half-edge-matching passes that mark selected edges and track identified, preactive, and active vertices.A pass ending in status G finds three new focal vertices; the other statuses help preserve large degrees and keep focal vertices close while limiting exploration.Source: §6 · pp. 23, 25
• On the event that the pass sequence leaves more than δ′n preactive vertices, the constructed subgraph has more than δn focal vertices, each activated after the initial passes and retaining degree at least S/4.The associated tree joins focal vertices along unique paths of length less than 20a log(1/λ).Source: §6 · pp. 27–28
• With probability greater than 1 − σ, both S(x) and S(y) are infested in the process restricted to S(x), S(y), and b(x, y).This is stated for x, y ∈ I′ with x ∗∼ y and sufficiently large M.Source: §6 · p. 28
• A sequence of indicator successes along vertices in I′ ensures ηR(xR) = 1 and that S(xR) is infested at time κR.At each step, the sequence may stay at the same vertex or move to the next vertex when the corresponding indicator equals 1.Source: §6 · p. 29
• For any p > pc(1), if M is large enough, the process {ηr} dominates a growth process on T defined from i.i.d. Bernoulli(p) random variables.Source: §6 · p. 29