2021/08/13 by Jason Bello, Bello, Jason, David Sivakoff +1
Computer Science · Mathematics · Physics and Astronomy · #60K35 (Primary) 05D99 (Secondary) #Cellular Automata and Applications #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #Stochastic processes and statistical mechanics #Theoretical and Computational Physics #math.CO #math.PR #msc:05D99 #msc:60K35
paper · pdf · doi:10.48550/arxiv.2108.06404
22 pages, 2 figures
arxiv created 2021/08/13 · openalex publication_date 2021/08/13 · arxiv updated 2021/08/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the cyclic cellular automaton (CCA) and the Greenberg-Hastings model (GHM) with κ≥ 3 colors and contact threshold θ≥ 2 on the infinite (d+1)-regular tree, Td. When the initial state has the uniform product distribution, we show that these dynamical systems exhibit at least two distinct phases. For sufficiently large d, we show that if κ(θ-1) ≤ d - O(√(dκln(d))), then every vertex almost surely changes its color infinitely often, while if κθ≥ d + O(κ√(dln(d))), then every vertex almost surely changes its color only finitely many times. Roughly, this implies that as d→ ∞, there is a phase transition where κθ/d = 1. For the GHM dynamics, in the scenario where every vertex changes color finitely many times, we moreover give an exponential tail bound for the distribution of the time of the last color change at a given vertex.