We study the end behavior of three different discrete-time processes on a variety of graphs. The first is the cyclic particle system (CPS) on 3 colors with discordant voting, (Xt). Given a connected finite graph G = (V, E), start by randomly coloring each vertex with any of the 3 colors, labeled 0, 1, or 2. At every time-step, the color X(v) at vertex v randomly chooses an adjacent vertex u with the property X(v)−X(u) = 1 mod 3 and paints u with its color. This Markovian process is using the push update rule. In addition to push updates, we also consider pull updates in which v randomly chooses an adjacent vertex u with the property X(u) − X(v) = 1 mod 3 and paints itself with the color of v. In this way, v pulls the color of its discordant neighbor. Since G is a connected, finite graph and all colors interact, eventually there will be a consensus in color among all the vertices. Hence, we study the time until consensus with respect to n = |V | for the star graph and the complete graph.
The second process we analyzed is the cyclic cellular automaton (CCA) on κ colors with threshold θ, (ξt). We study this on the infinite, (d + 1)-regular tree, Td, and on the random Galton-Watson tree with offspring distribution ζ, Tζ. So for a given tree, T, (ξt) is defined on the state space {0, 1, 2, . . . , κ − 1}T . Given a uniformly distributed random initial configuration, at each time-step t every vertex considers its neighbors. If v ∈ T has at least θ neighbors u, such that ξt(u)=ξt(v)+1 mod κ, then ξt+1(v)=ξt(v)+1 modκ. Otherwise, ξt+1(v) = ξt(v) mod κ. On Td, with these deterministic dynamics, we present sufficient conditions on κ and θ so that, for sufficiently large d, (ξt) either fixates or fluctuates almost surely i.e. all vertices in Td eventually do not change state or there exist vertices that will always change state. Furthermore on Tζ, we present sufficient conditions so that (ξt) fixates or fluctuates almost surely.
The last process we studied was the Greenberg-Hastings Model (GHM), (γt), on Td and Tζ. GHM defined on state space {0,1,2,...,κ−1}T for some tree T, on κ colors with threshold θ is a different cellular automaton intended to model excitable media. Thus, states {0}, {1} and {2, . . . , κ − 1} are respectively called resting, excited, and refractory states. Unlike CCA, if v ∈ T has γt(v) ≥ 1 mod κ then γt+1(v) = γt(v) + 1 mod κ regardless of threshold, but if γt(v) = 0 mod κ then γt+1(v) = γt(v)+1 mod κ if v has at least θ neighbors u, such that γt(u)=γt(v)+1 mod κ; otherwise,γt+1(v)=γt(v) mod κ. For this process, we find sufficient conditions for which GHM survives or dies out almost surely i.e. there exists a vertex that changes state infinitely often or all vertices are eventually color 0. Because of the similarities to CCA, we can replicate the threshold between survival and extinction for GHM on Td as we did with fluctuation and fixation for CCA. More interestingly on Tζ, we are able to relax some of the conditions on κ, θ, and ζ so that (γt) dies out almost surely.