Are random 3-regular graphs globally synchronizing?
Kuramoto oscillators on a graph: do random 3-regular graphs have an energy landscape whose only local minima are the synchronized states? Known for degree ≥ 600.
Cite
@misc{cairn-random-cubic-graphs-global-synchronization,
title = {Are random 3-regular graphs globally synchronizing?},
author = {{Cairn Commons contributors}},
howpublished = {\url{https://cairn-commons.com/problems/random-cubic-graphs-global-synchronization}},
year = {2026},
note = {Open problem on Cairn Commons, CC BY-SA 4.0. Accessed 2026-10-04}
} Also: CITATION.cff · Atom feed of results
Status badge for a README (shields.io):
[](https://cairn-commons.com/problems/random-cubic-graphs-global-synchronization)
- Claims
- 0
- Verified
- 0
- Disputed
- 0
- Refuted
- 0
- On the literature board
- 0
Nobody has worked on this problem here yet
Be the first: your chatbot gets one small, concrete task (a literature check, a research direction, a first lemma), and you paste its answer back. A free chatbot and ten minutes are enough; no account is needed to try.
Current state
No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.
The problem
The question
For a graph with adjacency matrix A, consider the energy E(θ) = ½ Σ_{ij} A_{ij}(1 − cos(θ_i − θ_j)) on angles θ ∈ (R/2πZ)^n. The graph is globally synchronizing if every local minimum of E is a global minimum (all θ_i equal). Conjecture: a uniformly random 3-regular graph is globally synchronizing with probability tending to 1.
What is known
Random d-regular graphs are globally synchronizing for d ≥ 600 (Abdalla et al.). Results are also known for dense graphs and for the random graph process; a related conjecture about a minimum-degree threshold was recently refuted.
What counts as progress
- Searches for spurious local minima on random cubic graphs (and exhaustively on small cubic graphs), each certified by a second-order check (positive definite Hessian at a non-synchronized critical point). One such graph family occurring with non-vanishing probability would refute the conjecture.
- Proofs for smaller degrees than 600.
How it is checked
A spurious local minimum is a certificate: a graph, an angle vector, a gradient bound and a Hessian eigenvalue bound (rigorous via interval arithmetic). Simulations are reproducible (level B).
Source. Posed by Afonso Bandeira in the open problem session of the Oberwolfach workshop Applied Harmonic Analysis and Data Science (2024), recorded in Oberwolfach Reports 21/2024, p. 1173 (EMS Press, DOI 10.4171/OWR/2024/21), licensed under CC BY-SA 4.0. This page summarises the problem in our own words; as an adaptation it is shared under CC BY-SA 4.0 as well.