$\mathcal{U}$-bootstrap percolation: critical probability, exponential decay and applications

Kinetically constrained models (KCM) are reversible interacting particle systems on $\mathbb{Z}^d$ with continuous-time constrained Glauber dynamics. They are a natural non-monotone stochastic version of the family of cellular automata with random initial state known as $\mathcal{U}$-bootstrap percolation. KCM have an interest in their own right, owing to their use for modelling the liquid-glass transition in condensed matter physics. In two dimensions there are three class...

In this paper we consider kinetically constrained models (KCM) on $\mathbb Z^2$ with general update families $\mathcal U$. For $\mathcal U$ belonging to the so-called "critical class" our focus is on the divergence of the infection time of the origin for the equilibrium process as the density of the facilitating sites vanishes. In a recent paper Mar\^ech\'e and two of the present authors proved that if $\mathcal U$ has an infinite number of "stable directions", then on a doub...

In modified two-neighbour bootstrap percolation in two dimensions each site of $\mathbb Z^2$ is initially independently infected with probability $p$ and on each discrete time step one additionally infects sites with at least two non-opposite infected neighbours. In this note we establish that for this model the second term in the asymptotics of the infection time $\tau$ unexpectedly scales differently from the classical two-neighbour model, in which arbitrary two infected ne...

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

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

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 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 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 type of cellular automaton on graphs, introduced as a simple model of the dynamics of ferromagnetism. Vertices in a graph can be in one of two states: `healthy' or `infected' and from an initial configuration of states, healthy vertices become infected by local rules. While the usual bootstrap processes are monotone in the sets of infected vertices, in this paper, a modification is examined in which infected vertices can return to a healthy state. V...

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