JOINT PACM / CSML Globally Synchronizing Graphs

Afonso Bandeira, ETH Zurich
Fine Hall 214

In the 1600s, Christiaan Hyugens realized that two pendulum clocks (an invention of his!) placed in the same wooden table eventually fall into synchrony. Since then, synchronization of coupled oscillators has been an important subject of study in classical mechanics and nonlinear dynamics. The Kuramoto model, proposed in the 1970s, has become a prototypical model used for rigorous mathematical analysis in this field. A realization of this model consists of a collection of identical oscillators with interactions given by a network, which we identify respectively with vertices and edges of a graph.

In this talk we discuss which graphs are globally synchronizing, meaning that all but a measure-zero set of initial conditions converge into the fully synchronized state. We show that large expansion of the underlying graph is a sufficient condition (but far from necessary) and solve a conjecture of Ling, Xu and Bandeira stating that Erdos-Renyi random graphs are globally synchronizing above their connectivity threshold.

Time permitting, we will discuss connections with studying the non-convex landscape of the Burer-Monteiro algorithm for Community Detection in the Stochastic Block Model.

Joint work with Pedro Abdalla (ETHZ), Martin Kassabov (Cornell), Victor Souza (Cambridge), Steven H. Strogatz (Cornell), Alex Townsend (Cornell).