Monotone cellular automata in a random environment

DOI10.1017/S0963548315000012MaRDI QIDQ5364252zbMATH OpenOpenAlexFDO

Authors Béla Bollobás, Paul Smith, Andrew J. Uzzell

Publication date 4 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.3980

Dynamical aspects of cellular automata (37B15) Combinatorial probability (60C05) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Processes in random environments (60K37)

Abstract: In this paper we study in complete generality the family of two-state, deterministic, monotone, local, homogeneous cellular automata in

m a t h b b Z^{d}

with random initial configurations. Formally, we are given a set

m a t h c a l U = X_{1}, d o t s, X_{m}

of finite subsets of

m a t h b b Z^{d} s e t m i n u s m a t h b f 0

, and an initial set

A_{0} s u b s e t m a t h b b Z^{d}

of `infected' sites, which we take to be random according to the product measure with density

p

. At time

t i n m a t h b b N

, the set of infected sites

A_{t}

is the union of

A_{t - 1}

and the set of all

x i n m a t h b b Z^{d}

such that

x + X i n A_{t - 1}

for some

X i n m a t h c a l U

. Our model may alternatively be thought of as bootstrap percolation on

m a t h b b Z^{d}

with arbitrary update rules, and for this reason we call it

m a t h c a l U

-bootstrap percolation. In two dimensions, we give a classification of

m a t h c a l 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

(m a t h b b Z / n m a t h b b Z)^{2}

is

(l o g n)^{- T h e t a (1)}

for all models in the critical class, and that it is

n^{- T h e t a (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

m a t h b b Z^{d}

.

Recommendations

Cites work

Cited in

(51)

This page was built for publication: Monotone cellular automata in a random environment

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5364252)