{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T19:15:55Z","timestamp":1775848555611,"version":"3.50.1"},"reference-count":22,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2015,2,2]],"date-time":"2015-02-02T00:00:00Z","timestamp":1422835200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2015,7]]},"abstract":"<jats:p>In this paper we study in complete generality the family of two-state, deterministic, monotone, local, homogeneous cellular automata in <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548315000012_inline1\"\/><jats:tex-math>$\\mathbb{Z}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula><jats:sup><jats:italic>d<\/jats:italic><\/jats:sup> with random initial configurations. Formally, we are given a set <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548315000012_inline2\"\/><jats:tex-math>$\\mathcal{U}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> = {<jats:italic>X<\/jats:italic><jats:sub>1<\/jats:sub>,.\u00a0.\u00a0.\u00a0, <jats:italic>X<jats:sub>m<\/jats:sub><\/jats:italic>} of finite subsets of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548315000012_inline1\"\/><jats:tex-math>$\\mathbb{Z}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula><jats:sup><jats:italic>d<\/jats:italic><\/jats:sup> \\ {<jats:bold>0<\/jats:bold>}, and an initial set <jats:italic>A<\/jats:italic><jats:sub>0<\/jats:sub> \u2282 <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548315000012_inline1\"\/><jats:tex-math>$\\mathbb{Z}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula><jats:sup><jats:italic>d<\/jats:italic><\/jats:sup> of \u2018infected\u2019 sites, which we take to be random according to the product measure with density <jats:italic>p<\/jats:italic>. At time <jats:italic>t<\/jats:italic> \u2208 <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548315000012_inline3\"\/><jats:tex-math>$\\mathbb{N}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, the set of infected sites <jats:italic>A<jats:sub>t<\/jats:sub><\/jats:italic> is the union of <jats:italic>A<\/jats:italic><jats:sub><jats:italic>t<\/jats:italic>-1<\/jats:sub> and the set of all <jats:italic>x<\/jats:italic> \u2208 <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548315000012_inline1\"\/><jats:tex-math>$\\mathbb{Z}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula><jats:sup><jats:italic>d<\/jats:italic><\/jats:sup> such that <jats:italic>x<\/jats:italic> + <jats:italic>X<\/jats:italic> \u2208 <jats:italic>A<\/jats:italic><jats:sub><jats:italic>t<\/jats:italic>-1<\/jats:sub> for some <jats:italic>X<\/jats:italic> \u2208 <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548315000012_inline2\"\/><jats:tex-math>$\\mathcal{U}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Our model may alternatively be thought of as bootstrap percolation on <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548315000012_inline1\"\/><jats:tex-math>$\\mathbb{Z}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula><jats:sup><jats:italic>d<\/jats:italic><\/jats:sup> with arbitrary update rules, and for this reason we call it <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548315000012_inline2\"\/><jats:tex-math>$\\mathcal{U}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula><jats:italic>-bootstrap percolation<\/jats:italic>.<\/jats:p><jats:p>In two dimensions, we give a classification of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548315000012_inline2\"\/><jats:tex-math>$\\mathcal{U}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-bootstrap percolation models into three classes \u2013 supercritical, critical and subcritical \u2013 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 (<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548315000012_inline1\"\/><jats:tex-math>$\\mathbb{Z}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>\/<jats:italic>n<\/jats:italic><jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548315000012_inline1\"\/><jats:tex-math>$\\mathbb{Z}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>)<jats:sup>2<\/jats:sup> is (log n)<jats:sup>\u2212\u0398(1)<\/jats:sup> for all models in the critical class, and that it is <jats:italic>n<\/jats:italic><jats:sup>\u2212\u0398(1)<\/jats:sup> for all models in the supercritical class.<\/jats:p><jats: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 <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548315000012_inline1\"\/><jats:tex-math>$\\mathbb{Z}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula><jats:sup><jats:italic>d<\/jats:italic><\/jats:sup>.<\/jats:p>","DOI":"10.1017\/s0963548315000012","type":"journal-article","created":{"date-parts":[[2015,2,1]],"date-time":"2015-02-01T23:27:46Z","timestamp":1422833266000},"page":"687-722","source":"Crossref","is-referenced-by-count":41,"title":["Monotone Cellular Automata in a Random Environment"],"prefix":"10.1017","volume":"24","author":[{"given":"B\u00c9LA","family":"BOLLOB\u00c1S","sequence":"first","affiliation":[]},{"given":"PAUL","family":"SMITH","sequence":"additional","affiliation":[]},{"given":"ANDREW","family":"UZZELL","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2015,2,2]]},"reference":[{"key":"S0963548315000012_ref22","volume-title":"Theory of Self-Reproducing Automata","author":"von Neumann","year":"1966"},{"key":"S0963548315000012_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/BF01019705"},{"key":"S0963548315000012_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/0378-4371(90)90280-6"},{"key":"S0963548315000012_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4149(94)00061-W"},{"key":"S0963548315000012_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/0378-4371(89)90033-2"},{"key":"S0963548315000012_ref11","doi-asserted-by":"publisher","DOI":"10.1088\/0022-3719\/12\/1\/008"},{"key":"S0963548315000012_ref6","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548308009322"},{"key":"S0963548315000012_ref7","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007619"},{"key":"S0963548315000012_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-005-0451-6"},{"key":"S0963548315000012_ref2","unstructured":"Balister P. , Bollob\u00e1s B. , Przykucki M. J. and Smith P. J. Subcritical $\\mathcal{U}$ -bootstrap percolation models have non-trivial phase transitions. Trans. Amer. Math. Soc. In press. arXiv:1311.5883"},{"key":"S0963548315000012_ref1","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470\/21\/19\/017"},{"key":"S0963548315000012_ref13","doi-asserted-by":"crossref","first-page":"1752","DOI":"10.1214\/aop\/1041903205","article-title":"First passage time for threshold growth dynamics on $\\mathbb{Z}$2","volume":"24","author":"Gravner","year":"1996","journal-title":"Ann. Probab."},{"key":"S0963548315000012_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-4149(02)00124-2"},{"key":"S0963548315000012_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-002-0239-x"},{"key":"S0963548315000012_ref4","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2011-05552-2"},{"key":"S0963548315000012_ref19","unstructured":"Ulam S. (1950) Random processes and transformations. In Proc. Internat. Congr. Math., pp. 264\u2013275."},{"key":"S0963548315000012_ref9","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1022874817"},{"key":"S0963548315000012_ref21","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-007-9377-y"},{"key":"S0963548315000012_ref18","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176989923"},{"key":"S0963548315000012_ref5","doi-asserted-by":"publisher","DOI":"10.1214\/08-AOP433"},{"key":"S0963548315000012_ref14","unstructured":"Gravner J. and Griffeath D. (1999) Scaling laws for a class of critical cellular automaton growth rules. In Proc. Erd\u0151s Center Workshop on Random Walks, pp. 167\u2013188."},{"key":"S0963548315000012_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-009-9798-x"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548315000012","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,20]],"date-time":"2019-04-20T18:51:41Z","timestamp":1555786301000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548315000012\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,2,2]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,7]]}},"alternative-id":["S0963548315000012"],"URL":"https:\/\/doi.org\/10.1017\/s0963548315000012","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,2,2]]}}}