{'fraction_non_alphanumeric': 0.0505743541764125, 'fraction_numerical': 0.01885059861046139, 'mean_word_length': 3.593187967531434, 'pattern_counts': {'":': 0, '<': 35, '<?xml version=': 0, '>': 58, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 15, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The Contact Process on Trees

The contact process on an infinite homogeneous tree is shown to exhibit at least two phase transitions as the infection parameter lambda is varied. For small values of lambda a single infection eventually dies out. For larger lambda the infection lives forever with positive probability but eventually leaves any finite set. (The survival probability is a continuous function of lambda, and the proof of this is much easier than it is for the contact process on d-dimensional integer lattices.) For still larger lambda the infection converges in distribution to a nontrivial invariant measure. For an n-ary tree, with n large, the first of these transitions occurs when lambda~1/n and the second occurs when 1/2 sqrt{n}<lambda<e/sqrt{n}. Nonhomogeneous trees whose vertices have degrees varying between 1 and n behave essentially as homogeneous n-ary trees, provided that vertices of degree n are not too rare. In particular, letting n go to infty, Galton-Watson trees whose vertices have degree n with probability that does not decrease exponentially with n may have both phase transitions occur together at lambda=0. The nature of the second phase transition is not yet clear and several problems are mentioned in this regard.


Introduction
This paper studies the contact process on trees. A tree is just a connected unoriented graph without cycles. A brief description of the contact process is as follows. The state space, in this case a tree, is any undirected graph. At any instant in time, some vertices of the graph are infected and some are healthy. The infected vertices recover (turn into healthy vertices) at poisson rate 1, independently. Each infected vertex independently infects each of its healthy neighbors at poisson rate λ for some fixed parameter λ. More complete descriptions of this are available in [Li] and [Du], along with a construction (which I will later describe) of the process from a poisson process called the graphical representation.
There are practical and mathematical reasons to study the contact process on trees.
The practical reason is that the process was developed to model the spread of infectious disease. The vertices of the graph represent individuals susceptible to the disease and the edges represent pairs of individuals who may have frequent contact. Traditionally, the graph is taken to be the n-dimensional integer lattice, probably because that makes sense for other interacting particle systems such as the Ising model for ferromagnetism.
While the "real" graph is a large finite graph, a tree is at least as likely as a lattice to serve as a local approximation to the real graph for a population.
One mathematical reason for studying the contact process on trees is to better understand the correspondence between behaviour of processes on trees and limits of behaviours on lattices as the dimension of the lattice goes to infinity. For other processes such as random walks and the Ising model, there is a critical dimension beyond which the lattice versions of the process behave in essential ways like the tree version.
Another reason to study trees is the following observation about the contact process on different graphs. If G and H are graphs with a map φ from the vertices of G to the vertices of H, such that (x, y) is an edge of G whenever (φx, φy) is an edge of H, then the contact process may be coupled so that the number of infections on G is always at least the number of infections on H. (Letting infections and recoveries on G proceed as on H but subject to the restriction that there can be at most one infection in any φ −1 (x) gives a process with equal recovery rate but smaller infection rate than the contact process on G. This process has as many infections as the process on H and by monotonicity, has fewer infections than the contact process on G.) Since any graph has a tree for a universal cover, this relates the contact process on any graph to the contact process on a tree. In particular, among all graphs where every vertex has the same degree n + 1, the tree has the best survival probability for the contact process, hence the critical value λ 1 defined below is least for the tree.
The main reason that the contact process on a tree is worth studying is that it exhibits a multiple phase transition. In this respect the behaviour differs remarkably from any of the usual interacting particle systems on the lattice. In fact a major recent result [BG] says that no such monkey business can happen with the contact process. That such behaviour may be the rule for trees, rather than the exception, is made plausible by the recent work of Grimmett, Newman and Wu [GN], [NW], which shows a similar phenomenon for percolation on a graph which is the integers crossed with a tree. Since the contact process on a graph G is very similar to oriented percolation on G × Z, it is not surprising that unoriented percolation on the integers crossed with a tree should behave like the contact process on a tree.
The results in this paper are concerned with the existence and location of the multiple phase transitions. The theory of the contact process on a tree has by no means been tidied up. In particular, I believe but am far from being able to prove that there are only two phase transitions. The rest of this introductory section will define the phase transitions and delimit what I know about their existence.
Let T be an infinite tree with a distinguished vertex ρ called the root. Let 2 T be the set of subsets of the vertices of T, and let A ⊆ 2 T be the finite subsets of vertices.
The contact process can be viewed as a random variable taking values in the space of functions ξ with domain R + and range 2 T , where ξ(t) is the set of vertices infected at time t. If the initial configuration ξ(0) is almost surely in A, then ξ(t) stays in A almost surely for all time. I will not prove statements on this level, or even formally construct the contact process; the reader may easily do this from [Du]. The idea is to construct the graphical representation, which is merely a set of independent poisson processes. There is a rate 1 poisson process for each vertex giving the recovery times at that vertex (a vertex ignores recovery times while it is healthy) and there is a rate λ poisson process for each oriented edge giving the attempted infection times, where an attempted infection from an infected node to a healthy node transmits the infection but all other attempted infections are ignored. It is also possible to construct the process directly from its semigroup [Li].
Here is some notation.
For any configuration η ∈ 2 T , use P η (ξ(t) has property X) to denote probabilities for the contact process started from the initial condition ξ(0) = η. Let P v denote P {v} in this regard. A measure µ is invariant for the contact process if ξ(t) has law µ for any t whenever ξ(0) has law µ. Since the contact process is an attractive system, it is easily seen [Li] that there is a stochastically greatest invariant measure µ that can be gotten by taking the limit of the laws of ξ(t) as t → ∞ when ξ(0) is the configuration with every vertex infected. (The contact process, since it is an attractive system, is monotone in the following sense. Two contact processes run from initial states where the infections of one are a subset of the infections of the other may be coupled so as always to remain in this relation. This and its consequences will be used freely in what follows, and sometimes without explicit mention.) The following are all possible definitions of critical values for the infection parameter λ.
where µ is the upper inveriant measure and δ 0 is the point mass at the empty set.
In words: λ 1 is the value at which the process can survive forever with nonzero probability, above λ a the root gets reinfected infinitely often, above λ b the root is reinfected with probability bounded away from zero at arbitrarily large times, above λ 2 these arbitrarily large times are all times, and above λ c there is complete convergence to a nontrivial measure (which has been shown for one-dimensional, and more recently any dimensional integer lattice). It is immediate that λ 1 ≤ λ a ≤ λ b ≤ λ 2 ≤ λ c < ∞, with the last inequality following from the classical results one the contact process on the integers, which are a subgraph of any infinite tree. I believe the following relations hold among the critical values.
Call a vertex v of an infinite tree T esential if T\{v} has at least two infinite components.
Say that a tree has strongly exponential growth if there is some r ≥ 1 such that for any v ∈ T there are at least 3 essential vertices w whose graph-distance from v is r.
conjecture 2 For any tree with strongly exponential growth, either all the above critical values are zero, or else λ 1 = λ a .
The nature of the phase transitions other than λ 1 is evidently unclear, but regarding the first phase transition I believe: conjecture 3 For any tree, the survival probability starting from a single infection is a continuous function of λ.
Conjecture 3 is undoubtedly difficult since it includes the case of the one-dimensional integer lattice, a recent and difficult result. Theorem 6.6 says that the survival probability is continuous whenever λ 1 = λ a , thus Conjecture 2 implies Conjecture 3 for trees of strongly exponential growth. The reason some kind of growth condition is needed in Conjecture 2 is that it is easy to make both λ 1 and λ a equal to the critical value for the integer lattice by making the tree contain indreasingly long stretches of vertices of degree two. The theorems in this paper make some progress toward proving these conjectures, separating λ 1 and λ a , bounding λ a and λ 2 near each other, and proving continuity of the survival probability, all in special cases. Here is a summary.
Say a tree is homogeneous of degree n if every vertex has n + 1 neighbors. For homogeneous trees of degree n > 2, Theorem 2.2 states that 0 < λ 1 < λ a . Additionally, it gives reasonable bounds for the location of λ 1 , λ a and λ 2 . So there are at least two phase transitions when n > 2.
Nonhomogeneous trees come in many shapes. This paper considers two varieties, namely periodic trees and Galton-Watson trees. Since there is no single parameter n measuring the size of such a tree (the mean growth of a Galton-Watson tree being an irrelevant statistic in this setting -Theorem 3.2), bounds on the critical values are harder to get at. The main result here is that 0 = λ 1 = λ a = λ b = λ 2 is possible. The last section deals with the continuity of the survival probability as a function of λ. This is linked to the separation of λ 1 and λ a , and to the question of whether survival is still possible if a single edge is severed. The relation is: λ 1 < λ a ⇒ survival with a severed edge whenever survival is possible without a severed edge ⇒ continuity of the survival probability in λ.
Thus again the process behaves nicely on homogeneous trees with n > 2.

Homogeneous trees
Fix an integer n ≥ 2. Let T be a homogeneous tree where each vertex (also called a node) has n + 1 neighbors. Pick any vertex ρ and call that the root; then each vertex other than ρ has one neighbor closer to ρ (the parent) and n neighbors (children) further from ρ. Define the contact process on T by letting each infected node recover at rate 1 and each infected node infect each of its neighbors at rate λ where λ is any positive parameter. Denote by ξ(t) the set of infected nodes at time t ≥ 0. Thus ξ is viewed as a function from R + to 2 T , or sometimes as a function from R + × T to {0, 1}. Probabilities referring to initial state η at time 0 will be written as P η (ξ(t) · · ·). When the initial state can be understood, the subscript will be dropped.
Theorem 2.1 For all n > 2, 0 < λ 1 < λ 2 < ∞. For n = 2 the same holds except that the middle inequality may not be strict.
This is a consequence of: Note that the LHS is asymptotically 4 − √ 8 2 √ n and is always better than (iii) (v) In particular, .561722, .425516, .354248 ≤ λ 2 when n is respectively 2, 3, 4 The upper bound on λ 1 in (ii) is less than the lower bound on λ a on (iii) except for n ≤ 4. The reason it is worth improving the relatively easy bound (iii) to the messy bound (iv) is to separate λ 1 and λ a for n = 3, 4, thus showing there are at least two phase transitions except possibly when n = 2. The rest of this section is taken up by the proof of Theorem 2.2. Proofs: (i): See Liggett (1985) page 166. Alternatively, see the remark after the proof of (ii).
✷ (ii): Assign a weight W (ξ) = ak(ξ)+bc(ξ) to each configuration ξ having finitely many infected nodes, where a and b are constants to be determined later, k is the number of infected nodes of ξ, and c is the number of components in the induced subgraph of T on ξ, i.e. the graph gotten by restricting T to ξ. For λ > ( 9 + 16/(n − 1)−1)/2(n+1), it will be shown that W (ξ) is a submartingale, and in fact E(W (ξ(t+dt)) | ξ(t)) ≥ (1+ǫ)W (ξ(t)) for a suitable ǫ > 0. Together with the fact that W is a pure jump process with bounded jumps, this implies that the probability of W getting arbitrarily large before hitting zero is bounded below. (Proof: 1/W is a supermartingale when W is greater than an appropriate function of ǫ and the bound on the jump size, so choose a starting time when W is large enough and stopping when W gets too small, the optional stopping theorem says the stopping time is reached with probability less than 1.) Here are some preliminary results.
(A) The rate of new infections is precisely λ((n − 1)k + 2c). To see this, count all the attempted infections and subtract off the times a node attempts to infect an already infected node. The attempted infection rate is λ(n + 1)k and the failure rate is just λ times twice the number of edges having infected nodes on both ends. But the number of such edges is the number of infected nodes minus the number of components they constitute, so the infection rate is λ((n + 1)k − 2(k − c)) = λ(n − 1)k + 2c.
(B) The total recovery rate is precisely k.
Finally, it is easy to see that when this inequality holds, [E(W (ξ(t + dt)) | ξ(t)) − W (ξ(t))]/dt is at least a small constant multiple of bn for each fixed λ, thus at least ǫW (ξ(t)) for an appropriate ǫ > 0 and the argument is done. ✷ Remark: This method also gives a proof of (i). Instead of the upper bound on component loss in preliminary result (D), use a lower bound of zero. The same calculation now gives a = b/((n + 1)λ − 1) and plugging that into equation (1) with the inequality reversed gives ((n − 1)λ − 1)/((n + 1)λ − 1) + 1 > 0 which is satisfiable when λ < 1/n. Thus for λ < 1/n, W can be defined to be a supermartingale and the weight must converge to zero. Then So for λ < 1/2 √ n, EM(t) goes to zero exponentially fast, hence so does P(ρ ∈ ξ(t)). ✷ (iv) and (v): This time the idea is to take into account the coalescing nature of the infection in order to improve on the bound in (iii). The weight of a vertex will depend on whether its parent is infected and will count less if so, due to the redundancy. Define where k is the distance from v to the root and r and d are parameters that will be chosen optimally later. The goal is to show that the expected change in the total weight is always negative. Let θ 1 (v) and θ 2 (v) denote respectively the number of infected parents of v (zero or one) and the number of infected children of v. Define Then u(v)r k ∂t is an upper bound on the expected increment in the total weight from t to t + ∂t due to the recovery of v or infection of other nodes by v. (Breaks down as follows: recovery loses weight (1 − θ 1 (v))dr k , but gains θ 2 (v)dr k+1 ; infecting the parent gains at most r k−1 while losing dr k , and infecting a child gains (1 − d)r k+1 while it may lose something as well.) One way to show that the expected increment in total weight is negative show that u(v) < 0 for each infected node. Trying to count this way is inefficient because d must be kept small so that a node that is completely surrounded by infection does not seem to increase the total weight if it recovers. A solution is to let Y be another parameter to be determined later, and define The sum over all nodes of U(v)r k is the same as the sum of u(v)r k , because for each parent and child node that are both infected, a quantity of r k Y has merely been transferred from parent to child. The U's are calibrated so as no longer to penalize our strategy at nodes with many infected neighbors.
Now there are 2n + 2 cases to check in the forward equation, one for each value of θ 1 (v) and θ 2 (v). For each pair of these values, r, d, λ and Y must be chosen to make U < 0. Again by linearity, it suffices to consider the cases where θ 2 (v) = 0 or n, so the inequalities are: These inequalities are not too hard to solve. Given n, r, and λ, equality in the first equation gives an optimal choice for d and equality in the third equation gives an optimal choice for Y . It then turns out that equality in both of the remaining equations can be achieved for the greatest λ when r = 1/ √ n, and hence the strict inequalities are satisfied for any smaller λ. Plugging in these values gives a nasty looking quadratic in λ that simplifies to and has the solution appearing in (iv) (divide through by 1 − √ n and use the quadratic formula). Values for λ, r, d and Y for n = 2, 3, 4 are given below so that skeptics may plug them into the four equations above and check that they actually work. For n = 2 use λ = .561722, r = .7071, d = .434212 and Y = .082293; for n = 3 use λ = .425516, r = .5773, d = .407781 and Y = .089933; for n = 4 use λ = .354246, r = .5012, d = .391747 and Y = .088349.
When all the inequalities are satisfied, it is easy to see, as in the proof of (ii), that in ) for a suitable ǫ > 0. Then again the expected total weight decays exponentially, hence the probability of finding an infection in any finite set decays exponentially and the proof is done. ✷ (vi): The 2 comes from the fact that the critical value for λ on the one-dimensional integer lattice is know to be at most 2 and is an upper bound on λ 2 by monotonicity.
For the nontrivial bound, first record two lemmas.
Lemma 2.3 Let M be an positive integer valued random variable and pick p < EM (with EM possibly being infinite). For any Proof: Pass to the bounded case as follows: let L be large enough so that E(M ∧ L) > p; and it suffices to prove the lemma for M ′ . Now for small enough x which proves the lemma. ✷ Lemma 2.4 Let H be any nondecreasing function on the nonnegative reals with H(x) ≥ x on some neighborhood of 0. Suppose f is a function on the nonnegative reals that Proof: For any t 0 and any ǫ > 0, (2) implies there is a sequence t 1 , t 2 , . . . , t k with is bounded away from 0 for small ǫ by (1). ✷ Continuing the proof of (vi), let f (t) = P δ (ρ ∈ ξ(t)) in an altered contact process where only n of the root's n+ 1 neighbors is allowed to infect the root. The object will be to get a recursion f (t) ≥ H(f (t − 2r)). Here 2r is a convenient size for a time increment to be chosen later so as to make H monotone increasing with H(0) = 0 and H ′ (0) > 1.
To get this recursion break down f (t) into a product of conditional probabilities as follows. Let and . Clearly a lower bound on H 2 that does not depend on t is the probability p(r) = P x (y ∈ ξ(r)) in a system with only two neighboring nodes x and y.
To calculate this, let Obtain from this a crude lower bound on p(r) by requiring x to stay infect up to time r: A better bound is given by conditioning on the recovery time s of x, requiring y to be infected at time s and remain infected through time r: Now for a lower bound on H 1 , let M be the number of children of ρ that are infected at time r, not counting the one child that is not allowed to infect ρ. The previous calculation says essentially that each child is infected at time r with probability at least p(r), so EM ≥ np(r). If each of these nodes is not allowed to be infected by its parent between time r and time t − r then by definition of f such a node infected at time r is infected at time t − r with probability f (t − 2r). Thus the actual number of children infected at time t − r stochastically dominates a random variable that is binomial(M, f (t − 2r)). Then by Lemma 2.4 will finish the proof.
For the first claim in (vi) use the crude lower bound (6) on p(r) to get This holds for any r, and an optimal choice of r is ln (2), giving To get the asymptotic, use the better bound to get As n → ∞ the minimum λ satisfying this inequality will have √ nλ → e r r −1 and choosing r = 1 gives lim sup √ nλ = e. ✷ (vii): First an outline of the argument. By duality, it suffices to show that when λ > λ 2 and λ > (3 + √ 8n + 1)/(2n − 2), a process that lives forever hits any big set. By duality again, this means that the process started from an infection at the root and run for a long time intersects an independent process initially infected on a sufficiently big set and run for a long time. This will be true because each of these processes will at some time infect a particular large configuration if it lives long enough (this uses λ > λ 2 ) and the configuration is chosen so that any future scenarios started from that configuration intersect with high probability. These two facts become the following two lemmas.
Proof: Assume without loss of generality that η is finite; an easy limit argument handles the infinite case. Fix λ > λ 2 . The first observation is that for any node v, P v (v ∈ ξ(t) for arbitrarily large t) = p > 0, where P v denotes P {v} , the contact process run from for arbitrarily large t) = 1. This follows from the Markov property and the fact that is bounded away from zero for a fixed finite S, fixed v ∈ T and any initial state of the contact process.
The last step in proving the lemma is to show that if the process lives forever then with probability 1 there is some v that is infected at an unbounded set of times. Assume to the contrary. Then there is some configuration η ′ such that conditional upon the process being in configuration η ′ at time t, the probability is greater than 1 − p that the process lives for ever but no node is infected at unbounded times. This contradicts the definition of p above, since η ′ must have at least one infected node, which is then infected at arbitrarily large future times with probability at least p. ✷ Lemma 2.6 Define a version of the contact process starting with a single infection at the root, where no vertex may infect its parent. Let ξ(t) and ξ ′ (t) be independent such processes, started simultaneously.
Proof: The argument will show that the set of nodes simultaneously infected in ξ and ξ ′ contains a supercritical branching process. This process Z will be coupled to ξ and Whether a node is ever alive in the Z process depends on: whether the parent was ever alive; the parent's lifetime, t 1 − t 0 ; and the attempted infections and recoveries at that node in the ξ and ξ ′ processes during the interval [t 0 , t 1 ). Since the distribution of attempted infections in an interval depends on the interval only through its length, and since lifetimes are i.i.d., Z is a Galton-Watson process. The mean number of offspring is easy to calculate exactly. The probability that v is ever alive given that the parent is born at time t is just the probability that v receives an attempted infection from its parent in both ξ and ξ ′ before its parent recovers. This is just 2λ/(2λ + 2) times λ/(λ + 2), the first of these being the probability that even one attempt arrives in time, and the second being the race between the other attempt and the recovery of the parent. The branching process is supercritical if n times this quantity is greater than 1, which happens when nλ 2 > λ 2 + 3λ + 2, and solving the inequality gives the condition in the statement of the lemma. Finally, note that Z(t) ⊆ ξ(t) ∩ ξ ′ (t), hence ξ(t) ∩ ξ ′ (t) = ∅ for all t when Z lives forever. ✷ Lemma 2.7 Let η be the configuration where the infected nodes are those at distance precisely r from the root, for some r > 0. Let λ be as large as in Lemma 2.6, and let ξ and ξ ′ be two independent versions of the contact process run from initial state η. Then for any ǫ > 0, r can be chosen large enough so that inf s,t P(ξ(s) ∩ ξ ′ (t) = ∅) > 1 − ǫ.
Proof: By duality, P(ξ(s)∩ξ ′ (t) = ∅) = P(ξ((s+t)/2)∩ξ ′ ((s+t)/2) = ∅), so it suffices to consider the case s = t. By monotonicity, the processes dominates altered versions where no node may infect its parent. These processes proceed independently on the subtrees below each of the (n + 1)n r−1 nodes in η, and on each subtree ξ and ξ ′ are versions of the process described in Lemma 2.6. By independence and the conclusion of Lemma 2.6, r can be chosen large enough so that ξ and ξ ′ intersect for all time on at least one of the subtrees with probability ≥ 1 − ǫ. ✷ Proof of (vii): Convergence in distribution is determined by finite-dimensional marginals, which by inclusion-exclusion are determined by the probabilities of infection existing in each finite set. So it suffices to show for finite sets S ⊆ T that P η (S ∩ ξ(t) = ∅) → µ(S ∩ ξ = ∅) times the survival probability of η. By duality, this is just the product of the survival probabilities of S and η.
Let ǫ > 0 be arbitrary and choose r as in Lemma 2.7. Let ξ and ξ ′ be independent versions of the contact process run from initial states S and η respectively. Let Let ξ ′′ and ξ ′′′ be independent contact processes run from the initial configuration in Lemma 2.7, coupled to ξ and ξ ′ respectively so that ξ ′′ (t) ⊆ ξ(t + τ ) whenever τ < ∞ The last expression converges to (1 − ǫ) times the product of the survival probabilities from S and η according to Lemma 2.5, since σ and τ are independent. Since ǫ is arbitrary, this shows lim inf t P η (S ∩ ξ(t) = ∅) is at least the product of the survival probabilities.
Duality gives trivially that lim sup t P η (S ∩ξ(t) = ∅) is at most the product of the survival probabilities, and the theorem is proved. ✷

