2022/11/04 by Béla Bollobás, Hugo Duminil‐Copin, Robert Morris +1 · 1 citation
Computer Science · Mathematics · #Cellular Automata and Applications #Stochastic processes and statistical mechanics #Markov Chains and Monte Carlo Methods
paper · doi:10.1112/plms.12497
We study the class of monotone, two-state, deterministic cellular automata, in which sites are activated (or ‘infected') by certain configurations of nearby infected sites. These models have close connections to statistical physics, and several specific examples have been extensively studied in recent years by both mathematicians and physicists. This general setting was first studied only recently, however, by Bollobás, Smith and Uzzell, who showed that the family of all such ‘bootstrap percolation’ models on Z 2 \mathbb Z2 can be naturally partitioned into three classes, which they termed subcritical, critical and supercritical. In this paper we determine the order of the threshold for percolation (complete occupation) for every critical bootstrap percolation model in two dimensions. This ‘universality’ theorem includes as special cases results of Aizenman and Lebowitz, Gravner and Griffeath, Mountford and van Enter and Hulshof; significantly strengthens bounds of Bollobás, Smith and Uzzell; and complements recent work of Balister, Bollobás, Przykucki and Smith on subcritical models.