|Dept.||The Ohio State Univ.|
We propose a novel generalized cellular automaton(GCA) model for discrete-time pulse-coupled oscillators and study the emergence of synchrony. Given a finite simple graph and an integer n≥3, each vertex is an identical oscillator of period n with the following weak coupling along the edges: each oscillator inhibits its phase update if it has at least one neighboring oscillator at a particular "blinking" state and if its state is ahead of this blinking state. We obtain conditions on initial configurations and on network topologies for which states of all vertices eventually synchronize. We show that our GCA model synchronizes arbitrary initial configurations on paths, trees, and with random perturbation, any connected graph. In particular, our main result is the following local-global principle for tree networks: for n∈3456, any n-periodic network on a tree synchronizes arbitrary initial configuration if and only if the maximum degree of the tree is less than the period n.
Moreover, we will talk about more recent results on n-color model on Z in relation to cyclic cellular automata and random walk, and "4-color theorem" on d-dimensional grids for d≥2.