Nonhomogeneous trees
The upper and lower bounds Theorem 2.2 gives for the critical values of λ 2 on homogeneous trees are within a constant factor. Since the constant may be quite large, it was reasonable to get some more accurate values for small n. In the case of nonhomogeneous trees, more work is needed just to get the bounds within a constant asymptotic factor, as shown by the example in the following paragraph. This section is therefore devoted to improving the bounds so that they are again within a constant factor of each other. This section does not discuss bounds on λ 1 per se, but when the trees are nonhomogeneous enough, the better upper bounds on λ 2 get pushed down by more than a constant factor below the upper bounds on λ 1 that can be obtained using the methods of the previous section, which means that the correct value of λ 1 in these cases is also more than a constant factor lower than can be gotten by the methods of the previous section. In fact, the last example of this section shows that λ 1 and λ 2 may both be zero on a Galton-Watson tree whose generating function has all moments. For ease of exposition, large constants are chosen with reckless abandon, leaving the interested reader the exercise of determining better constants.
To see that there is indeed a problem, try to apply the methods of the previous section to the following tree. The root has n children, each of which has only one child. Each of the n grandchildren has n children, and in general the number of children alternates between 1 and n along any direct lineage.
For an upper bound on λ 2 , adapt the method used to prove (iv). Let f (t) = P(ρ ∈ ξ(t)) as before, and let g(t) = P T ′ (ρ ∈ ξ(t)) where T ′ is the subtree rooted at a child of the root of T. Then the same argument as before gives f (t) ≥ H(g(t − 2r)) and where H is the same as in the proof of (iv) and J is similar but based on only 1 child. Then monotonicity of H gives , Lemma 2.4 together with equation (6) imply that λ > λ 2 whenever the quantity Q(r) in equation (5) satisfies e −4r Q(r) 4 · 1 · n > 1. This means λ must be of order n −1/4 as n gets large. Thus if G is the geometric mean of n and 1, an upper bound on the second critical value for λ is For trees with longer periodicity, the same argument yields λ 2 ≤ c √ G where G is the geometric mean of the whole sequence of family sizes.
On the other hand, the somewhat ad hoc methods in (iii) and (iii ′ ) can also be adapted to this tree to give lower bounds on λ 2 . The reader is invited to check that the best simple weighting scheme along the lines of (iii) for trees whose generation sizes alternate between a and b has the weight of a vertex with a children equal to √ a times the weight of each of its children, and the weight of a vertex with b children equal to √ b times the weight of each of its children (this scheme is not optimal when the periodicity of the generations is three or more). Under this weighting scheme, the total weight goes to zero almost surely whenever λ < 1/( √ a + √ b). When a = 1 and b = n, this gives the lower bound Thus the bounds in (7) and (8) have different asymptotics as n → ∞, one decreasing as n −1/4 and the other as n −1/2 , in contrast to the case where the tree was homogeneous and the bounds were always within a constant factor.
Which of these asymptotics for λ 2 is sharp, if either?
The somewhat surprising answer is that (8) is sharp, even though (7) is clearly a better representative for the growth rate of the tree. In fact for reasonably regular nonhomogeneous trees, the critical value of λ 2 is determined by M = the (essential) supremum of the number of children of a vertex and is at most a constant times rM −1/2 where r is a logarithmic measure of how far apart vertices with M children are from each other.
There are several kinds of nonhomogeneous trees one might wish to study. The periodic trees mentioned earlier in this section are one such class and Galton-Watson trees are another. Theorem 4.1 below will be used to obtain results about both of these cases. Since the proofs for Galton-Watson trees are harder, these will be given first and a brief version of the other will follow.
Let T be a Galton-Watson tree with generating function f = n≥0 a n x n , i.e. there is a root ρ and each vertex v has a random number C(v) of children, where C(v) are independent and each is equal to n with probability a n . Assume f ′ (1) > 1 so that the tree is infinite with probability p > 0. To run the contact process on a Galton-Watson tree that begins with only the root infected, choose T(ω) according to the Galton-Watson distribution and let ξ(t, ω | T(ω)) be the contact process run on the tree T(ω) starting with only the root infected.
Proposition 3.1 For a given offspring generating function f , let Then either q is almost surely zero or else P(q > 0 | |T| = ∞) = 1.
Proof: Let p 1 = P(q = 0). If the root has n children with subtrees T 1 , . . . , T n then the T i are independent, identically distributed with distribution independent of n. Furthermore, if q(T i ) > 0 for any i then q(T) > 0. To see this use the same argument as in (vi) of the last section for any fixed r to get P(ρ ∈ ξ(t)) ≥ e −2r Q 2 P T i (ρ ∈ ξ(t − 2r)).
Taking lim inf's over t gives q(T) ≥ a constant times q(T i ) for each i. Now by independence of the subtrees T i , p 1 = P(q(T) = 0) ≤ n a n (p 1 ) n = f (p 1 ). That means that either p 1 = 1 or p 1 is bounded above by the unique fixed point of f in (0, 1). In the first case q is almost surely zero and in the second case P(q = 0) is at most P(|T| < ∞); since it is also at least P(|T| < ∞), these two must be equal and the proposition is proved. ✷ In light of this, it is natural to define λ 2 (f ) to be the inf of λ such that q is almost surely nonzero for the contact process with parameter λ run on a Galton-Watson tree with generating function f conditioned to be infinite. The following upper bound on λ 2 can now be obtained.
The class of periodic trees may be defined in any of a number of ways so that a corresponding theorem is true. Here is one possible course broad enough to include the example at the beginning of this section. Let G be any finite graph with a root, ρ, a second distinguished vertex, σ, and another set of distinguished vertices v 1 , . . . v m distinct from each other. Suppose that for some j 1 and j 2 a path from σ to each v i of length at most j 2 exists that is disjoint from a fixed path of length j 1 connecting σ and ρ. Let n be 1 less than the number of neighbors of σ and let j = j 1 + j 2 . Construct a graph that will be a m-ary tree of G's as follows.
Let T (1) (G) = G. For each i ≥ 1 let T (i+1) (G) be a copy of G together with m copies of T (i) (G) but with ρ in the i th copy of T (i) identified with v i in the copy of G, so there remains only a single root in T (i+1) , namely the one from the copy of G. The increasing limit of these trees (as seen from the root) is the desired graph T(G). If G is a tree then so is T(G).
Theorem 3.3 For G, n, j, m and T(G) as above, let r be the maximum of 2 and ⌈j/ ln(m)⌉.
Then there is a constant c 4 such that λ 2 ≤ c 4 r ln(r) ln(n)/n.
The proofs of Theorems 3.2 and 3.3, will be given in section 5 since it relies on the results from section 4 on finite stars.

