Monotone cellular automata in a random environment

In many interacting particle systems, relaxation to equilibrium is thought to occur via the growth of 'droplets', and it is a question of fundamental importance to determine the critical length at which such droplets appear. In this paper we construct a mechanism for the growth of droplets in an arbitrary finite-range monotone cellular automaton on a $d$-dimensional lattice. Our main application is an upper bound on the critical probability for percolation that is sharp up to...

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

We study a general class of interacting particle systems called kinetically constrained models (KCM) in two dimensions tightly linked to the monotone cellular automata called bootstrap percolation. There are three classes of such models, the most studied being the critical one. In a recent series of works it was shown that the KCM counterparts of critical bootstrap percolation models with the same properties split into two classes with different behaviour. Together with the...

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 connectivity properties of certain i.i.d. random environments on $\Z^d$, where at each location some steps may not be available. Site percolation and oriented percolation can be viewed as special cases of the models we consider. In such models, one of the quantities most often studied is the (random) set of vertices that can be reached from the origin by following a connected path. More generally, for the models we consider, multiple different types of connectivit...

We study a general class of interacting particle systems called kinetically constrained models (KCM) in two dimensions. They are tightly linked to the monotone cellular automata called bootstrap percolation. Among the three classes of such models, the critical ones are the most studied. Together with the companion paper by Mar\^ech\'e and the author, our work determines the logarithm of the infection time up to a constant factor for all critical KCM. This was previously kno...

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

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

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