Monotone Cellular Automata in a Random Environment. (July 2015)

• Record Type: Journal Article
• Authors: BOLLOBÁS, BÉLA; SMITH, PAUL; UZZELL, ANDREW
• Is Part Of: Combinatorics, probability and computing. Volume 24:Number 4(2015:Jul.)
• Page Start: 687
• Page End: 722
• Publication Date: 2015-07
• Subjects: Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548315000012
• Languages: English
• ISSNs: 0963-5483

Abstract

<abstract abstract-type="normal"> <title> <x content-type="archive" xml:space="preserve">Abstract</x> </title> <p>In this paper we study in complete generality the family of two-state, deterministic, monotone, local, homogeneous cellular automata in <inline-formula><alternatives><inline-graphic xlink:href="ark:/27927/pgjqhxb4hw" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><tex-math><![CDATA[$\mathbb{Z}$]]></tex-math></alternatives></inline-formula><sup><italic>d</italic></sup> with random initial configurations. Formally, we are given a set <inline-formula><alternatives><inline-graphic xlink:href="ark:/27927/pgjqhxb4db" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><tex-math><![CDATA[$\mathcal{U}$]]></tex-math></alternatives></inline-formula> = {<italic>X</italic><sub>1</sub>, . . . , <italic>X<sub>m</sub></italic>} of finite subsets of <inline-formula><alternatives><inline-graphic xlink:href="ark:/27927/pgjqhxb4hw" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><tex-math><![CDATA[$\mathbb{Z}$]]></tex-math></alternatives></inline-formula><sup><italic>d</italic></sup> \ {<bold>0</bold>}, and an initial set <italic>A</italic><sub>0</sub> ⊂ <inline-formula><alternatives><inline-graphic xlink:href="ark:/27927/pgjqhxb4hw" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><tex-math><![CDATA[$\mathbb{Z}$]]></tex-math></alternatives></inline-formula><sup><italic>d</italic></sup> of 'infected' sites, which we take to be random according to the product measure with density <italic>p</italic>. At time <italic>t</italic> ∈ <inline-formula><alternatives><inline-graphic xlink:href="ark:/27927/pgjqhxb4jd" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><tex-math><![CDATA[$\mathbb{N}$]]></tex-math></alternatives></inline-formula>, the set of infected sites <italic>A<sub>t</sub></italic> is the union of <italic>A</italic><sub><italic>t</italic>-1</sub> and the set of all <italic>x</italic> ∈ <inline-formula><alternatives><inline-graphic xlink:href="ark:/27927/pgjqhxb4hw" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><tex-math><![CDATA[$\mathbb{Z}$]]></tex-math></alternatives></inline-formula><sup><italic>d</italic></sup> such that <italic>x</italic> + <italic>X</italic> ∈ <italic>A</italic><sub><italic>t</italic>-1</sub> for some <italic>X</italic> ∈ <inline-formula><alternatives><inline-graphic xlink:href="ark:/27927/pgjqhxb4db" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><tex-math><![CDATA[$\mathcal{U}$]]></tex-math></alternatives></inline-formula>. Our model may alternatively be thought of as bootstrap percolation on <inline-formula><alternatives><inline-graphic xlink:href="ark:/27927/pgjqhxb4hw" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><tex-math><![CDATA[$\mathbb{Z}$]]></tex-math></alternatives></inline-formula><sup><italic>d</italic></sup> with arbitrary update rules, and for this reason we call it <inline-formula><alternatives><inline-graphic xlink:href="ark:/27927/pgjqhxb4db" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><tex-math><![CDATA[$\mathcal{U}$]]></tex-math></alternatives></inline-formula><italic>-bootstrap percolation</italic>.</p> <p>In two dimensions, we give a classification of <inline-formula><alternatives><inline-graphic xlink:href="ark:/27927/pgjqhxb4db" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><tex-math><![CDATA[$\mathcal{U}$]]></tex-math></alternatives></inline-formula>-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 (<inline-formula><alternatives><inline-graphic xlink:href="ark:/27927/pgjqhxb4hw" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><tex-math><![CDATA[$\mathbb{Z}$]]></tex-math></alternatives></inline-formula>/<italic>n</italic><inline-formula><alternatives><inline-graphic xlink:href="ark:/27927/pgjqhxb4hw" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><tex-math><![CDATA[$\mathbb{Z}$]]></tex-math></alternatives></inline-formula>)<sup>2</sup> is (log n)<sup>−Θ(1)</sup> for all models in the critical class, and that it is <italic>n</italic><sup>−Θ(1)</sup> for all models in the supercritical class.</p> <p>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 <inline-formula><alternatives><inline-graphic xlink:href="ark:/27927/pgjqhxb4hw" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><tex-math><![CDATA[$\mathbb{Z}$]]></tex-math></alternatives></inline-formula><sup><italic>d</italic></sup>.</p> </abstract>