Global Synchronization (problems 3-5)

In the 17th century, Christiaan Huygens (inventor of the pendulum clock) observed that pendulum clocks have a tendency to spontaneously synchronize when hung on the same board. This phenomenon of spontaneous synchronization of coupled oscillators has since become a central object of study in dynamical systems.

We will focus here on spontaneous synchronization of $n$ coupled oscillators with pairwise connections given by a graph with adjacency matrix $A\in\mathbb{R}^{n\times n}$. The celebrated Kuramoto model (Kuramoto, 1975) models the oscillators as gradient flow on $ \mathcal{E}(\theta) = \frac12\sum_{i,j=1}^n A_{ij}\left(1-\cos(\theta_i-\theta_j)\right),$ where the parameterization $\theta\in[0,2\pi[^n$ represents each oscillators angle in the moving frame of its natural frequency (for the sake of the sequel the derivation of this potential is not crucial you can see, e.g. (Abdalla et al., 2023) for more details). This motivates the following Definition which is central to what follows.

Definition 1

We say an $n\times n$ matrix $A$ is globally synchronizing if the only local minima of $\mathcal{E}:\mathbb{S}^{n-1}\to \mathbb{R}$, parameterized by $\theta\in[0,2\pi[^n$ and given by \begin{equation} \mathcal{E}(\theta) = \frac12\sum_{i,j=1}^n A_{ij}\left(1-\cos(\theta_i-\theta_j)\right), \end{equation} are the global minima corresponding to $\theta_i=c$, $\forall_i$. A graph $G$ is said to be globally synchronizing if its adjacency matrix is globally synchronizing.

Abdalla, Bandeira, Kassabov, Souza, Strogatz, and Townsend (Abdalla et al., 2023) recently showed that a random Erdős–Rényi graph is globally synchronizing above the connectivity threshold with high probability (you can also see the Quanta article covering this. The same paper also shows that a uniform $d$-regular graph is globally synchronizing with high probability for $d\geq 600$, but it leaves open the following question.

Conjecture 3 (Globally Synchronizing Regular Graphs)

A uniform random $3$-regular graph is globally synchronizing with high probability (probability going to $1$ as $n\to\infty$).

The following question is motivated by trying to understand the Burer-Monteiro algorithmic approach to community detection in the stochastic block model (Kuramoto, 2016). The most recent progress is in (McRae et al., 2024) which answers a high rank version of this question.

Conjecture 4 (Global Synchrony with negative edges)

Given any $\varepsilon>0$, the $n\times n$ random matrix $A$ with zero diagonal and off-diagonal entries given by
\(A_{ij} = \begin{cases} 1 \text{ with probability } \frac{1}{2}+\delta\\ -1 \text{ with probability } \frac{1}{2}-\delta \end{cases}\) , with $\delta \geq (1+\varepsilon)\sqrt{\frac{\log n}{2n}}$, is globally synchronizing with high probability.

Another elusive question about global synchrony is the ``extremal combinatorics’’ version of the question.

Conjecture 5 (Density threshold for Global Synchrony)

For any $\varepsilon>0$, there exists $n>0$ and a graph $G$ on $n$ nodes such that the minimum degree of $G$ is at least $\left(\frac{3}{4}-\varepsilon\right)n$ and $G$ is not globally synchronizing.

Kassabov, Strogatz, and Townsend (Kassabov et al., 2021) showed an upper bound on the $\frac34$ threshold in Conjecture 5, and the same paper contains evidence that $\frac34$ is the correct threshold (by arguing that an upper bound below $\frac34$ would need to go beyond linear analysis of the dynamical system).

References

1. Kuramoto, Y. (1975). Self-entrainment of a population of coupled non-linear oscillators. International Symposium on Mathematical Problems in Theoretical Physics, 420–422.
2. Abdalla, P., A. S. Bandeira, Kassabov, M., & Souza, V. (2023). Expander graphs are globally synchronizing. Preprint, Available on ArXiv.
3. Kuramoto, Y. (2016). On the low-rank approach for semidefinite programs arising in synchronization and community detection. COLT.
4. McRae, A., Abdalla, P., Bandeira, A. S., & Boumal, N. (2024). Nonconvex landscapes for Z2 synchronization and graph clustering are benign near exact recovery thresholds. Preparing, Available on ArXiv.
5. Kassabov, M., S. H. Strogatz, & A. Townsend. (2021). Sufficiently dense Kuramoto networks are globally synchronizing. Chaos \textbf31.