The second term for two-neighbour bootstrap percolation in two dimensions

Let $G_{n,p}^1$ be a superposition of the random graph $G_{n,p}$ and a one-dimensional lattice: the $n$ vertices are set to be on a ring with fixed edges between the consecutive vertices, and with random independent edges given with probability $p$ between any pair of vertices. Bootstrap percolation on a random graph is a process of spread of "activation" on a given realisation of the graph with a given number of initially active nodes. At each step those vertices which have ...

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

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

In this paper a random graph model $G_{\mathbb{Z}^2_N,p_d}$ is introduced, which is a combination of fixed torus grid edges in $(\mathbb{Z}/N \mathbb{Z})^2$ and some additional random ones. The random edges are called long, and the probability of having a long edge between vertices $u,v\in(\mathbb{Z}/N \mathbb{Z})^2$ with graph distance $d$ on the torus grid is $p_d=c/Nd$, where $c$ is some constant. We show that, {\em whp}, the diameter $D(G_{\mathbb{Z}^2_N,p_d})=\Theta (\lo...

Bootstrap percolation is a wide class of monotone cellular automata with random initial state. In this work we develop tools for studying in full generality one of the three `universality' classes of bootstrap percolation models in two dimensions, termed subcritical. We introduce the new notion of `critical densities' serving the role of `difficulties' for critical models, but adapted to subcritical ones. We characterise the critical probability in terms of these quantities a...

Bootstrap percolation has been used effectively to model phenomena as diverse as emergence of magnetism in materials, spread of infection, diffusion of software viruses in computer networks, adoption of new technologies, and emergence of collective action and cultural fads in human societies. It is defined on an (arbitrary) network of interacting agents whose state is determined by the state of their neighbors according to a threshold rule. In a typical setting, bootstrap per...

Bootstrap percolation is a cellular automaton modelling the spread of an `infection' on a graph. In this note, we prove a family of lower bounds on the critical probability for $r$-neighbour bootstrap percolation on Galton--Watson trees in terms of moments of the offspring distributions. With this result we confirm a conjecture of Bollob\'as, Gunderson, Holmgren, Janson and Przykucki. We also show that these bounds are best possible up to positive constants not depending on t...

Majority bootstrap percolation is a monotone cellular automata that can be thought of as a model of infection spreading in networks. Starting with an initially infected set, new vertices become infected once more than half of their neighbours are infected. The average case behaviour of this process was studied on the $n$-dimensional hypercube by Balogh, Bollob\'{a}s and Morris, who showed that there is a phase transition as the typical density of the initially infected set in...

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