Global synchronization of random 3-regular graphs
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$. Abdalla, Bandeira, Kassabov, Souza, Strogatz and Townsend showed that Erdős–Rényi graphs above the connectivity threshold, and uniform random $d$-regular graphs with $d \ge 600$, are globally synchronizing with high probability.
Problem. Prove or disprove that a uniform random $3$-regular graph on $n$ vertices is globally synchronizing with probability tending to $1$ as $n \to \infty$.
Source: Bandeira, Conjecture 3 of Randomstrasse101, in “Global Synchronization” (2024); Entry 2 of arXiv:2504.20539.
The statement is adapted from randomstrasse101.math.ethz.ch, whose text is available under CC BY 4.0.
Classification
- Primary
- PR — Probability
- Secondary
- CO, DS
- Keywords
- global synchronization, Kuramoto model, random regular graphs, 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}
}
@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}
}
@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}
}
Resolution claims
For a uniformly random labelled simple cubic graph on an even number of vertices, we give a proof claim that the probability that every local minimum of the homogeneous attractive Kuramoto energy is synchronized tends to zero. This is the opposite of the limit proposed in problem MD-06 of \emph{OpenProblemsInNLA} and Conjecture~3 of \emph{Randomstrasse101: Open Problems of 2024}. A two-by-two …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-06 | Open → Solution claimed | The registry's curators | Random cubic graphs admit nonsynchronized stable Kuramoto equilibria v1 recorded from OpenProblemsInNLA @ a345cfc, manuscripts/MD-06.pdf. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00029, "Global synchronization of random 3-regular graphs", clopen.solutions.