Graphs with connectivity $3/4-\epsilon$ are globally synchronizing

Abstract

We study synchronization in the Kuramoto model on finite graphs. We prove that there is an absolute constant $\eta >0$ such that every finite simple graph $G$ on $n$ vertices with minimum degree at least $(3/4-\eta )n$ has no local minima of the Kuramoto energy other than the fully synchronized states. This strictly improves the previous $3/4$ upper bound and refutes a conjecture of Bandeira, Kireeva, Maillard, and Rödder.

17 pages