2005/02/01 by Christopher Hoffman · 83 citations
Mathematics · #Algorithm #Combinatorics #Conjecture #Discrete mathematics #Ergodic theory #Graph #Markov Chains and Monte Carlo Methods #Mathematics #Pure mathematics #Random Matrices and Applications #State (computer science) #Stochastic processes and statistical mechanics #Vertex (graph theory)
paper · pdf · doi:10.1214/105051604000000729
published in The Annals of Applied Probability 15(1B) (Institute of Mathematical Statistics)
openalex publication_date 2005/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/27
We study a large family of competing spatial growth models. In these models the vertices in ℤd can take on three possible states 0,1,2. Vertices in states 1 and 2 remain in their states forever, while vertices in state 0, which are adjacent to a vertex in state 1 (or state 2), can switch to state 1 (or state 2). We think of the vertices in states 1 and 2 as infected with one of two infections, while the vertices in state 0 are considered uninfected. In this way these models are variants of the Richardson model. We start the models with a single vertex in state 1 and a single vertex in state 2. We show that with positive probability state 1 reaches an infinite number of vertices and state 2 also reaches an infinite number of vertices. This extends results and proves a conjecture of Häggström and Pemantle [J. Appl. Probab. 35 (1998) 683–692]. The key tool is applying the ergodic theorem to stationary first passage percolation.