The minimum-degree threshold 3/4 for global synchronization
Call a graph on $n$ vertices globally synchronizing if, for its adjacency matrix $A$, the only local minima of the Kuramoto energy $$\mathcal{E}(\theta) = \frac12\sum_{i,j=1}^n A_{ij}\bigl(1-\cos(\theta_i-\theta_j)\bigr), \qquad \theta \in [0,2\pi)^n,$$ are its global minima $\theta_1 = \dots = \theta_n$. Kassabov, Strogatz and Townsend showed that every graph on $n$ vertices with minimum degree greater than $\frac34 n - 1$ is globally synchronizing, and that $\frac34$ is the best bound a purely linear stability analysis can give.
Problem. Prove or disprove that for every $\varepsilon > 0$ there is a graph, on some number $n$ of vertices, with minimum degree at least $(\frac34 - \varepsilon)n$ that is not globally synchronizing.
Source: Bandeira, Conjecture 5 of Randomstrasse101, in “Global Synchronization” (2024); Entry 2 of arXiv:2504.20539. The threshold 3/4 was suggested by Townsend, Stillman and Strogatz (2020).
The statement is adapted from randomstrasse101.math.ethz.ch, whose text is available under CC BY 4.0.
Classification
- Primary
- CO — Combinatorics
- Secondary
- DS
- Keywords
- extremal graph theory, global synchronization, Kuramoto model, Randomstrasse101
- Literature checked
- Oct. 2, 2026 by clemens-admin
References
@misc{randomstrasse2024,
author = {Bandeira, Afonso S. and Kireeva, Anastasia and Maillard, Antoine and R{\"o}dder, Almut},
title = {{Randomstrasse101}: Open Problems of 2024},
year = {2025},
eprint = {2504.20539},
archivePrefix = {arXiv}
}
@article{kassabov2021dense,
author = {Kassabov, Martin and Strogatz, Steven H. and Townsend, Alex},
title = {Sufficiently dense {K}uramoto networks are globally synchronizing},
journal = {Chaos},
volume = {31},
pages = {073135},
year = {2021}
}
@article{townsend2020dense,
author = {Townsend, Alex and Stillman, Michael and Strogatz, Steven H.},
title = {Dense networks that do not synchronize and sparse ones that do},
journal = {Chaos},
volume = {30},
year = {2020},
eprint = {1906.10627},
archivePrefix = {arXiv}
}
@misc{abdalla2022expander,
author = {Abdalla, Pedro and Bandeira, Afonso S. and Kassabov, Martin and Souza, Victor and Strogatz, Steven H. and Townsend, Alex},
title = {Expander graphs are globally synchronizing},
year = {2022},
eprint = {2210.12788},
archivePrefix = {arXiv}
}
Resolution claims
We study synchronization in the Kuramoto model on finite graphs. We prove that there is an absolute constant $η>0$ such that every finite simple graph $G$ on $n$ vertices with minimum degree at least $(3/4-η)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 …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-02 | Open → Solution claimed | The registry's curators | Graphs with connectivity $3/4 - \varepsilon$ are globally synchronizing v1 recorded from arXiv:2608.20010v1. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00053, "The minimum-degree threshold 3/4 for global synchronization", clopen.solutions.