Graphs with connectivity $3/4 - \varepsilon$ 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\"odder.