ID: 2203.01917

Subcritical monotone cellular automata

March 3, 2022

View on ArXiv
Paul Balister, Béla Bollobás, Robert Morris, Paul Smith
Mathematics
Probability
Combinatorics

We study monotone cellular automata (also known as $\mathcal{U}$-bootstrap percolation) in $\mathbb{Z}^d$ with random initial configurations. Confirming a conjecture of Balister, Bollob\'as, Przykucki and Smith, who proved the corresponding result in two dimensions, we show that the critical probability is non-zero for all subcritical models.

Similar papers 1

Universality for monotone cellular automata

March 25, 2022

93% Match
Paul Balister, Béla Bollobás, ... , Smith Paul
Probability
Combinatorics
Mathematical Physics

In this paper we study monotone cellular automata in $d$ dimensions. We develop a general method for bounding the growth of the infected set when the initial configuration is chosen randomly, and then use this method to prove a lower bound on the critical probability for percolation that is sharp up to a constant factor in the exponent for every 'critical' model. This is one of three papers that together confirm the Universality Conjecture of Bollob\'as, Duminil-Copin, Morris...

Find SimilarView on arXiv

Monotone cellular automata in a random environment

April 18, 2012

92% Match
Béla Bollobás, Paul Smith, Andrew Uzzell
Probability
Combinatorics

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\{\mathbf{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...

Find SimilarView on arXiv
Paul Balister, Béla Bollobás, ... , Smith Paul
Probability

We prove that there exist natural generalizations of the classical bootstrap percolation model on $\mathbb{Z}^2$ that have non-trivial critical probabilities, and moreover we characterize all homogeneous, local, monotone models with this property. Van Enter (in the case $d=r=2$) and Schonmann (for all $d \geq r \geq 2$) proved that $r$-neighbour bootstrap percolation models have trivial critical probabilities on $\mathbb{Z}^d$ for every choice of the parameters $d \geq r \g...

The critical length for growing a droplet

March 25, 2022

89% Match
Paul Balister, Béla Bollobás, ... , Smith Paul
Probability
Combinatorics
Mathematical Physics

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

Find SimilarView on arXiv

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

June 29, 2018

88% Match
Ivailo Hartarsky
Probability
Mathematical Physics

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

Find SimilarView on arXiv

Cellular Automata and Bootstrap Percolation

October 1, 2021

87% Match
Ville Salo, Guillaume Theyssier, Ilkka Törmä
Probability
Discrete Mathematics
Dynamical Systems

We study qualitative properties of two-dimensional freezing cellular automata with a binary state set initialized on a random configuration. If the automaton is also monotone, the setting is equivalent to bootstrap percolation. We explore the extent to which monotonicity constrains the possible asymptotic dynamics by proving two results that do not hold in the subclass of monotone automata. First, it is undecidable whether the automaton almost surely fills the space when init...

Find SimilarView on arXiv

Universality for two-dimensional critical cellular automata

June 25, 2014

87% Match
Béla Bollobás, Hugo Duminil-Copin, ... , Smith Paul
Probability
Combinatorics

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\'as, Smith and Uzzell, who showed that the family of all su...

Find SimilarView on arXiv

Critical probabilities and convergence time of Percolation Probabilistic Cellular Automata

December 25, 2013

86% Match
Lorenzo Taggi
Mathematical Physics

This paper considers a class of probabilistic cellular automata undergoing a phase transition with an absorbing state. Denoting by ${\mathcal{U}}(x)$ the neighbourhood of site $x$, the transition probability is $T(\eta_x = 1 | \eta_{{\mathcal{U}}(x)}) = 0$ if $\eta_{{\mathcal{U}}(x)}= \mathbf{0}$ or $p$ otherwise, $\forall x \in \mathbb{Z}$. For any $\mathcal{U}$ there exists a non-trivial critical probability $p_c({\mathcal{U}})$ that separates a phase with an absorbing stat...

Find SimilarView on arXiv

Subcritical bootstrap percolation via Toom contours

March 30, 2022

85% Match
Ivailo Hartarsky, Réka Szabó
Probability
Combinatorics

In this note we provide an alternative proof of the fact that subcritical bootstrap percolation models have a positive critical probability in any dimension. The proof relies on a recent extension of the classical framework of Toom. This approach is not only simpler than the original multi-scale renormalisation proof of the result in two and more dimensions, but also gives significantly better bounds. As a byproduct, we improve the best known bounds for the stability threshol...

Find SimilarView on arXiv

Dynamic critical properties of a one-dimensional probabilistic cellular automaton

December 24, 1997

84% Match
Pratip Bhattacharyya
Statistical Mechanics

Dynamic properties of a one-dimensional probabilistic cellular automaton are studied by monte-carlo simulation near a critical point which marks a second-order phase transition from a active state to a effectively unique absorbing state. Values obtained for the dynamic critical exponents indicate that the transition belongs to the universality class of directed percolation. Finally the model is compared with a previously studied one to show that a difference in the nature of ...

Find SimilarView on arXiv