Finite stars
Let T be a star of size n, i.e. T consists of a root, ρ and n other vertices each connected only to ρ. Although any finite system is eventually trapped in the state of zero infection, this star turns out to be capable of storing the infection for a long time when λ is an appropriate constant times 1 / √ n. Since the application of these results is to get the two asymptotics is equations (7) and (8) to agree within a constant factor, there is no loss of generality in assuming n is greater than 64, say, so that n −1/2 and n −1/4 are actually distinguishable. It will also be convenient to restrict λ to being less than 1; again, nothing is lost, since all the critical values are less than 1 for n ≥ 64.
Before stating the theorems precisely, here is a heuristic explanation of the results.
Suppose n is large and let λ = a/ √ n for some constant a. Let x be the number of infected neighbors of ρ divided by √ n and pretend that x is a continuous rather than a discrete parameter. When the root is not infected, x decreases deterministically at a rate x (i.e. x = e −t x 0 ) and when the root is infected, x approaches a at rate 1 (i.e. x − a = e −t (x 0 − a)). The root, when infected, recovers at rate 1, and when healthy, is infected at rate (a/ √ n)(x √ n) = ax. In other words, the state of infection is a Markov process on where the second coordinate is x and the first coordinate is 0 if the root is healthy and 1 if the root is infected. Its natural scale can be calculated exactly, giving a which have the unique (up to affine transformation) solution From this it is easy to read off the behaviour of x(t) and in particular, to see that for k < l < m, the chance of hitting x = a/k before hitting x = a/m, starting from x = a/l is on the order e −a 2 (1/l−1/m) .
Returning to the actual situation, where the number of infections is integral, there are roundoff errors in the statement of an analogous result due to the greatest integer function, and roundoff errors in the proof due to the fact that the functions f and g are no longer very nice. To kill the roundoff error I require n to be larger than some N and choose sequentially a bunch of constants satisfying certain relations. The constants involved are named c 5 through c 13 and are fixed throughout once they are chosen. These can be evaluated easily by tracing the argument, but the value of N that this yields is far from optimal.
Theorem 4.1 Let c 9 , c 10 , c 11 be constants satisfying 1/4 > 1/c 10 + 1/c 11 > 1/c 10 > 1/c 9 > 0 and let c 5 satisfy 1/c 5 < 1/c 10 − 1/c 9 . For n a positive integer and a a positive real number, run the contact process on a star of size n with λ = a/ √ n and initially y nodes infected, where y = ⌊ a √ n c 10 ⌋. Then the conditions n > (1/c 10 − 1/c 9 − 1/c 5 ) −1 and 4 ≤ a ≤ √ n imply that the probability of the number of infected nodes dropping below a √ n/c 9 before reaching y + a √ n/c 11 is at most e a 2 /c 5 .
Corollary 4.2 If n is large enough then beginning with only ρ infected at time zero, the probability of the number of infected nodes staying above a √ n/c 9 during the time interval 1 ≤ t ≤ e a 2 /c 5 /2c 11 is at least e −1 /5.
Remarks: (1) The important fact here is that the infection lives for a time exponential in a 2 with a probability bounded away from zero; this is what creates the order ln(n)/n bound in Theorems 3.2 and 3.3, via equation (11) in the next section.
(2) As observed earlier, requiring n to be large and λ = a/ √ n to be less than 1 gives away nothing.
Proof of corrolary: The probability that ρ remains infected until at least time 1 is e −1 .
Remember this value: p 1 = e −1 . Conditioned on that, the probability of finding at least y nodes infected at time 1 is at least the probability of a binomial with parameters n and Q(1) being least y, where Q(1) = (a/(a + √ n))(1 − e −(1+a/ √ n) ) > (1 − e −1 )a/2 √ n is as in equation (5). The mean of this binomial is at least a √ n/4 and the variance is at most nQ(1) ≤ an/(a + √ n) so if n is large enough, the binomial is at least y = a √ n/c 10 with probability arbitrarily close to 1, say 4/5. Remember this too: p 2 = 4/5. Next, conditional on all that, Theorem 4.1 implies that the number of times the number of neighbors of ρ goes from y to y + a √ n/c 11 before becoming less than a √ n/c 9 dominates a geometric random variable with mean at least e a 2 /c 5 . Finally, if n is large enough to apply Theorem 4.1 then the waiting times for each new infection are independent from everything else and are at least exponential with mean 1/a √ n (the infection rate summed over all neighbors of the root is at most a √ n). The mean sum of a √ n/c 11 of these waiting times e a 2 /c 5 times over is thus at least e a 2 /c 5 /c 11 . Any sum of a geometric random number of i.i.d. exponential random variables is at least half its mean with probability at least 1/4 if the geometric has large enough mean. So the probability that the sum of the waiting times is at least e a 2 /c 5 /2c 11 conditional on there being at least e a 2 /c 5 transitions from y to y + a √ n/c 11 is at least 1/4. Call this p 3 . Now multiply p 1 , p 2 and p 3 to give the result. where x is the number of infected neighbors of ρ. This W is not a martingale like the heuristic one was, but reducing the exponent from ax/ √ n to ax/10 √ n makes it a supermartingale by, as will be evident, a comfortable margin. Note that by the size assumption on a, a/10 √ n ≤ .1 so e a/10 √ n −1 ≤ 1.2a/10 √ n, hence √ n(e a/10 √ n −1)/a ≤ .12 and W is always positive. Let τ be the first time that ρ has at least y +a √ n/c 11 < a √ n/4 For W (ξ(t ∧ τ )) to be a supermartingale, two inequalities must be satisfied. The transitions from (0, x) yield the inequality ax √ n √ n a e a/10 √ n − 1 ≥ x e a/10 √ n − 1 which is satisfied with equality. Setting k = ( √ n/a)(e a/10 √ n − 1), the transitions from (1, x) yield k + x(1 − k)(e a/10 √ n − 1) ≤ a √ n (n − x)(1 − k)e −a/10 √ n (e a/10 √ n − 1) and dividing out by 1 − k and by e a/10 √ n − 1 gives k (1 − k)(e a/10 √ n − 1) + x ≤ a √ n (n − x)e −a/10 √ n x + √ n a − √ n(e a/10 √ n − 1) ≤ a √ n (n − x)e −a/10 √ n e a/10 √ n √ nx + n e a/10 √ n a − √ n(e a/10 √ n − 1) ≤ an − ax (a + √ ne a/10 √ n )x ≤ n a − e a/10 √ n a − √ n(e a/10 √ n − 1) .
Since a ≤ √ n, the left hand side is at most (1 + e 1/10 ) √ nx, and since a ≥ 4, the right hand side is at least an(1 − e 1/10 /(4 − √ n)(e 2/5 √ n−1 )) > an/2 (the denominator on the right hand side has a local minimum at either endpoint of [4, √ n] with the absolute minimum at 4). Thus the inequalities are satisfied as long as 1.11 √ nx < an/2 which is always satisfied when x < a/4 √ n, which is always satisfied up to the stopping time.
To finish proving the theorem, suppose that ρ has y infected neighbors at time t, where y is as in the statement of the theorem. There is no loss of generality in the worst-case assumption that ρ is not infected at time t. Then W (ξ(t)) = e −ay/10 √ n and by definition of y, this is between e −a 2 /10c 10 and e −a 2 /10c 10 +a/10 √ n . But W (ξ) ≥ e −a 2 /10c 9 the first time the number of infected nodes falls below a √ n/c 9 . Use the fact that W is always positive together with the optional stopping theorem see that W can reach the value e −a 2 /10c 9 with probability at most exp(−a 2 /10c 10 + a/10 √ n + a 2 /10c 9 ). This gives the desired conclusion as long as a 2 /10c 10 − a/10 √ n − a 2 /10c 9 > a 2 /c 5 . Factoring out a 2 /10 yields the equivalent condition 1/c 10 − 1/c 9 − 1/c 5 > 1/a √ n and since a is at least 1, the condition n > (1/c 10 − 1/c 9 − 1/c 5 ) −1 finishes the proof. ✷ One more lemma will be needed for the next section, so record it now.
Lemma 4.3 Let n, a and λ be as in Theorem 4.1 and run the contact process on any graph containing the finite tree T where T consists of a star of size n with the root infected at time zero, to which has been added a single chain of length r of descendants of some child v 1 of ρ, denoted v 2 , . . . , v r . Then P(v r is infected before time e a 2 /c 5 /2c 11 ) > e −1 /5 − (1 − c r λ r ) (e a 2 /c 5 )/2c 11 r−2 (10) where c is a constant independent of everything else.
Proof: By monotonicity, it is sufficient to prove the statement for a modified contact process in which v 2 cannot infect v 1 , so the process restricted to the star of size n is unaffected by what happens at v 1 and below. Also by monotonicity assume without loss of generality that the graph is actually equal to T. Let B t be the event that the number of infected nodes of the star at time t is at least a √ n/c 9 , B = {B t : 1 ≤ t ≤ e a 2 /c 5 /1c 11 }, and let F t be the σ-algebra of events up to time t. Then P(v r is infected at some time s ∈ (t, t + r) | F t , B t ) is bounded below by the probability that ρ becomes infected before time t + 1 given F t , B t , times the product of the probabilities that v i infects v i + 1 before becoming uninfected and this happens within time 1. Working out these probabilities gives a lower bound of (cλ) r for a universal constant c.
Now let L = ⌊(1 + e a 2 /c 5 )/2c 11 r⌋ − 1, and consider a sequence of times Corollary 4.2 gives P(B) > e −1 /5 and since L is at least as big as the exponent in the right hand side of (10) the lemma is proved. ✷

