Bootstrap percolation in three dimensions

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 r-neighbour bootstrap percolation on a graph G, a (typically random) set A of initially 'infected' vertices spreads by infecting (at each time step) vertices with at least r already-infected neighbours. This process may be viewed as a monotone version of the Glauber dynamics of the Ising model, and has been extensively studied on the d-dimensional grid $[n]^d$. The elements of the set A are usually chosen independently, with some density p, and the main question is to dete...

In r-neighbour bootstrap percolation on a graph G, a set of initially infected vertices A \subset V(G) is chosen independently at random, with density p, and new vertices are subsequently infected if they have at least r infected neighbours. The set A is said to percolate if eventually all vertices are infected. Our aim is to understand this process on the grid, [n]^d, for arbitrary functions n = n(t), d = d(t) and r = r(t), as t -> infinity. The main question is to determine...

Consider a $p$-random subset $A$ of initially infected vertices in the discrete cube $[L]^d$, and assume that the neighbourhood of each vertex consists of the $a_i$ nearest neighbours in the $\pm e_i$-directions for each $i \in \{1,2,\dots, d\}$, where $a_1\le a_2\le \dots \le a_d$. Suppose we infect any healthy vertex $v\in [L]^d$ already having $r$ infected neighbours, and that infected sites remain infected forever. In this paper we determine the $(d-1)$-times iterated log...

The $r$-neighbour bootstrap percolation process on a graph $G$ starts with an initial set $A_0$ of "infected" vertices and, at each step of the process, a healthy vertex becomes infected if it has at least $r$ infected neighbours (once a vertex becomes infected, it remains infected forever). If every vertex of $G$ eventually becomes infected, then we say that $A_0$ percolates. We prove a conjecture of Balogh and Bollob\'as which says that, for fixed $r$ and $d\to\infty$, ev...

Graph bootstrap percolation is a deterministic cellular automaton which was introduced by Bollob\'as in 1968, and is defined as follows. Given a graph $H$, and a set $G \subset E(K_n)$ of initially `infected' edges, we infect, at each time step, a new edge $e$ if there is a copy of $H$ in $K_n$ such that $e$ is the only not-yet infected edge of $H$. We say that $G$ percolates in the $H$-bootstrap process if eventually every edge of $K_n$ is infected. The extremal questions fo...

We study a new geometric bootstrap percolation model, line percolation, on the $d$-dimensional integer grid $[n]^d$. In line percolation with infection parameter $r$, infection spreads from a subset $A\subset [n]^d$ of initially infected lattice points as follows: if there exists an axis-parallel line $L$ with $r$ or more infected lattice points on it, then every lattice point of $[n]^d$ on $L$ gets infected, and we repeat this until the infection can no longer spread. The el...

In r-neighbour bootstrap percolation on the vertex set of a graph G, vertices are initially infected independently with some probability p. At each time step, the infected set expands by infecting all uninfected vertices that have at least r infected neighbours. We study the distribution of the time t at which all vertices become infected. Given t = t(n) = o(log n/log log n), we prove a sharp threshold result for the probability that percolation occurs by time t in d-neighbou...

In the $r$-neighbour bootstrap process on a graph $G$, vertices are infected (in each time step) if they have at least $r$ already-infected neighbours. Motivated by its close connections to models from statistical physics, such as the Ising model of ferromagnetism, and kinetically constrained spin models of the liquid-glass transition, the most extensively-studied case is the two-neighbour bootstrap process on the two-dimensional grid $[n]^2$. Around 15 years ago, in a major ...

For $r\geq1$, the $r$-neighbour bootstrap process in a graph $G$ starts with a set of infected vertices and, in each time step, every vertex with at least $r$ infected neighbours becomes infected. The initial infection percolates if every vertex of $G$ is eventually infected. We exactly determine the minimum cardinality of a set that percolates for the $3$-neighbour bootstrap process when $G$ is a $3$-dimensional grid with minimum side-length at least $11$. We also characteri...