Limiting behavior of 3-color excitable media on arbitrary graphs. (English) Zbl 1404.60151

Summary: Fix a simple graph \(G=(V,E)\) and choose a random initial 3-coloring of vertices drawn from a uniform product measure. The 3-color cycle cellular automaton is a process in which at each discrete time step in parallel, every vertex with color \(i\) advances to the successor color \((i+1)\mod 3\) if in contact with a neighbor with the successor color, and otherwise retains the same color. In the Greenberg-Hastings model, the same update rule applies only to color 0, while other two colors automatically advance. The limiting behavior of these processes has been studied mainly on the integer lattices. In this paper, we introduce a monotone comparison process defined on the universal covering space of the underlying graph, and characterize the limiting behavior of these processes on arbitrary connected graphs. In particular, we establish a phase transition on the Erdős-Rényi random graph. On infinite trees, we connect the rate of color change to the cloud speed of an associated tree-indexed walk. We give estimates of the cloud speed by generalizing known results to trees with leaves.


60K35 Interacting random processes; statistical mechanics type models; percolation theory
82B43 Percolation
Full Text: DOI arXiv Euclid


[1] Arnol’d, V. I. (2013). Mathematical Methods of Classical Mechanics. Graduate Texts in Mathematics60. Springer, New York.
[2] Belitsky, V. and Ferrari, P. A. (1995). Ballistic annihilation and deterministic surface growth. J. Stat. Phys.80 517–543. · Zbl 1081.60553
[3] Benjamini, I. and Peres, Y. (1994). Tree-indexed random walks on groups and first passage percolation. Probab. Theory Related Fields98 91–112. · Zbl 0794.60068
[4] Bollobás, B. (1998). Random graphs. In Modern Graph Theory 215–252. Springer, Berlin.
[5] Bramson, M. and Griffeath, D. (1989). Flux and fixation in cyclic particle systems. Ann. Probab.17 26–45. · Zbl 0673.60103
[6] Datta, A. K., Petit, F. and Guerraoui, R. (2016). Toward a time-optimal odd phase clock unison in trees. In Stabilization, Safety, and Security of Distributed Systems 137–151. Springer, Cham.
[7] Dembo, A. and Zeitouni, O. (2009). Large Deviations Techniques and Applications. Applications of Mathematics (New York) 38. Springer, New York. · Zbl 0793.60030
[8] Deuschel, J.-D. and Stroock, D. W. (1989). Large Deviations. Pure and Applied Mathematics137. Academic Press, Boston, MA. · Zbl 0705.60029
[9] Dolev, S. (2000). Self-Stabilization. MIT Press, Cambridge, MA. · Zbl 1026.93001
[10] Durrett, R. and Steif, J. E. (1991). Some rigorous results for the Greenberg-Hastings model. J. Theoret. Probab.4 669–690. · Zbl 0741.92001
[11] Fisch, R. (1990). The one-dimensional cyclic cellular automaton: A system with deterministic dynamics that emulates an interacting particle system with stochastic dynamics. J. Theoret. Probab.3 311–338. · Zbl 0701.60105
[12] Fisch, R. (1992). Clustering in the one-dimensional three-color cyclic cellular automaton. Ann. Probab.20 1528–1548. · Zbl 0806.60096
[13] Fisch, R. and Gravner, J. (1995). One-dimensional deterministic Greenberg-Hastings models. Complex Systems9 329–348. · Zbl 0867.68120
[14] Fisch, R., Gravner, J. and Griffeath, D. (1991). Cyclic cellular automata in two dimensions. In Spatial Stochastic Processes. Progress in Probability19 171–185. Birkhäuser, Boston, MA. · Zbl 0737.60088
[15] Fisch, R., Gravner, J. and Griffeath, D. (1991). Threshold-range scaling of excitable cellular automata. Stat. Comput.1 23–39. · Zbl 0737.60088
[16] Greenberg, J. M. and Hastings, S. P. (1978). Spatial patterns for discrete models of diffusion in excitable media. SIAM J. Appl. Math.34 515–523. · Zbl 0398.92004
[17] Herman, T. and Ghosh, S. (1995). Stabilizing phase-clocks. Inform. Process. Lett.54 259–265. · Zbl 0875.68040
[18] Janson, S., Łuczak, T. and Rucinski, A. (2011). Random Graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization45. Wiley-Interscience, New York. · Zbl 0968.05003
[19] Lamport, L. (1978). Time, clocks, and the ordering of events in a distributed system. Commun. ACM21 558–565. · Zbl 0378.68027
[20] Lyons, R. (1989). The Ising model and percolation on trees and tree-like graphs. Comm. Math. Phys.125 337–353. · Zbl 0679.60101
[21] Lyons, R. (1990). Random walks and percolation on trees. Ann. Probab.18 931–958. · Zbl 0714.60089
[22] Lyu, H. (2015). Synchronization of finite-state pulse-coupled oscillators. Phys. D303 28–38. · Zbl 1364.37037
[23] O’Connell, N. (1998). Some large deviation results for sparse random graphs. Probab. Theory Related Fields110 277–285.
[24] Pittel, B. (1988). A random graph with a subcritical number of edges. Trans. Amer. Math. Soc.309 51–75. · Zbl 0658.05062
[25] Spencer, J. (1993). Nine lectures on random graphs. In École D’Été de Probabilités de Saint-Flour XXI—1991. Lecture Notes in Math.1541 293–347. Springer, Berlin.
[26] Varadhan, S. R. S. (2008). Large deviations. Ann. Probab.36 397–419. · Zbl 1146.60003
[27] Wiener, N. and Rosenblueth, A. (1946). The mathematical formulation of the problem of conduction of impulses in a network of connected excitable elements, specifically in cardiac muscle. Arch. Inst. Cardiol. Méx.16 205–265. · Zbl 0134.37904
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.