Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Discrete threshold growth dynamics
are omnivorous for box neighborhoods

Author: Tom Bohman
Journal: Trans. Amer. Math. Soc. 351 (1999), 947-983
MSC (1991): Primary 60K35; Secondary 05D99
MathSciNet review: 1443863
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In the discrete threshold model for crystal growth in the plane we begin with some set $A_{0} \subset {\mathbf Z}^{2}$ of seed crystals and observe crystal growth over time by generating a sequence of subsets $ A_{0} \subset A_{1} \subset A_{2} \subset \dotsb $ of ${\mathbf Z}^{2}$ by a deterministic rule. This rule is as follows: a site crystallizes when a threshold number of crystallized points appear in the site's prescribed neighborhood. The growth dynamics generated by this model are said to be omnivorous if $A_{0}$ finite and $A_{i+1} \neq A_{i} \; \forall i$ imply $ \bigcup _{i=0}^{\infty} A_{i} = {\mathbf Z}^{2}$. In this paper we prove that the dynamics are omnivorous when the neighborhood is a box (i.e. when, for some fixed $\rho$, the neighborhood of $z$ is $ \{ x \in {\mathbf Z}^{2} : \|x-z\|_{\infty} \le \rho\})$. This result has important implications in the study of the first passage time when $A_{0}$ is chosen randomly with a sparse Bernoulli density and in the study of the limiting shape to which $ n^{-1}A_{n} $ converges.

References [Enhancements On Off] (What's this?)

  • [C] E. Berlekamp, J. Conway, and R. Guy, Winning Ways for Your Mathematical Plays, Academic Press, New York, 1982. MR 84h:90091a
  • [ES] P. Erd\H{o}s and J. Selfridge, On a combinatorial game, J. Comb. Theory A, 14(1973) 298-301. MR 48:5655
  • [GG1] J. Gravner and D. Griffeath, Threshold Growth Dynamics, Transactions of the AMS, 340(1993) 837-869. MR 94b:52006
  • [GG2] J. Gravner and D. Griffeath, First Passage Times for Discrete Threshold Growth Dynamics, Ann. Prob, to appear.

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (1991): 60K35, 05D99

Retrieve articles in all journals with MSC (1991): 60K35, 05D99

Additional Information

Tom Bohman
Affiliation: Department of Mathematics, Rutgers University, New Brunswick, New Jersey 08903
Address at time of publication: Department of Mathematics, 2-339, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Keywords: Threshold growth, cellular automata
Received by editor(s): August 19, 1996
Received by editor(s) in revised form: February 7, 1997
Article copyright: © Copyright 1999 American Mathematical Society