{'fraction_non_alphanumeric': 0.05309274379910645, 'fraction_numerical': 0.0178131258665845, 'mean_word_length': 3.955057251908397, 'pattern_counts': {'":': 0, '<': 23, '<?xml version=': 0, '>': 18, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 17, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
First passage percolation and competition models

This paper is a survey of various results and techniques in first passage percolation, a random process modeling a spreading fluid on an infinite graph. The latter half of the paper focuses on the connection between first passage percolation and a certain class of stochastic growth and competition models.


Introduction
First passage percolation is a random process on a (typically infinite) graph. Hammersley and Welsh [HW65] introduced first passage percolation as a model of fluid flow through a randomly porous medium. In this model, each edge e in the graph is assigned a random nonnegative number τ (e), called the passage time of e, which is interpreted as the time it takes to cross the edge in either direction. In other contexts, τ (e) may represent a weight or a capacity, but we shall stick with the passage time interpretation. The picture to keep in mind is that of a fluid emanating from some source vertex and flowing outward through the edges of the graph according to the prescribed passage times. Equivalently, one can think of an infection spreading out from some initial locus and transmitted between neighboring vertices at random times.
First passage percolation can be defined on any graph, but the most commonly studied model is the one in which the underlying graph is the integer lattice Z d for d ≥ 2. This is the model we will focus on, although we briefly discuss models on certain random infinite graphs in § 2.6. The most basic results in first passage percolation rely on ergodic theory and the theory of subadditive processes. In fact, the study of first passage percolation was an impetus for the development of Kingman's subadditive ergodic theorem [Kin68]. A good general reference detailing the fundamental results in first passage percolation is [Kes86].
Based on heuristic arguments, the growing interface described by first passage percolation is believed to belong to the Kardar-Parisi-Zhang (KPZ) universality class [KPZ86] of models in statistical physics. In particular, the Eden growth model [Ede61], which can be described in terms of a particular first passage percolation process, has been studied extensively in this context. We will define the Eden growth model in § 3.1. In § 2.4 we will see some of the progress that has been made in verifying various predictions from statistical physics.
The rest of the paper is organized as follows. In § 2, after giving the precise definition of the first passage percolation process and introducing some of the topics of interest, we summarize the early results in the subject and proceed to describe some of the more recent work that has been carried out. In § 3 we describe how to define growth processes and competition models based on first passage percolation and summarize recent work in this direction.

First passage percolation 2.1 Basic definitions
Let Z d be the integer lattice of dimension d ≥ 2, which we consider both as a graph and as a subset of R d . Two vertices u, v ∈ Z d are adjacent if ||u − v|| 1 = 1, and we denote the edge set of Z d by E(Z d ). Let {τ (e)} e∈E(Z d ) be a collection of nonnegative random variables indexed by the edges. We call τ (e) the passage time of the edge e, and it represents the time needed to cross the edge in either direction. The joint law of the passage times τ (e) determines the first passage percolation process.
In order to do anything useful with the first passage percolation model, we need to make some assumptions about the distribution of the passage times. Typically, the minimal assumption one makes is that the passage times {τ (e)} e∈E(Z d ) are stationary and ergodic with respect to translations of Z d . More explicitly, we can consider the canonical sample space Ω = (R + ) E(Z d ) , equipped with some probability measure ν defined on the product σ-field. If ω ∈ Ω is a realization of ν, the passage times for ω are given by τ ω (e) = ω(e). Now, for each u ∈ Z d , let θ u : Ω → Ω be the natural shift operator defined by θ u ω(e) = ω(e + u), where the notation "e + u" has the obvious meaning. The passage times τ (e) are stationary if for each u, the measure ν is θ u -invariant (i.e. ν • θ −1 u = ν). Stationary passage times are ergodic if any event which is invariant under every θ u has probability 0 or 1 (i.e. any event A ⊂ Ω such that θ −1 u A = A for all u must satisfy ν(A) ∈ {0, 1}). Throughout the rest of the paper we will assume that the passage times are stationary and ergodic, and we will be most interested in the case where they are in fact independent and identically distributed (i.i.d.) and have finite expectation. In particular, our focus in § 3 will be on i.i.d. exponential passage times.
We now define several concepts that will be discussed in more detail in later sections. Suppose that {τ (e)} e∈E(Z d ) is a collection of passage times describing a first-passage percolation process on Z d . If γ is a path in Z d , then the passage time of γ is If U, V ⊂ Z d , the passage time from U to V is T (U, V ) = inf{T (γ) : γ is a path from U to V }.
(2.1.1) (If U or V is a singleton, we will write its unique element in place of the set when using this notation or other similar notation.) We can extend this definition to subsets of R d as follows: If A ⊂ R d , let A consist of all the lattice points that are closest to A, i.e.
We refer to T ( 0, n) as a point-to-point passage time and T ( 0, H n ) as a point-tohyperplane (or point-to-line when d = 2) passage time. We will see in § 2.2 that the passage times T ( 0, n) and T ( 0, H n ) satisfy a law of large numbers (Theorem 2.2), which shows that first passage percolation has an asymptotic speed along the coordinate axes. One of the primary objects of interest in first passage percolation is the set B(t) of vertices that can be reached from the origin by time t, or a continuum versionB(t) of this set in which each v ∈ B(t) is replaced with a unit cube centered at v. That is, If we think of the percolation process as modeling an infection spreading outward from the origin, B(t) is the set of vertices which are infected at time t. (We will return more explicitly to this interpretation of B(t) in § 3, where we discuss growth and competition models.) One of the fundamental results about first passage percolation is that, under some mild hypotheses for the passage times,B(t)/t converges almost surely to a deterministic shape (Theorem 2.4), so the process in fact has an asymptotic speed in all directions simultaneously. We will discuss this so called shape theorem further in § 2.3, and in § 2.4 we will discuss the related question of deviation bounds for the convergence.
Another topic that arises naturally in the study of first passage percolation is that of time-minimizing paths, or geodesics. For sets U, V ⊂ R d , if T (U, V ) = T (γ) for some (necessarily finite) lattice path γ (i.e. γ achieves the infimum in (2.1.1)), we call γ a geodesic from U to V , and we denote any such path by G(U, V ). More generally, a finite or infinite where u ′ and v ′ are the endpoints of γ ′ . Observe that a finite path γ with endpoints u and v is a geodesic if and only if γ = G(u, v). When the passage times are i.i.d., it is easy to see that G(u, v) exists and is unique a.s. for each u, v ∈ Z d if and only if τ (e) is a continuous random variable (see e.g. [WW98,Lemma 8]). See [GM05,§ 4] for conditions guaranteeing the existence and uniqueness of finite geodesics with stationary passage times. We will discuss the existence of infinite geodesics in § 2.5.

The subadditive ergodic theorem and the time constant
One property of the point-to-point passage times {T ( m, n)} 0≤m<n that is immediate from the definition (2.1.1) is This motivates the following definition: A doubly indexed process {X m,n } 0≤m<n is called subadditive if X 0,n ≤ X 0,m + X m,n for all 0 < m < n.
The main result about subadditive processes is the subadditive ergodic theorem, which was developed by Kingman [Kin68] to study point-to-point passage times and is now a standard tool in first passage percolation and other applications. The following version, due to Liggett [Lig85a], is an improvement on Kingman's original result. (Instead of (b) and (c) below, Kingman assumed that the distribution of {X m+k,n+k } 0≤m<n does not depend on k, in which case it follows from (a) that X ℓ,n ≤ X ℓ,m + X m,n for all ℓ < m < n.) Theorem 2.1 (Subadditive ergodic theorem [Kin68], [Lig85a]). Suppose X m,n , 0 ≤ m < n, is a family of random variables satisfying (a) X 0,n ≤ X 0,m + X m,n for all 0 < m < n.
(c) The distribution of the sequence {X m,m+k } k≥1 does not depend on m.
(ii) The limit X = lim n→∞ X 0,n /n exists and is less than +∞ a.s.
(iii) If there is some c < ∞ such that E X − 0,n ≥ −cn for all n, then the convergence in (ii) also holds in L 1 , so EX = γ.
(iv) If the stationary sequences in (b) are ergodic, then X = γ a.s.
If the random variables in Theorem 2.1 are all degenerate, then the theorem reduces to a well-known result about subadditive functions (see e.g. [Kal02,p. 191] or [Kin73]). On the other hand, if {ξ k } k≥1 is a stationary sequence with E |ξ k | < ∞, then X m,n := ξ m+1 +. . .+ξ n satisfies (a)-(d) and (iii) (with equality in (a), so the process {X m,n } is in fact additive), and Theorem 2.1 reduces to Birkhoff's ergodic theorem in this case.
If the passage times τ (e) are stationary and ergodic with finite expectation, the random variables X m,n := T ( m, n), 0 ≤ m < n, are easily seen to satisfy (a)-(d), (iii), and (iv) of Theorem 2.1, so T ( 0, n)/n converges a.s. to some constant µ 1 < ∞. The constant µ 1 is known as the time constant in the direction 1, and its reciprocal is the the asymptotic speed of the first passage percolation process along the coordinate axes. When the passage times are i.i.d., it turns out that the scaled point-to-hyperplane passage times T ( 0, H n )/n converge to the same constant µ 1 . This was first proved by Wierman and Reh [WR78], and can be deduced from the shape theorem (Theorem 2.4 below -see [Kes86,). (Note that the process T ( m, H n ) is not subadditive, so we cannot apply Theorem 2.1 directly.) We restate these two results for i.i.d. passage times in the following theorem. Finally, we mention two basic results about the time constant µ 1 in the case of i.i.d. passage times. First, it is easy to see that in general µ 1 < E[τ (e)] (see [HW65, Theorem 4.1.9]). Also, observe that µ 1 = 0 corresponds to infinite percolation speed, so that the process has superlinear growth. There is a simple criterion for deciding when this occurs. A proof of Proposition 2.3 can be found in [Kes86,§ 6]. A heuristic argument goes as follows. If Pr[τ (e) = 0] > p c (Z d ), then there is a.s. an infinite cluster in Z d on which the travel time between any two vertices is zero. It will a.s. take only finite time to reach this cluster from the origin, at which point the process can head off in any direction with infinite speed. On the other hand, if Pr[τ (e) = 0] < p c (Z d ), then a.s. all the clusters on which infinite speed can occur have finite size. Thus, the process can only travel a finite distance before it has to step off one of these clusters and accumulate some positive travel time before reaching the next cluster. It is not too hard to show that this accumulated travel time must with high probability increase linearly with the distance traveled, so that the asymptotic speed is finite a.s. The situation at the critical value p c (Z d ) is a bit more delicate, but Proposition 2.3 shows that the asymptotic speed in this case is infinite.

The shape theorem
It is natural to generalize the idea of the time constant and consider the speed of percolation in arbitrary directions rather than just along the coordinate axis. In particular, for any x ∈ R d with rational coordinates, we can apply Theorem 2.1 to see that there is some constant µ(x) such that T ( 0, nx)/n → µ(x) a.s. With this notation we have µ 1 = µ( 1). For i.i.d. passage times, it is not difficult to show that the function µ : is Lipschitz continuous and hence can be extended to all of R d , and that the resulting function µ : R d → [0, ∞) is either identically zero or defines a norm on R d . We will refer to µ as the norm for the first passage percolation process when appropriate; more generally, we will refer to µ as the shape function for the process because of its role in the shape theorem, which we now describe.
Recall the definitions of the growing shapes Under some moment conditions on the passage times, it can be shown thatB(t)/t converges almost surely to the unit µ-ball B 0 = {x ∈ R d : µ(x) ≤ 1} as t → ∞. This result is known as the shape theorem, and an in probability version was first proved by Richardson  . , e 2d } is any set of 2d distinct edges). Let µ be the shape function for the process, let µ 1 = µ( 1) be the time constant, and let B 0 = {x ∈ R d : µ(x) ≤ 1}.
1. If µ 1 > 0, then B 0 is compact and convex with nonempty interior, and for any ǫ > 0, for all large t almost surely.
2. If µ 1 = 0, then µ ≡ 0 (so B 0 = R d ), and for any compact set K ⊂ R d , for all large t almost surely.
The moment condition on the passage times in Theorem 2.4 is optimal, in the sense that if it fails then lim sup v→∞ T ( 0, v)/||v|| 1 = ∞ a.s. However, even without any moment conditions on the passage times τ (e), it is possible to define modified passage times T (u, v) for u, v ∈ Z d and a corresponding set B(t) such that an analogue of Theorem 2.4 holds (see [Kes86]). By Proposition 2.3, we see that The convexity of B 0 follows from subadditivity, and when B 0 = R d , compactness and nonempty interior follow from the fact that µ is a norm. Otherwise, little is known about the limit shape B 0 other than the obvious fact that it must have all the symmetries of Z d . Kesten [Kes86,§ 8] shows that if the passage times are i.i.d. exponential and d is large, then B 0 is not a Euclidean ball, casting doubt on the conjecture that B 0 might be a disc for d = 2 based on early Monte Carlo simulations [Ede61]. Durrett and Liggett [DL81] show that there are i.i.d. passage times for which B 0 has flat edges but is not a diamond or a square. In particular, this occurs if τ (e) is nontrivial but attains some nonzero minimum value with probability greater than p dir There is also a version of the shape theorem for stationary passage times. Boivin [Boi90] proves that if the passage times τ (e) are stationary, ergodic, and have finite moment of order d + ǫ for some ǫ > 0, then B(t)/t converges a.s. to a deterministic shape B 0 . In the stationary case, the shape function µ may take on both zero and strictly positive values so that the limit shape B 0 can be an unbounded proper subset of R d . However, if µ(x) > 0 for every unit vector x, then B 0 is compact, convex, has nonempty interior, and is symmetric with respect to reflection through the origin. (B 0 may fail to have further symmetries since isotropy may not hold in the non-i.i.d. case.) Conversely, Häggström and Meester [HM95] show that any set B 0 ⊂ R d with these properties can arise as the limit shape for some collection of stationary passage times.

Deviations in the passage times and the growing shape
Throughout this section we will assume that the passage times {τ (e)} e∈E(Z d ) are i.i.d. and satisfy the hypotheses of Theorem 2.4 so that B(t)/t → B 0 a.s. We further assume that Pr[τ (e) = 0] < p c (Z d ) so that µ 1 > 0 and the limit shape B 0 is compact.

The variance of T ( 0, n)
Once we know that B(t) converges, we can ask how much it deviates from the limit shape B 0 . There are various ways to approach this problem. As a first step, we consider the variance of T ( 0, n). It is predicted that the standard deviation of T ( 0, n) is of order n χ for some constant χ = χ(d). Based on heuristic arguments from statistical physics, it is expected that χ(2) = 1/3 (see e.g. [KS91], [KPZ86]). This conjecture is supported by simulations and by rigorous results for related growth models (e.g. [BDJ99], [Joh00a], [Joh00b]), which we shall discuss in § 2.7. The situation is less clear for higher dimensions d, although it is generally believed that χ is nonincreasing in d (see [NP95] for a discussion). So far, the only general bound on χ, due to Kesten, is χ(d) ≤ 1/2 for all d: Theorem 2.5 (Kesten [Kes93]). If E[τ (e) 2 ] < ∞, then there are positive constants c 1 and c 2 such that Kesten proves Theorem 2.5 using martingale methods (the "method of bounded differences"). Although Theorem 2.5 provides the best known bounds for a general distribution on the passage times, better bounds have been proved for certain classes of distributions. For example, Benjamini, Kalai, and Schramm [BKS03] use an inequality of Talagrand [Tal94, Thm. 1.5] to show that Var[T ( 0, n)] = O(n/ log n) if the passage times have the uniform distribution on {a, b}, where 0 < a < b. They note that the essential feature of first passage percolation needed to prove both their result and Kesten's is that the number of edges e ∈ E(Z d ) such that modifying τ (e) increases T ( 0, n) is bounded by a constant times n. Building on the methods in [BKS03], Benaïm and Rossignol [BR06a] use a Gaussian version of Talagrand's [Tal94] inequality and apply the techniques of [BKS03] to prove O(n/ log n) variance for a large class of i.i.d. absolutely continuous passage times, including exponential.
As for lower bounds on the variance, Newman and Piza [NP95] prove that in dimension d = 2, Var[T ( 0, n)] = Ω(log n) under certain hypotheses on the passage times. In particular, if we set λ = inf{x : Pr(τ (e) ≤ x) > 0}, the condition assumed in [NP95] is that Based on Proposition 2.3 and the results in [DL81], this condition is necessary for the shape B 0 to be compact and for its boundary to have no flat edges; it is suspected that (2.4.1) should also be sufficient for this to hold (see [NP95]). Pemantle and Peres [PP94] use different methods to prove Ω(log n) variance for the special case of exponential passage times in d = 2. On the other hand, for higher dimensions d, it is still not known whether the variance of T ( 0, n) even diverges as n → ∞.

Large deviation bounds for T ( 0, n)
If the assumption of finite variance for the passage times is strengthened to the existence of a finite exponential moment, then one can obtain good bounds on the deviation of T ( 0, n) from its expected value, and on the deviations of E[T ( 0, n)] from nµ. The following theorem is due primarily to Kesten [Kes93], with the upper bound in (2.4.3) being an improvement made by Alexander.
Theorem 2.6 (Kesten [Kes93], Alexander [Ale93]). If E[e γτ (e) ] < ∞ for some γ > 0, then there exist positive constants c 1 , c 2 , c 3 , c 4 , c 5 , such that and Note that the lower bound in (2.4.3) strengthens the trivial inequality E[T ( 0, n)] ≥ nµ implied by Theorem 2.1. Both Theorems 2.5 and Theorem 2.6 remain valid if T ( 0, n) is replaced by T ( 0, H n ) (see [Kes93] or [Ale93]), or if n is replaced by any v ∈ Z d and n is replaced by ||v|| 1 . In fact, using versions of (2.4.2) and (2.4.3) valid for arbitrary directions, Kesten [Kes93, Theorem 2] shows that there is some constant C (depending on the dimension d and the distribution of τ (e)) such that almost surely, is replaced with a median of T ( 0, n). For the same class of distributions considered in [BR06a] (with the added assumption of finite exponential moment), Benaïm and Rossignol [BR06b] prove that (2.4.2) still holds if the √ n in the denominator is replaced by n/ log n.
Instead of the Talagrand-type inequalities used in [BR06a], the techniques used in [BR06b] involve modified Poincaré inequalities arising from the context of "threshold phenomena" for Boolean functions.

Scaling exponents for the growth process
In the statistical physics literature (see e.g. [KS91]), the fluctuations of a randomly growing shape such asB(t) are studied in terms of two exponents χ and ξ, which describe respectively the longitudinal and transverse fluctuations in the surface ofB(t). For example, it is expected that the standard deviation of the time T ( 0, H) at whichB(t) first reaches a hyperplane H at distance r from the origin is of order r χ , while the set of points in H which are likely to be first reached byB(t) is expected to have diameter on the order of r ξ . There are various ways to define χ and ξ precisely, and it is an open problem to determine whether the various definitions are equivalent. The exponents χ and ξ are not expected to depend on the underlying distribution of the τ (e)'s, at least under certain hypotheses (for example, (2.4.1) above -see [NP95] or [LNP96]). A priori, χ and ξ could depend on the direction of travel, but it is expected that they should be the same in any direction in which the boundary of B 0 has nonzero curvature, at least in low dimensions. The values of χ and ξ are expected to depend on the dimension d, but heuristic arguments suggest that the scaling identity χ = 2ξ − 1 holds in all dimensions (see [KS91]). As noted in the introduction, first passage percolation models are expected to belong to the KPZ universality class [KPZ86], leading to the prediction that χ(2) = 1/3 and (in accordance with the scaling identity) ξ(2) = 2/3.
We now describe some of the progress that has been made towards computing the exponents χ and ξ. Since χ and ξ might depend on the direction of travel, we will write χx and ξx to denote their values in the direction of some unit vectorx ∈ R d . In [NP95], Newman and Piza show that in any dimension d, if (2.4.1) holds, then χx ≥ (1−(d−1)ξx)/2 (this was proved by Wehr and Aizenman [WA90] for d = 2). Then they show that, under the same hypothesis (2.4.1), if the passage times have finite exponential moment, then ξx ≤ 3/4 for anyx which is a direction of curvature for B 0 (i.e. a direction in which the boundary of B 0 has nonzero curvature). For d = 2, this yields χx ≥ 1/8 in any direction of curvaturex, improving the previously mentioned logarithmic lower bound on Var[T ( 0, nx)]. It is easy to show that any compact convex set has a direction of curvature [NP95, Lemma 5], so in d = 2 there is at least one directionx such that Var[T ( 0, nx)] = Ω(n 1/4 ) when the τ (e)'s have finite exponential moment.

Infinite geodesics
Recall that a geodesic is a time-minimizing path in first passage percolation, and that G(U, V ) denotes a geodesic between the sets U and V when such a path exists. Suppose that G(u, v) exists and is unique for each pair of vertices u, v ∈ Z d . For any u ∈ Z d , we define the tree of infection of u, Γ(u), to be the (graph theoretic) union of all the finite geodesics starting at u: The fact that Γ(u) is a tree follows from the uniqueness of the geodesics. If we think of the percolation process as modeling an infection spreading outward from u, then the unique path in Γ(u) from u to another vertex v traces the route by which v became infected. Let K(Γ(u)) denote the number of topological ends in Γ(u) -that is, the number of semi-infinite paths in Γ(u) starting at u. We call any such path a one-sided geodesic starting at u. A standard compactness argument shows that K(Γ(u)) ≥ 1 for any u. (The set of finite geodesics starting at u can be viewed in a natural way as a compact space, so it must contain a limit point since it has infinitely many elements.) In [New95], Newman uses the Kesten-Alexander deviation bounds (Theorem 2.6) and methods similar to those in [NP95] to show that if the passage times are i.i.d. and the curvature of the boundary of B 0 is uniformly bounded away from 0, then K(Γ(u)) = ∞ a.s. for any u. While the assumption of uniform curvature is plausible, there are no i.i.d. probability measures on the passage times for which B 0 is known to have this property. Hoffman [Hof05b] has shown that K(Γ(u)) = ∞ under a much weaker assumption on the limit shape, namely that B 0 is not a polygon. Although there are no i.i.d. passage times which are known to satisfy this assumption either, the result of [HM95] shows that there are stationary passage times for which it holds. We will revisit this topic in § 3.3, where we discuss the connection between the existence of geodesics and the question of coexistence in a certain competition model obtained as a projection of first passage percolation.
Newman proves the above result by considering geodesics with an asymptotic direction. Ifx is a unit vector in R d and γ is a one-sided geodesic with vertices v 0 , v 1 , v 2 , . . ., then γ has asymptotic directionx if lim n→∞ v n /||v n || 2 =x, and we call γ anx-geodesic. It is not known in general whetherx-geodesics exist or whether every one-sided geodesic must have a direction, but Newman [New95] gives affirmative answers to both questions under the assumption that B 0 is uniformly curved. Licea and Newman [LN96] use some of the ideas in [New95] to prove a uniqueness result forx-geodesics when d = 2: Theorem 2.7 (Licea and Newman [LN96]). Suppose the passage times {τ (e)} e∈Z 2 are i.i.d. with continuous distribution. Then for Lebesgue almost everyx on the unit circle, Pr (There exist disjointx-geodesics) = 0, and hence any twox-geodesics must coalesce.
Naturally, in addition to one-sided geodesics, one can also consider two-sided geodesics, i.e. geodesics which are infinite in both directions instead of just one. In contrast to onesided geodesics, it is unclear whether two-sided geodesics exist at all. (Since a two-sided geodesic does not have a fixed starting point, the compactness argument used to prove the existence of one-sided geodesics fails in this case.) Most of the work on two sided-geodesics has focused on the case of continuous i.i.d. passage times in d = 2, where it is expected that two-sided geodesics do not exist. We summarize some results in this direction.
In [Weh97], Wehr shows that almost surely, the number of 2-sided geodesics is either 0 or ∞ in d = 2, and that an analogous result holds in d dimensions for locally weightminimizing hypersurfaces instead of curves. This result is equivalent to the statement that the number of ground states in the random exchange Ising model (REIM) is 2 or ∞ a.s.
Using Theorem 2.7, Licea and Newman [LN96] show that for Lebesge-a.e. unit vector x ∈ R 2 , there cannot exist an (x, −x)-geodesic, i.e. a two-sided geodesic with asymptotic directionsx and −x. Wehr and Woo [WW98] show that if H is any half-plane in R 2 , then there can exist no two-sided geodesics contained entirely within H. As a corollary, any two-sided geodesic must intersect every line with rational slope.

Isotropic models of first passage percolation
As we have seen on various occasions above, one disadvantage of the first passage percolation model on Z d is that we do not have much information about the limit shape B 0 . One way to get around this is to define a stochastically isotropic model so that symmetry considerations imply that B 0 must be a Euclidean ball. For example, Vahidi-Asl and Wierman [VAW90] introduce models in which the underlying graph is either a random Voronoȋ tesselation of the plane or its dual Delaunay triangulation, where the centers of the Voronoȋ cells are given by a Poisson point process on R 2 . Howard and Newman [HN97] introduce a different model, in which the underlying graph is the complete graph with vertices given by a Poisson point process on R d and the passage times are given by τ (e) = |e| α , where α > 1 and |e| denotes the Euclidean distance between the endpoints of e.
Using a random graph for the for the percolation process introduces various technical problems, but nevertheless, versions of many of the results familiar from the Z d model still hold for these Euclidean models. For example, in the Voronoȋ and Delaunay models, there is a time constant [VAW90], a shape theorem [VAW92], and deviation bounds similar to those in Theorems 2.5 and 2.6 [Pim05]. Furthermore, since B 0 has uniform curvature in this model, Pimentel [Pim04] is able to use the techniques in [NP95] and [New95] to show that the transversal fluctuation exponent ξ ≤ 3/4, and that almost surely, every onesided geodesic has an asymptotic direction and there exists a one-sided geodesic in every direction. Similar results are proved by Howard and Newman for their model in [HN97], [HN99], and [HN01]. We also mention that [Pim04] contains results about a competion model on the Delaunay triangulation analogous to the competition model on Z d described in § 3.3 below.

Directed first passage and last passage percolation
The process we have been referring to as first passage percolation is more properly called undirected first passage percolation. One can also consider directed first passage percolation or a related model called (directed) last passage percolation. Both of these models are defined similarly to undirected first passage percolation, except that only increasing paths (defined below) are allowed. Certain versions of directed last passage percolation are much better understood than undirected first passage percolation. We now describe the directed models and summarize some of the most interesting results.
Let {τ (e)} e∈Z d be a collection of i.i.d. nonnegative passage times. A path γ in Z d is called increasing if each step in γ is made by increasing a single coordinate by 1. For If u ≤ v, define the (directed) first-passage time from u to v to be T min (u, v) = min{T (γ) : γ is an increasing path from u to v}, and define the last-passage time from u to v to be T max (u, v) = max{T (γ) : γ is an increasing path from u to v}, where T (γ) is defined as in the undirected case. As before, we can extend these definitions to passage times between two points in R d . The directed models are often defined with passage times τ (v) on the vertices v of Z d rather than the edges, but the analysis is similar with either convention, so we will stick with edge passage times.
As with the undirected first-passage times, the directed first-passage times are subadditive, whereas the last-passage times are superadditive, i.e. for vertices u Applying Theorem 2.1 to the first-passage times and a superadditive version of Theorem 2.1 to the last-passage times implies that there are shape functions g, h : Furthermore, we can define growing shapes analogous to B(t): Under appropriate conditions on the distribution of τ (e), Martin [Mar03] proves a shape theorem for the directed models: In the first-passage case, subadditivity implies that U 0 is convex, whereas in the last-passage case, superadditivity implies that In contrast with the undirected model, there are two special cases of directed lastpassage percolation in d = 2 for which the shape function h(x) is known explicitly. A theorem of Rost [Ros81] (see also [BS04], [Mar03]) implies that for exponential passage times with mean 1, Johansson [Joh00a] shows that for geometric passage times with parameter q, These are the only two nontrivial cases where the shape function for i.i.d. passage times is known, in any of the directed or undirected, first-or last-passage models. However,  [BDJ99] to show that the passage times T max ( 0, nx), appropriately centered and scaled, converge in distribution to the Tracy-Widom [TW94] distribution for the largest eigenvalue in a random matrix sampled from the Gaussian Unitary Ensemble (GUE). In particular, it is shown that the standard deviation of T max ( 0, nx) in this model is of order n 1/3 , so that χ = 1/3 in accordance with the predictions of KPZ universality [KPZ86].
Finally, we mention another model which can be viewed as a continuum version of the directed last-passage percolation model defined above, and in fact can be obtained as a limit of last-passage percolation with i.i.d. geometric passage times (see, e.g. [Joh02]). This model was introduced by Hammersley [Ham72] as a method for approaching Ulam's problem [Ula61] of finding the distribution of the longest increasing subsequence in a random permutation.
Consider a unit-rate Poisson process on R 2 . Analogous to increasing lattice paths, we can define an increasing path between Poisson points to be a path γ that moves only up and to the right. That is, γ is a sequence of Poisson points such that if x and x ′ are consecutive points in γ, then x ≤ x ′ . We define the length of γ to be the number of Poisson points it contains. Let L(r) be the length of the longest increasing path between Poisson points contained in the square [0, r] 2 . Conditional on the event that [0, r] 2 contains N points, L(r) has the same distribution as the length of the longest increasing subsequence in a random (uniform distribution) permutation of {1, 2, . . . , N} (see [Ham72]). Baik, Deift, and Johansson [BDJ99] show that lim r→∞ Pr L(r) − 2r where F(s) is the Tracy-Widom distribution for the largest eigenvalue of a GUE random matrix. The r 1/3 in the denominator shows that χ = 1/3 for this model, where χ is the exponent describing the longitudinal fluctuations of a maximal increasing path. Moreover, Johansson [Joh00b] applies the techniques from [NP95] and [LNP96] to show that the transversal fluctuations of the maximal paths have exponent ξ = 2/3, verifying the scaling identity χ = 2ξ − 1 for this model.

Richardson's growth model and competition models 3.1 The 1-type Richardson model
First passage percolation can be put into the framework of interacting particle systems (see e.g. [Lig85b]) by defining a {0, 1} Z d -valued process {η t } t≥0 given by We may think of sites in state 0 as healthy and sites in state 1 as infected, so that the process represents an infection spreading outward from the origin.
When the passage times are i.i.d. exponentials with parameter λ > 0, the memoryless property implies that the process η t is Markovian. In this case the process is called Richardson's growth model [Ric73], also known as the "contact process with no recoveries," in comparison with the similarly defined contact process (cf. [Lig85b]). In Richardson's growth model, a site in state 1 remains infected forever and tries to infect each of its 2d neighbors at rate λ. Thus, the rate at which an uninfected site flips from 0 to 1 is equal to λ times the number of infected neighbors it has. Only the origin is infected at time 0.
As noted in [Ric73], this process is related to a discrete time process called Eden's growth model [Ede61], defined as follows: Set A 1 = { 0}, and for n > 1 set A n = A n−1 ∪{v n }, where v n is chosen from the set of uninfected sites with probability proportional to the number of neighbors it has in A n−1 . Then A n has the same distribution as B(t n ), where t n = inf{t : B(t) contains n vertices}.

The 2-type Richardson model
In [HP98], Häggström and Pemantle introduced the two-type Richardson model. In this model, instead of one type of particle spreading throughout the lattice, there are two species of particles competing for space. This competition is described by a {0, 1, 2} Z dvalued Markov process {ξ t } t≥0 with parameters λ 1 and λ 2 which determine the flip rates as follows: 1's and 2's never flip, while a 0 flips to a 1 (resp. a 2) at rate λ 1 (resp. λ 2 ) times the number of neighbors of type 1 (resp. 2). The 1's and 2's represent sites infected by species 1 and 2, respectively, and 0's represent uninfected sites.
One natural question we can ask in the two-type model is whether both species continue growing indefinitely or whether one species ends up surrounded by the other so that it is only able to infect a finite number of sites. If A 1 and A 2 are two disjoint subsets of Z d , we denote by Coex(A 1 , A 2 ) the event that both species eventually infect an infinite number of sites when species i initially occupies the sites in A i , and we call this event coexistence or mutual unbounded growth for the initial configuration (A 1 , A 2 ). It is easy to see that Pr(Coex(A 1 , A 2 )) < 1 unless both of the sets A 1 and A 2 are already infinite, so the first nontrivial question to ask is whether Pr(Coex(A 1 , A 2 )) > 0. Clearly coexistence is impossible if one of the sets A i surrounds the other set A j , i.e. if there is no infinite path starting in A j that does not intersect A i . We say that the pair (A 1 , A 2 ) is fertile if neither set surrounds the other. Deijfen and Häggström showed that as long as the initial configuration of the process is finite and fertile, the choice of configuration is irrelevant to the question of whether coexistence has positive probability: Theorem 3.1 (Deijfen and Häggström [DH06a]). If (A 1 , A 2 ) and (A ′ 1 , A ′ 2 ) are two fertile pairs of disjoint finite sets in Z d , then for any pair of growth rates λ 1 and λ 2 , Weaker versions of Theorem 3.1 (in which the sets A i and A ′ i consist of single points) appeared in [HP98] and [GM05], and most treatments of coexistence have simply focused on the case where the initial configuration is ({ 0}, { 1}).
Intuitively, if the growth rates λ 1 and λ 2 are equal, we might expect that coexistence occurs with positive probability since neither species has an inherent advantage over the other. This result was in fact proved for d = 2 in [HP98], and subsequently generalized to any d ≥ 2 in [GM05] and [Hof05a]. On the other hand, if the growth rates are different, say λ 1 > λ 2 , then unless species 2 gets lucky and surrounds species 1 relatively quickly, species 1 is likely to overtake species 2 by virtue of its superior speed, making coexistence implausible. Häggström and Pemantle conjecture in [HP98] that Pr(Coex( 0, 1)) = 0 when λ 1 = λ 2 and prove a somewhat weakened version of this conjecture in [HP00]. In the next two sections we discuss the two-type Richardson model in more detail in the two cases λ 1 = λ 2 and λ 1 = λ 2 .

Competition with equal growth rates
The two-type Richardson model is somewhat simpler to analyze when both species grow at the same rate. If λ 1 = λ 2 = λ, we can obtain the two-type process ξ t as the projection of a single first passage percolation process with i.i.d. exponential(λ) passage times, analogous to the definition of η t in the one-type model. If the process starts with initial configuration (A 1 , A 2 ), then Note that the definition of ξ t can be generalized in an obvious way to model competition between k species with equal growth rates and initial configuration (A 1 , . . . , A k ), for any k ≥ 1. Since the two-type (or k-type) model and the one-type model are both defined in terms of an underlying first passage percolation process, results about one model can often be translated into results about the other, as will be illustrated below.
Häggström and Pemantle first addressed the question of coexistence for species with equal growth rates in [HP98], where they proved that Pr[Coex( 0, 1)] > 0 when d = 2. The main step in their proof was to show that in the related one-type process starting at 0, there are infinitely many sites in the right half-plane which have a > 50% probability of being infected after their neighbor to the left, so that these sites "sense" that the infection is coming from the left. From there, it is a small step to show that in the two-type process, with positive probability there are infinietly many sites in the right half plane that are reached by species 2 before they are reached by species 1, and that a symmetric situation holds in the left half-plane.
Observe that the definition of ξ t makes sense for more general passage time distributions, although the Markov property holds only in the i.i.d. exponential case. However, for any stationary distribution of passage times, the two species will still be growing at the same average rate, and we might expect coexistence to hold in the stationary case as well. Indeed, Garet and Marchand [GM05] and Hoffman [Hof05a] independently generalized the coexistence result of [HP98] to a large class of stationary ergodic passage times in any dimension d ≥ 2. Furthermore, an analogue of Theorem 3.1 holds in the stationary case so that the starting configuration is still irrelevant [GM05,p. 312].
Coexistence in the two-type or k-type model is related to the existence of one-sided geodesics in the corresponding one-type model. If coexistence of k species occurs, then the same compactness argument used to show that K(Γ( 0)) ≥ 1 shows that there exist k disjoint one-sided geodesics in the underlying first passage percolation process, one starting in each of the initial sets A 1 , . . . , A k . Therefore, denoting coexistence in the k-type model by Coex (A 1 , . . . , A k ) and the existence of disjoint geodesics G i starting in the sets A i by Geo(A 1 , . . . , A k ), we have (3.3.1) Furthermore, if Geo(A 1 , . . . , A k ) occurs, it seems plausible that some finite modification of passage times might allow the construction of k one-sided geodesics starting at 0 so that Pr[K(Γ( 0)) ≥ k] > 0. In fact, at least when k = 2 (and probably for any k -see [Hof05b]), we can go in the other direction as well, from geodesics to coexistence: For the class of stationary measures considered in [GM05] or [Hof05a], it can be shown (see [GM05,Lemma 5.3]) that Thus, since coexistence of two species occurs with positive probability, there are at least two one-sided geodesics starting at 0 with positive probability. In fact, while Garet and Marchand [GM05] use techniques similar to those in [HP98] to prove that coexistence is possible and then conclude that there are at least two geodesics with positive probability, Hoffman [Hof05a] first proves that there almost surely exist at least two distinct onesided geodesics (not necessarily with the same starting point) and uses this to show that coexistence has positive probability.
In [Hof05b], Hoffman applies the techniques in [Hof05a] to the k-type model to obtain further results about both geodesics and coexistence when d = 2 and the passage times are given by a certain class of "good" ergodic stationary measures ν. Although the results are stated only for d = 2, the methods can be applied to any d ≥ 2. We now state the main results, which depend on the geometry of the limit shape B 0 corresponding to ν. For a good measure ν, let Sides(ν) be the number of sides of ∂B 0 if ∂B 0 is a polygon or infinity if ∂B 0 is not a polygon.
The points u i in Theorem 3.2 are chosen to be the lattice points closest to points u ′ 1 , . . . , u ′ k ∈ ∂(rB 0 ) at which the tangent lines of ∂(rB 0 ) are distinct (such points exist by the assumption that k ≤ Sides(ν)). The idea of the proof is that if v 1 , . . . , v k are points on ∂B 0 with distinct tangent lines L v 1 , . . . , L v k , then with positive probability, for each i there will be infinitely many n such that v i is closer (in travel time) to the translated line nv i + L v i than any of the other points v j are. This shows that if the process starts with initial configuration (v 1 , . . . , v k ) (assuming v i ∈ Z 2 ), each v i will infect infinitely many sites with positive probability, so coexistence occurs. By scaling the picture up by a sufficiently large factor r, the probability of coexistence can be made arbitrarily close to 1.
Hoffman also obtains the following results about one-sided geodesics starting at 0.
Theorem 3.4 (Hoffman [Hof05b]). Let ν = (L(τ )) ⊗E(Z 2 ) , where τ is an exponential random variable. If k ≤ Sides(ν), then Observe that by symmetry, we must have Sides(ν) ≥ 4 when d = 2, so Theorem 3.2 shows that coexistence of four species is possible for any good measure ν, and Theorem 3.4 shows that with i.i.d. exponential passage times it is possible to get four one-sided geodesics starting at 0. Furthermore, in [DL81] it is shown that there is a nontrivial i.i.d. measure ν such that B 0 is neither a square nor a diamond, so by symmetry we must have Sides(ν) ≥ 8. Thus, Theorem 3.2 implies that there is a nontrivial i.i.d. measure ν for which coexistence of eight species is possible. In [HM95] it is shown that there exists a good measure ν such that B 0 is the unit disc, so Theorem 3.3 implies that there exists a good measure ν such that K(Γ( 0)) = ∞ a.s.

Competition with different growth rates
If the growth rates λ 1 and λ 2 are different for the two species, we can construct the Markov process ξ t from two independent i.i.d. exponential first passage percolation processes on Z d , one with parameter λ 1 and the other with parameter λ 2 . However, the description of ξ t is not quite as simple as it was in the case of equal growth rates because, with two underlying sets of passage times instead of just one, there is no guarantee that the geodesics between infected vertices of one species will not cross geodesics of the other species. For this reason, the values of ξ t must be defined iteratively by considering the process at the time t n of the n th infection. We mention that the state of the process at time t n can be described analogously to Eden's growth model for the one-type process, except that the edge causing the next infection is chosen from all edges on the boundary with probability proportional to λ i if the edge borders species i.
In [HP98], Häggström and Pemantle conjecture that coexistence in the two-type Richardson model is impossible if λ 1 = λ 2 . While the full conjecture is still an open problem, Häggström and Pemantle were able to prove the slightly weaker result that coexistence is impossible for almost all choices of parameter values: Theorem 3.5 (Häggström and Pemantle [HP00]). For the two-type Richardson model on Z d , d ≥ 2, with λ 1 = 1 we have Pr(Coex( 0, 1)) = 0 for all but at most countably many choices of λ 2 .
By time scaling, the probability of coexistence depends only on the ratio λ = λ 2 /λ 1 , so Theorem 3.5 remains true for any other choice of λ 1 . Furthermore, the same time-scaling argument plus symmetry implies that the probabilities of coexistence for the pairs (1, λ) and (1, 1/λ) are equal, so it suffices to consider the case λ 1 = 1 and λ 2 = λ ∈ [0, 1].
At first glance, it may seem strange that Theorem 3.5 has not been extended to include all values of λ 2 = λ 1 . Intuitively, we expect that Pr(Coex( 0, 1)) should decrease as λ = λ 2 /λ 1 moves farther away from 1. Since Theorem 3.5 implies that we can choose λ arbitrarily close to 1 such that Pr(Coex( 0, 1)) = 0, such monotonicity would imply that coexistence is impossible for all λ = 1. However, it is not obvious how to prove that the probability of coexistence is monotone in λ. In fact, although this monotonicity property is certainly plausible for the integer lattice Z d , Deijfen and Häggström [DH06b] have shown that there are other (highly non-symmetric) graphs where monotonicity does not hold.
We now give a brief outline of the proof of Theorem 3.5 from [HP00]. The main tool is the following proposition, which we state as it appears in [DH06c]. Let P λ 1 ,λ 2 A 1 ,A 2 denote the law of the two-type process with rates λ 1 , λ 2 and initial configuration (A 1 , A 2 ). For i = 1, 2, let G i be the event that species i finally infects an infinite number of sites (so Coex(A 1 , A 2 ) = G 1 ∩ G 2 ), and let B 0 denote the limit shape for the one-type Richardson model with rate 1. Then where the supremum is over all initial configurations (A 1 , A 2 ) such that For example, Proposition 3.6 says that if we start the process with with the slow species occupying the entire µ-ball of radius r and the fast species occupying a single site outside the µ-ball of radius (1 + ǫ)r (where µ is the norm for the unit rate Richardson model), the survival probability of the slow species goes to zero as r → ∞. Using Proposition 3.6 and the strong Markov property, Häggström and Pemantle show that if Coex( 0, 1) occurs, the set of sites infected by both species, scaled by t, converges a.s. to the limit shape of the slow species.
To prove Theorem 3.5, Häggström and Pemantle first describe a coupling Q of the processes P 1,λ 0, 1 (λ ∈ [0, 1]) such that Q-a.s., for all t, the set 1's at time t decreases with λ, and the set of 2's at time t increases with λ. Writing Coex(λ) for the event that Coex( 0, 1) occurs at parameter λ under the law Q, they use the above result to show that Q-a.s., Coex(λ) occurs for at most one λ ∈ [0, 1]. That is, 1 Coex(λ) ≤ E Q 1 = 1.
Therefore, since the sum on the left is finite, there can be only countably many λ's such that Q(Coex(λ)) > 0, which proves Theorem 3.5 since Q(Coex(λ)) = P 1,λ 0, 1 (Coex( 0, 1)). While the results in [HP00] apply only to finite initial configurations, Deijfen and Häggström [DH06c] recently proved some interesting results about coexistence in the case when one of the initial sets A i is infinite. In particular, they considered the cases where A 1 is either the hyperplane H = H 0 = {z ∈ Z d : z 1 = 0} (minus the origin) or the half line L = {z ∈ Z d : z 1 ≤ 0 and z i = 0 for all i = 1} (minus the origin), and A 2 = { 0}. Their main result is The fact that coexistence is impossible if λ 1 > λ 2 for either H or L follows from Proposition 3.6 since whenever A 1 is infinite while A 2 is finite, the pair (A 1 , A 2 ) satisfies (3.4.1) for all sufficiently large r. The "if" direction of 1 is proved by combining a shape theorem for the one-type process starting from H (which is proved using the large deviation bounds of Theorem 2.6) with a shape theorem for the "hampered" one-type process starting from 0 and restricted to a cylinder about the first coordinate axis (which follows from a standard modification of the proof of the ordinary shape theorem). The strategy of proof is to show that when λ 1 < λ 2 , there is a positive probability that species 2 gets a big enough head start over species 1 that it is able to take over the entire cylinder without interference. The corresponding result for L follows from the result for H because (a rotation of) L is a subset of H, and the probability of survival for either species is monotone with respect to the starting configuration [DH06c, Lemma 3.1].
For the critical case λ 1 = λ 2 , the proof that coexistence is possible when A 1 = L \ { 0} follows techniques similar to those used in [HP98]. In fact, the coexistence result for A 1 = L \ { 0} when λ 1 = λ 2 allows an easy proof of the the coexistence result in [HP98] (see [DH06c,Theorem 6.1]). The proof that coexistence is impossible when A 1 = H \ { 0} is rather more involved, and we will not discuss it here. We mention, however, that this result shows that in a one-type process started from H, almost surely every vertex in H will infect only a finite number of vertices in Z d .
As was the case with equal growth rates, the definition of the process ξ t in terms of first passage percolation makes sense for more general passage times, although again, Markovity will be lost in the non-exponential case. In [GM06], Garet and Marchand extend the results of [HP00] to include i.i.d. passage times which are not necessarily exponential but for which the passage time distributions for the two species are stochastically comparable. In this setting, they show that for any d, if the slow species survives, the fast species cannot occupy a very high density of space (for example, "it could not be observed by a medium resolution satellite"). For d = 2, they show that almost surely, one species must finally occupy a set of full density in the plane while the other species occupies only a set of null density. They also obtain deviation bounds similar to those in [HP00] showing that if coexistence occurs then the infected region in the two-type process must grow essentially according to the law of the first passage percolation process governing the slow species. Finally, they prove an analogue of Theorem 3.5 for families of stochastically comparable passage times indexed by a continuous parameter, showing that coexistence cannot occur except perhaps for a countable set of parameters.