New Proof Shows That ‘Expander’ Graphs Synchronize

The proof establishes new conditions that cause connected oscillators to sway in sync.

Samuel Velasco and Paul Chaikin/Quanta Magazine

July 24, 2023

Introduction

Six years ago, Afonso Bandeira and Shuyang Ling were attempting to come up with a better way to discern clusters in enormous data sets when they stumbled into a surreal world. Ling realized that the equations they’d come up with were, unexpectedly, a perfect match for a mathematical model of spontaneous synchronization. Spontaneous synchronization is a phenomenon in which oscillators, which might take the form of pendulums, springs, human heart cells or fireflies, end up moving in lockstep without any central coordination mechanism.

Bandeira, a mathematician at the Swiss Federal Institute of Technology Zurich, and Ling, a data scientist at New York University, dove into synchronization research, obtaining a series of noteworthy results on the strength and structure that connections between oscillators must have to force the oscillators to synchronize. That work culminated in an October paper in which Bandeira proved (together with five co-authors) that synchronization is inevitable in special types of networks called expander graphs, which are sparse but also well connected.

Expander graphs turn out to have a slew of applications not only in math but also in computer science and physics. They can be used to create error-correcting codes and to figure out when simulations based on random numbers converge to the reality they are trying to simulate. Neurons can be modeled in a graph that some researchers believe forms an expander, due to the limited space for connections inside the brain. The graphs are also useful to geometers who try to understand how to traverse complicated surfaces, among other problems.