Bootstrap percolation in high dimensions

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...

Two-dimensional bootstrap percolation is a cellular automaton in which sites become 'infected' by contact with two or more already infected nearest neighbors. We consider these dynamics, which can be interpreted as a monotone version of the Ising model, on an n x n square, with sites initially infected independently with probability p. The critical probability p_c is the smallest p for which the probability that the entire square is eventually infected exceeds 1/2. Holroyd de...

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...

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...

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...

In $r$-neighbour bootstrap percolation, vertices (sites) of a graph $G$ are infected, round-by-round, if they have $r$ neighbours already infected. Once infected, they remain infected. An initial set of infected sites is said to percolate if every site is eventually infected. We determine the maximal percolation time for $r$-neighbour bootstrap percolation on the hypercube for all $r \geq 3$ as the dimension $d$ goes to infinity up to a logarithmic factor. Surprisingly, it tu...

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 the polluted bootstrap percolation model, the vertices of a graph are independently declared initially occupied with probability p or closed with probability q. At subsequent steps, a vertex becomes occupied if it is not closed and it has at least r occupied neighbors. On the cubic lattice Z^d of dimension d>=3 with threshold r=2, we prove that the final density of occupied sites converges to 1 as p and q both approach 0, regardless of their relative scaling. Our result pa...

In the modified bootstrap percolation model, sites in the cube {1,...,L}^d are initially declared active independently with probability p. At subsequent steps, an inactive site becomes active if it has at least one active nearest neighbour in each of the d dimensions, while an active site remains active forever. We study the probability that the entire cube is eventually active. For all d>=2 we prove that as L\to\infty and p\to 0 simultaneously, this probability converges to ...

Answering questions of Itai Benjamini, we show that the event of complete occupation in 2-neighbour bootstrap percolation on the d-dimensional box [n]^d, for d\geq 2, at its critical initial density p_c(n), is noise sensitive, while in k-neighbour bootstrap percolation on the d-regular random graph G_{n,d}, for 2\leq k\leq d-2, it is insensitive. Many open problems remain.