A global synchronization theorem for oscillators on a random graph

Abstract

Consider n identical Kuramoto oscillators on a random graph. Specifically, consider Erdős-Rényi random graphs in which any two oscillators are bidirectionally coupled with unit strength, independently and at random, with probability 0 ≤ p ≤ 1. We say that a network is globally synchronizing if the oscillators converge to the all-in-phase synchronous state for almost all initial conditions. Is there a critical threshold for p above which global synchrony is extremely likely but below which it is extremely rare? It is suspected that a critical threshold exists and is close to the so-called connectivity threshold, namely, p ∼ log ⁡ ( n ) / n for n ≫ 1. Ling, Xu, and Bandeira made the first progress toward proving a result in this direction: they showed that if p ≫ log ⁡ ( n ) / ⁿ, then Erdős-Rényi networks of Kuramoto oscillators are globally synchronizing with high probability as n → ∞. Here, we improve that result by showing that p ≫ ^log ⁡ ( n ) / n suffices. Our estimates are explicit: for example, we can say that there is more than a 99.9996 % chance that a random network with n = ¹⁰ and p > 0.011 17 is globally synchronizing.