ID: 1806.11405

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

June 29, 2018

View on ArXiv
Ivailo Hartarsky
Mathematics
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 and successfully apply this link to prove new and old results for concrete models such as DTBP and Spiral as well as a general non-trivial upper bound. Our approach establishes and exploits a tight connection between subcritical bootstrap percolation and a suitable generalisation of classical oriented percolation, which will undoubtedly be the source of more results and could provide an entry point for general percolationists to bootstrap percolation. Furthermore, we prove that above a certain critical probability there is exponential decay of the probability of a one-arm event, while below it the event has positive probability and the expected infection time is infinite. We also identify this as the transition of the spectral gap and mean infection time of the corresponding kinetically constrained model. Finally, we essentially characterise the noise sensitivity properties at fixed density for the two natural one-arm events. In doing so we answer fully or partially most of the open questions asked by Balister, Bollob\'as, Przykucki and Smith (2016)---namely we are concerned with their Questions 11, 12, 13, 14 and 17.

Similar papers 1

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

Monotone cellular automata in a random environment

April 18, 2012

90% 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

Subcritical monotone cellular automata

March 3, 2022

88% Match
Paul Balister, Béla Bollobás, ... , Smith Paul
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.

Find SimilarView on arXiv

Universality for two-dimensional critical cellular automata

June 25, 2014

88% 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

Refined universality for critical KCM: lower bounds

November 13, 2020

88% Match
Ivailo Hartarsky, Laure Marêché
Probability
Statistical Mechanics
Combinatorics

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

Find SimilarView on arXiv

Refined universality for critical KCM: upper bounds

April 6, 2021

88% Match
Ivailo Hartarsky
Probability
Statistical Mechanics
Mathematical Physics

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

Find SimilarView on arXiv

Universality for monotone cellular automata

March 25, 2022

87% 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

Spiral Model: a cellular automaton with a discontinuous glass transition

September 4, 2007

87% Match
Cristina Toninelli, Giulio Biroli
Statistical Mechanics
Probability

We introduce a new class of two-dimensional cellular automata with a bootstrap percolation-like dynamics. Each site can be either empty or occupied by a single particle and the dynamics follows a deterministic updating rule at discrete times which allows only emptying sites. We prove that the threshold density $\rho_c$ for convergence to a completely empty configuration is non trivial, $0<\rho_c<1$, contrary to standard bootstrap percolation. Furthermore we prove that in the ...

Find SimilarView on arXiv

Scaling Limit and Critical Exponents for Two-Dimensional Bootstrap Percolation

October 21, 2004

87% Match
Federico Camia
Probability
Statistical Mechanics
Mathematical Physics

Consider a cellular automaton with state space $\{0,1 \}^{{\mathbb Z}^2}$ where the initial configuration $\omega_0$ is chosen according to a Bernoulli product measure, 1's are stable, and 0's become 1's if they are surrounded by at least three neighboring 1's. In this paper we show that the configuration $\omega_n$ at time n converges exponentially fast to a final configuration $\bar\omega$, and that the limiting measure corresponding to $\bar\omega$ is in the universality c...

Find SimilarView on arXiv

Complexity of 2D bootstrap percolation difficulty: Algorithm and NP-hardness

September 5, 2018

86% Match
Ivailo Hartarsky, Tamás Róbert Mezei
Combinatorics
Computational Complexity
Discrete Mathematics

Bootstrap percolation is a class of cellular automata with random initial state. Two-dimensional bootstrap percolation models have three rough universality classes, the most studied being the `critical' one. For this class the scaling of the quantity of greatest interest -- the critical probability -- was determined by Bollob\'as, Duminil-Copin, Morris and Smith in terms of a simply defined combinatorial quantity called `difficulty', so the subject seemed closed up to finding...

Find SimilarView on arXiv