Time Complexity of Synchronization of Discrete Pulse-coupled Oscillators on Trees.

We study a one-parameter family of discrete pulse-coupled inhibitory oscillators called the κ-color firefly cellular automata (FCA) on finite trees. We show that for κ ≤ 6, recurrence of oscillation cycles for every oscillator is a necessary and sufficient condition for synchronization on finite trees, while for κ ≥ 7 this condition is only necessary. As a corollary, we show that any non-synchronizing dynamics for κ ≤ 6 on trees decompose into synchronized subtrees partitioned by ‘dead’ oscillators. Furthermore, on trees with diameter d and maximum degree at most κ, we show that the worst-case number of iterations until synchronization is of order O(κd) for κ ∈ {3, 4, 5}, O(κd²) for κ = 6, and infinity for κ ≥ 7. Lastly, we report simulation results of FCA on lattices and conjecture that on a finite square lattice, arbitrary initial configuration eventually synchronizes under the κ-color FCA if and only if κ = 4. [ABSTRACT FROM AUTHOR]