Title: Discrete excitable media on graphs
Speaker: Hanbaek Lyu (The Ohio State University)
Abstract: An excitable medium is a nonlinear dynamical system over a network which has the capacity to propagate a wave of fluctuations, examples of which in nature include neural networks, chemical reactions, and coupled oscillators. Spontaneous generation of such waves often leads to surprising self-organizations in the system. We study three discrete models of excitable media in probabilistic aspects, emphasizing their common nature as well as interesting discrepancies. Greenberg-Hastings Model (GHM) and Cyclic cellular automaton (CCA) are two particular discrete excitable media which have been studied extensively from 90s. Recently, we proposed a discrete model for coupled oscillators which we call the firefly cellular automaton (FCA), and studied its limiting behavior on finite trees.
A classic technique for studying GHM and CCA on the one dimensional lattice is to relate the limiting behavior with random walks with i.i.d. increments by considering their embedded particle system structure. An extra complication arises for FCA, since the associated random walk has long-range correlation. We handle this complication through a combination of Markov chain and generating function methods and show that all sites gets fluctuated less and less frequently, as known for GHM and CCA. However, this particle system method does not easily carry over to general network topology. To overcome this limitation, we develop a new technique to construct a monotone comparison process in the universal covering space of the underlying graph. Roughly speaking, it is to compare original model with an easier meta-model but constructed on larger graph. This enables us to characterize limiting behavior of 3-color GHM and CCA on arbitrary graphs, including the Erdos-Renyi random graphs. On infinite rooted trees, our method in particular relates the average rate of fluctuation of the root to a certain notion of speed of a tree-indexed random walk. Due to a large-deviations effect, all sites get fluctuated at a linear average rate.
In two or more dimensions, both CCA and GHM show spontaneous emergence of spiral waves by which all sites fluctuates periodically, for any available number of colors for each site. This behavior is shared in FCA for all but one case: the 4-color FCA shows mysterious clustering behavior in all higher dimensions. Time permitted, we remark on an application of a continuous generalization of the 4-color FCA to distributed clock synchronization algorithms.
Seminar URL: http://mgsa.org.ohio-state.edu/home.html