The time of bootstrap percolation in two dimensions

We study the percolation time of the $r$-neighbour bootstrap percolation model on the discrete torus $(\Z/n\Z)^d$. For $t$ at most a polylog function of $n$ and initial infection probabilities within certain ranges depending on $t$, we prove that the percolation time of a random subset of the torus is exactly equal to $t$ with high probability as $n$ tends to infinity. Our proof rests crucially on three new extremal theorems that together establish an almost complete understa...

We consider first-passage percolation on $\mathbb{Z}^2$ with i.i.d. weights, whose distribution function satisfies $F(0) = p_c = 1/2$. This is sometimes known as the "critical case" because large clusters of zero-weight edges force passage times to grow at most logarithmically, giving zero time constant. Denote $T(\mathbf{0}, \partial B(n))$ as the passage time from the origin to the boundary of the box $[-n,n] \times [-n,n]$. We characterize the limit behavior of $T(\mathbf{...

Consider a cellular automaton with state space $\{0,1 \}^{{\mathbb Z}^2}$ where the initial configuration $\omega_0$ is chosen according to a Bernoulli product measure, 1's are stable, and 0's become 1's if they are surrounded by at least three neighboring 1's. In this paper we show that the configuration $\omega_n$ at time n converges exponentially fast to a final configuration $\bar\omega$, and that the limiting measure corresponding to $\bar\omega$ is in the universality c...

Bootstrap percolation on a graph with infection threshold $r\in \mathbb{N}$ is an infection process, which starts from a set of initially infected vertices and in each step every vertex with at least $r$ infected neighbours becomes infected. We consider bootstrap percolation on the binomial random graph $G(n,p)$, which was investigated among others by Janson, \L uczak, Turova and Valier (2012). We improve their results by strengthening the probability bounds for the number of...

We investigate the behaviour of $r$-neighbourhood bootstrap percolation on the binomial $k$-uniform random hypergraph $H_k(n,p)$ for given integers $k\geq 2$ and $r\geq 2$. In $r$-neighbourhood bootstrap percolation, infection spreads through the hypergraph, starting from a set of initially infected vertices, and in each subsequent step of the process every vertex with at least $r$ infected neighbours becomes infected. For our analysis the set of initially infected vertices i...

In $r$-neighbor bootstrap percolation on the vertex set of a graph $G$, a set $A$ of initially infected vertices spreads by infecting, at each time step, all uninfected vertices with at least $r$ previously infected neighbors. When the elements of $A$ are chosen independently with some probability $p$, it is natural to study the critical probability $p_c(G,r)$ at which it becomes likely that all of $V(G)$ will eventually become infected. Improving a result of Balogh, Bollob\'...

In majority bootstrap percolation on a graph G, an infection spreads according to the following deterministic rule: if at least half of the neighbours of a vertex v are already infected, then v is also infected, and infected vertices remain infected forever. Percolation occurs if eventually every vertex is infected. The elements of the set of initially infected vertices, A \subset V(G), are normally chosen independently at random, each with probability p, say. This process ...

This paper analyzes various questions pertaining to bootstrap percolation on the $d$-dimensional Hamming torus where each node is open with probability $p$ and the percolation threshold is 2. For each $d'<d$ we find the critical exponent for the event that a $d'$-dimensional subtorus becomes open and compute the limiting value of its probability under the critical scaling. For even $d'$, we use the Chen-Stein method to show that the number of $d'$-dimensional subtori that bec...

In the bootstrap percolation model, sites in an L by L square are initially infected independently with probability p. At subsequent steps, a healthy site becomes infected if it has at least 2 infected neighbours. As (L,p)->(infinity,0), the probability that the entire square is eventually infected is known to undergo a phase transition in the parameter p log L, occurring asymptotically at lambda = pi^2/18. We prove that the discrepancy between the critical parameter and its ...

Graph bootstrap percolation, introduced by Bollob\'as in 1968, is a cellular automaton defined as follows. Given a "small" graph $H$ and a "large" graph $G = G_0 \subseteq K_n$, in consecutive steps we obtain $G_{t+1}$ from $G_t$ by adding to it all new edges $e$ such that $G_t \cup e$ contains a new copy of $H$. We say that $G$ percolates if for some $t \geq 0$, we have $G_t = K_n$. For $H = K_r$, the question about the size of the smallest percolating graphs was independe...