Monotone cellular automata in a random environment

Abstract

In this paper we study in complete generality the family of two-state, deterministic, monotone, local, homogeneous cellular automata in ${\mathbb{Z}}^d$ with random initial configurations. Formally, we are given a set $\mathcal{U}=\{X_1,\dots ,X_m\}$ of finite subsets of ${\mathbb{Z}}^d\setminus \{0\}$, and an initial set $A_0\subset {\mathbb{Z}}^d$ of `infected' sites, which we take to be random according to the product measure with density $p$. At time $t\in \mathbb{N}$, the set of infected sites $A_t$ is the union of $A_{t-1}$ and the set of all $x\in {\mathbb{Z}}^d$ such that $x+X\in A_{t-1}$ for some $X\in \mathcal{U}$. Our model may alternatively be thought of as bootstrap percolation on ${\mathbb{Z}}^d$ with arbitrary update rules, and for this reason we call it $\mathcal{U}$-bootstrap percolation. In two dimensions, we give a classification of $\mathcal{U}$-bootstrap percolation models into three classes -- supercritical, critical and subcritical -- and we prove results about the phase transitions of all models belonging to the first two of these classes. More precisely, we show that the critical probability for percolation on $(\mathbb{Z}/n\mathbb{Z}{)}^2$ is $(\log n{)}^{-\Theta (1)}$ for all models in the critical class, and that it is $n^{-\Theta (1)}$ for all models in the supercritical class. The results in this paper are the first of any kind on bootstrap percolation considered in this level of generality, and in particular they are the first that make no assumptions of symmetry. It is the hope of the authors that this work will initiate a new, unified theory of bootstrap percolation on ${\mathbb{Z}}^d$.

33 pages, 7 figures

References in corpus (4)

• Bootstrap percolation in three dimensions
• Finite-size effects for anisotropic bootstrap percolation: logarithmic corrections
• Metastable behavior for bootstrap percolation on regular trees
• Subcritical $\mathcal{U}$-bootstrap percolation models have non-trivial phase transitions

Cited by in corpus (24)

• Universality results for kinetically constrained spin models in two dimensions
• The second term for two-neighbour bootstrap percolation in two dimensions
• Refined universality for critical KCM: lower bounds
• Sharp threshold for the FA-2f kinetically constrained model
• A trust model for spreading gossip in social networks
• $\mathcal{U}$-bootstrap percolation: critical probability, exponential decay and applications
• Bootstrap percolation, probabilistic cellular automata and sharpness
• Kinetically Constrained Models with Random Constraints
• Refined universality for critical KCM: upper bounds
• Combinatorics for general kinetically constrained spin models
• Complexity of 2D bootstrap percolation difficulty: Algorithm and NP-hardness
• An Improved Upper Bound for Bootstrap Percolation in All Dimensions
• On the Running Time of Hypergraph Bootstrap Percolation
• The time of bootstrap percolation in two dimensions
• Sharp metastability transition for two-dimensional bootstrap percolation with symmetric isotropic threshold rules
• Maximal Bootstrap Percolation Time on the Hypercube via Generalised Snake-in-the-Box
• Fixation for Two-Dimensional $\mathcal{U}$-ISING and $\mathcal{U}$-VOTER Dynamics
• Exponential convergence to equilibrium in supercritical kinetically constrained models at high temperature
• Fixation for $\mathcal{U}$-Ising and $\mathcal{U}$-voter dynamics with frozen vertices
• Triangle Percolation on the Grid
• Cold Dynamics in Cellular Automata: a Tutorial
• Subcritical bootstrap percolation via Toom contours
• Bounds on Minimum Number of Anchors for Iterative Localization and its Connections to Bootstrap Percolation
• A Note on Bootstrap Percolation Thresholds in Plane Tilings using Regular Polygons