Doctor of Philosophy, The Ohio State University, 2021, Mathematics
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 Greenb (open full item for complete abstract)
Committee: David Sivakoff (Advisor); Matthew Kahle (Committee Member); Hoi Nguyen (Committee Member)
Subjects: Mathematics