Combinatorics Seminar - Hanbaek Lyu

September 21, 2015
Thursday, October 1, 2015 - 10:20am to 11:15am
Math Tower 154
math_sculpture

Title: Synchronization of finite-state pulse-coupled oscillators on various network topologies

Speaker: Hanbaek Lyu (OSU)

Abstract: 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\ge 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. For finite graphs, we show that our GCA model synchronizes arbitrary initial configurations on paths, trees, and, with random perturbation, any connected graph. In particular, one main result is the following local-global principle for tree networks: for $n\in \{3,4,5,6\}$, 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$. For infinite graphs, we consider $\mathbb{Z}^{d}$ for $d\ge 1$. For $d=1$, our model is related to annihilating particle systems and random walks, and by this connection, we show that starting with uniform product measure, the probability of not having synchrony on a finite fixed interval $[a,b]$ at time $t$ decays to zero in the order of $O(t^{-1/2+o(1)})$. For $d=2$, our model shows fascinating spiraling or clustering behavior depending on the number $n$ of states and we discuss some interesting conjectures on higher dimensional lattices. If time allows, we also discuss asynchronous and continuous-state generalization of our GCA model for which the similar tree theorems hold, and applications to distributed networks of computers.

S M T W T F S
 
 
 
1
 
2
 
3
 
4
 
5
 
6
 
7
 
8
 
9
 
10
 
11
 
12
 
13
 
14
 
15
 
16
 
17
 
18
 
19
 
20
 
21
 
22
 
23
 
24
 
25
 
26
 
27
 
28
 
29
 
30
 
31