Proofs of Theorems 3.2 and 3.3 and examples
Proof of Theorem 3.2: Assume without loss of generality that a n > 0 (or else r is infinite). Also, there is no loss of generality in assuming n to be large enough to apply Corollary 4.2, since c 2 and c 3 may be taken large enough so that c 3 r ln(r) ln(n)/n is at least 2 for any n that is too small, and 2 is an upper bound on all critical values on trees. By Proposition 3.1, is suffices to prove that lim inf t→∞ P(ρ ∈ ξ(t)) > 0 without conditioning on T. Let g(t) = P(ρ ∈ ξ(t)) ≥ a n P(ρ ∈ ξ(t) | ρ has at least n children).
To calculate g(t), condition on the root having at least n children until further notice.
Let c be the constant in Lemma 4.3. Treat r as a parameter to be determined later and choose a = a(r) so that e a 2 /c 5 /2c 11 r > 2 + 10(c r (a/ √ n) r ) −1 .
Using the inequality (1 − x) 1/x < e −1 , observe that (11) forces the right hand side of equation (10) to be at least c 8 = e −1 /4 − e −10 when λ is at least a/ √ n. To satisfy (11), it suffices to choose a > c 5 ln(2c 11 r · 10 · c −r 1 √ n r ) which is at most c 3 √ r ln r ln n for an appropriate c 3 as long as r ≥ 2. Set λ = a/ √ n. If this is sufficient to force P(q(T) > 0 | |T| = ∞) = 1 then λ 2 (f ) ≤ c 3 r ln(r) ln(n)/n as desired. Now the root has at least n children; select n of them and ignore the rest (by monotonicity). Among all the vertices at distance r from ρ, look for those having at least n children; call these v 1 r , . . . , v j r where j is the random cardinality of the set of such descendants. From the facts that ρ has n children, that each descendant has an expected f ′ (1) children and that a node has n children with probability a n , it follows that Now let M be the random number of vertices among v 1 r , . . . , v j r that are infected before e a 2 /c 5 /2c 11 . By the choice of a, Lemma 4.3, and the above expression for Ej, EM ≥ c 8 na n (f ′ (1)) r−1 . Now the argument proceeds as in (iv) of the previous section. Fix t and Let x be the minimum value of g(s) for 0 ≤ s ≤ t − e a 2 /c 5 /2c 11 . Recursively calculate a lower bound on g(t) as follows.
Ignoring all but the first infection of each v i r by its parent, any of these that are infected at some time s < t−e a 2 /c 5 /2c 11 will evolve independently from time s to time t−e a 2 /c 5 /2c 11 and then be infected with probability at least x = inf{g(s) : s ≤ t − e a 2 /c 5 /2c 11 }. Thus the distribution of the number of such nodes infected at time t − e a 2 /c 5 /2c 11 given M dominates a random variable M x that is binomial (M, x). Thus for small enough x, P(M x ≥ 1) ≥ x(EM − ǫ) for arbitrarily small ǫ. Finally, if some v i r is infected at time t − e a 2 /c 5 /2c 11 , then the probability of finding ρ infected at time t is bounded below by the probability, p 1 , that the contact process starting with only v i r infected at time t − e a 2 /c 5 /2c 11 infects ρ at some time s with t − e a 2 /c 5 /2c 11 ≤ s ≤ t times the probability p 2 that ρ is infected at time t given infection of ρ at some such time s. Then p 1 is at least c 8 by Lemma 4.3 and equation (11) with the star of size n centered at v i r this time. Meanwhile, p 2 is at least (e −1 /5)e −1 a 2 /(c 9 + a 2 ), which will be called c 13 . (See this by applying Corollary 4.2 together with the fact that the probability of ρ becoming reinfected between times t − 1 and t given at least a √ n/c 9 infections during this time, and then staying reinfected, is at least a 2 /(c 9 + a 2 ).) Thus as x → 0, g(t) is bounded below by c 8 c 13 xE(M) ≥ c 2 8 c 13 xna n (f ′ (1)) r−1 . Now choose c 2 so that putting r = c 2 ln(1/na n )/ ln(f ′ (1)) forces c 2 8 c 13 na n (f ′ (1)) r−1 to be greater than 1. Applying Lemma 2.4 then gives inf t g(t) > 0. ✷ Proof of Theorem 3.3: Passing to a subtree if necessary, assume without loss of generality that the parent of σ is on the unique path of length j 1 connecting ρ to σ and that there is a unique path connecting σ to each v i and it passes through a child of σ, not through the parent of σ.
For a positive integer q to be determined later, consider T(G) as being put together from units of size T (q) instead of from units of size G. Then ρ has at least n neighbors and furthermore it has at least m q descendants at distance at most qj, all of which continue recursively the property of having the right number of neighbors and wellendowed descendants.
Now use the argument for the previous theorem with m q instead of a n (f ′ (1)) r−1 .
Then a must be at least c 3 qj ln(qj) ln(n)/n as before, and the condition needed for Lemma 2.4 is that q is that c 2 8 c 13 m q > 1. This means that q = c ′ / ln(m) suffices, and setting r = qj/c ′ proves the theorem. ✷ A couple of examples conclude this section. The first shows that the the upper bound for λ 2 in Theorem 3.3 can be asymptotically sharp. In fact for this example it is shown that λ 1 is within a constant factor of the upper bound for λ 2 as n → ∞, so Theorem 3.3 provides asymptotically tight bounds on both critical values.

