# Expander graphs are globally synchronizing

arXiv: https://arxiv.org/abs/2210.12788 · HTML: https://mlsanity.com/paper/2210.12788/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Oct 2022.

## Built on by (most cited first, 8 of 8)

- [A mathematical perspective on Transformers](https://mlsanity.com/paper/2312.10794/) (2023)
- [Dynamic metastability in the self-attention model](https://mlsanity.com/paper/2410.06833/) (2024)
- [Clustering in Causal Attention Masking](https://mlsanity.com/paper/2411.04990/) (2024)
- [Quantitative Clustering in Mean-Field Transformer Models](https://mlsanity.com/paper/2504.14697/) (2025)
- [Critical attention scaling in long-context transformers](https://mlsanity.com/paper/2510.05554/) (2025)
- [Synchronization on circles and spheres with nonlinear interactions](https://mlsanity.com/paper/2405.18273/) (2024)
- [Synchronization of mean-field models on the circle](https://mlsanity.com/paper/2507.22857/) (2025)
- [Benign landscape for Burer-Monteiro factorizations of MaxCut-type semidefinite programs](https://mlsanity.com/paper/2411.03103/) (2024)

## Abstract (arXiv)

The Kuramoto model is fundamental to the study of synchronization. It consists of a collection of oscillators with interactions given by a network, which we identify respectively with vertices and edges of a graph. In this paper, we show that a graph with sufficient expansion must be globally synchronizing, meaning that a homogeneous Kuramoto model of identical oscillators on such a graph will converge to the fully synchronized state with all the oscillators having the same phase, for every initial state up to a set of measure zero. In particular, we show that for any varepsilon > 0 and p ≥ (1 + varepsilon) (log n) / n, the homogeneous Kuramoto model on the ErdHos-R'enyi random graph G(n, p) is globally synchronizing with probability tending to one as n goes to infinity. This improves on a previous result of Kassabov, Strogatz, and Townsend and solves a conjecture of Ling, Xu, and Bandeira. We also show that the model is globally synchronizing on any d-regular Ramanujan graph, and on typical d-regular graphs, for large enough degree d.