EXAMPLE
This example calculates λ 1 for a particular tree in order to show that the order ln(n)/n bound given by Theorem 3.3 may be sharp to within a constant factor. Let T be a homogeneous binary tree to every vertex of which has been added n children that have no children themselves. Thus each vertex has n + 2 children, only 2 of which have descendants. To get a lower bound on λ 1 , define the weight of a configuration as the sum over all nodes that have children of 1 if the node or any of its childless children are infected and 0 otherwise. The following partial converse to Corollary 4.2 will be needed.
Proposition 5.1 Let T be a star of size n with λ = a/ √ n < 1 as usual. There is an N for which n > N implies that the probability starting from configuration η of the infection dying out before time ln(n) + 2(ln |η| ∨ 4) is at least e −4a 2 /10.
Proof: First observe that from any configuration η, P η (|ξ(2(ln |η| ∨ 4))| < 2a To see this, couple the process on T to one on another star of size n, T ′ , where the root of T ′ always remains infected, but none of the children of ρ ′ in T ′ starts out infected.
The coupling has corresponding children of ρ and ρ ′ recover at the same times and has an infection occurring in T ′ whenever one occurs in T but not necessarily vice versa.
When every child of ρ has recovered once, the number of infected children of ρ is at most the number of infected children of ρ ′ . This happens by time 2(ln |η| ∨ 4) with probability (1−e −2(ln |η|∨4) ) |η| > 7/8. But the number of infected children of ρ ′ at any time is a random variable converging upwards to a stationary distribution that has mean approximately a √ n and for large enough n has probability less than 1/8 of being above 2a √ n. Thus the coupling establishes the observation. Now from a configuration where at most 2a √ n nodes are infected, it remains to show that the probability of the infection dying out within time ln(n) is at least e −4a 2 /7.5. The probability that no reinfection ever occurs is Going back now to the example, consider any node v that contributes 1 to the weight of the configuration either by having an infected child or by being a node with children that is itself infected. There are only three neighbors of v that may increase the weight of the configuration if they get infected by v, so the expected contribution of v to increasing the weight of the configuration in a time period of length 3 ln(n) is at most 9λ ln(n) = 9a ln(n)/ √ n.
The probability of v decreasing the weight during this time because the infection dies out on v and its childless children is at least e −4a 2 /10, by the beefed up version of the previous proposition (since |η| is necessarily at most n). Now pick a = ln(n)/10. This makes e −4a 2 /10 = n .1 /10 √ n/2 > 9 ln(n) ln(n)/10 √ n = 9a ln(n)/ √ n for large enough n. Thus any node contributes an expected weight that is less than 1 before it and its childless children all recover. The usual supermartingale argument then implies that the infection dies out almost surely and so for large enough n.
On the other hand, T is a periodic tree: T = T(G) for the graph G with root ρ = σ and n + 2 other vertices all connected only to the root, two of which are labelled v 1 and v 2 . In the notation of section 3, m = 2, j = 1 and what is called n in Theorem 3.3 is n + 2. Then Theorem 3.3 gives Thus for this class of trees, both (12) and (13)  Then ln(1/na n ) ≈ n γ , so Theorem 3.2 gives λ 2 ≤ c n γ−1 ln(n) which goes to zero as n → ∞. Thus λ 2 is less than any positive number, hence λ 1 = λ 2 = 0.

Continuity of the survival probability
Continuity from the right of the survival probability as a function of λ is immediate from the monotonicity, since versions of the process for each λ can all be coupled so that the event of survival is continuous from the right in λ. At the moment, I can only prove continuity from the left when the phase transitions at λ 1 and at λ a are distinct. It is also necessary to assume that the tree is homogeneous or periodic. In particular, the survival probability is a continuous function of λ for homogeneous trees with n > 2. I believe that survival probability is continuous for arbitrary trees.
I will present the argument that λ 1 < λ a implies continuity of the survival probability only for homogeneous trees; the generalization to periodic trees is straight-forward but tedious. In the foregoing discussions, let p(λ) denote the survival probability for the contact process on an n-ary homogeneous tree with only the root infected initially. Begin with a counting lemma.
Definition 6.1 For a finite set S ⊆ T, say a vertex v ∈ S is surrounded in S iff each of the n + 1 components of T \ {v} intersects S. The rest of the discussion deals with the contact process on a tree with a severed edge.
For each positive integer r, let ξ (r) be a contact process run from an initial infection at the root with an edge severed at distance r from the root, i.e. no infection passes over that edge. Write ξ (r;λ) or ξ (;λ) when it is necessary to emphasize the choice of λ. An adjacent edge counts as being at distance one. The main lemma on continuity from the left is the following.
Lemma 6.3 Let T be a homogeneous tree. For a fixed λ, let ξ (r) be as above, and suppose the survival probability for the infection in ξ (r) is positive for some r. Then the survival probability for the unaltered contact process is continuous from the left for that value of λ.
Remark: There is a corresponding lemma in percolation theory stating that the percolation probability is continuous provided that percolation in Z d implies percolation in a half-space.
Proof: First note that r can be taken to be 1, since the initial infection in the ξ (1) process has a nonzero chance of moving to a distance r from the severed edge before it dies, thus dominating a ξ (r) process a postive fraction of the time.
For this paragraph, let the infection rate be understood to be λ ′ . Let S ⊆ ξ (1;λ ′ ) (t) be the random subset of the infected nodes at time t that are not surrounded in the set of infected nodes at time t. Since 1 − 1/n ≥ 1/2, Lemma 6.2 shows that S contains at least half the nodes infected at time t. Thus P(|S| ≥ 5(1 + λ ′ )/2λ ′ p) ≥ p/2.
For each v ∈ S there is by definition of S some neighbor, say g(v) for which the component of T \ v containing g(v) does not intersect ξ (1;λ ′ ) (t). For each such v, the probability is λ ′ /(1 + λ ′ ) that v will pass the infection on to g(v) before recovering. Let A be the random set of such v. Forbid any infection of nodes in S from time t onward. Then the process proceeds independently on each component of T \ S containing some x ∈ A, since communication has been severed. Furthermore, the starting configuration on each such component is precisely a single infection and the process evolves as ξ (1;λ ′ ) , since an edge next to the initial edge has been severed. Then the ξ (1) process dominates a set of independent ξ (1) processes, started from each vertex in A. As in the theory on Galton-Watson processes, the survival probability is greater than the fixed point of a generating function for the probabilities of the various cardinalities of A. This must be positive if E|A| > 1. Since E(|A| | |S| > 5(1 + λ ′ )/2λp) > 5/2p, the desired result follows from equation (14).
Rerun the previous argument but for infection rate λ ′′ . Let S be the unsurrounded infected nodes in ξ (;λ ′′ ) (t), so each v ∈ S has a neighbor g(v) in a component of T \ S with no infection. There is a set A of nodes g(v) for v ∈ S, that are infected before v recovers. Formally A is the set of nodes g(v) sucht that v ∈ S and there exists a t ′ > t for which v is infected throughout the time interval [t, t ′ ] and such that v infects g(v) at time t ′ . The binomial hypothesis on M guarantees that A has cardinality at least M with probability at least q − 3ǫ/4, since each g(v) is independently in A with probability λ ′′ /(1+λ ′′ ). Each node in A defines an independent process which is a restarted version of ξ (1) with parameter λ ′′ ≥ λ ′ , so the hypothesis on p(λ ′ ) and M gives a survival probability of at least q − ǫ for the whole process. Since ǫ was arbitrary, the lemma is proved. ✷ It remains to show that the hypothesis of this lemma is satisfied when the phase transitions at λ 1 and λ a are distinct. This is done in two steps.
Lemma 6.4 Suppose the contact process is run on a homogenous tree for some λ < λ a .
Proof: Suppose not. Then by monotonicity it decreases to some bound b > 0. Since λ < λ a the root is infected finitely often almost surely, so there is some time t and configuration η such that P(survival without infecting the root any more | ξ(t) = η) > 1 − b. Since any node alive at time t infects the root with probability at least b, this is a contradiction. ✷ Lemma 6.5 Suppose λ < λ a . Then the survival probability for ξ (r) on a homogenaous tree approaches the survival probability for the unaltered contact process as r → ∞.
Proof: Couple all the ξ (r) with the unaltered process, so that they evolve identically until an infection in the unaltered process crosses an edge that is severed in the other process.
By Lemma 6.4 the probability of the processes ever becoming uncoupled goes to zero as r goes to infinity, and the result follows. ✷ Putting all these lemmas together gives Theorem 6.6 If λ 1 < λ a then the survival probability for the contact process from a single initial infection on a homogeneous tree is continuous in λ.
Proof: When the survival probability is zero there is nothing to prove. When it is positive and λ < λ a then some ξ (r) also has positive survival probability by Lemma 6.5, and continuity follows from Lemma 6.3. For λ ≥ λ a , the existence of a λ between λ 1 and λ a implies the survival with positive probability of a severed-edge contact process for that and hence all higher λ, and Lemma 6.3 again applies. ✷