Expander graphs are globally synchronizing
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911385064046592 |
|---|---|
| author | Abdalla, Pedro Bandeira, Afonso S. Kassabov, Martin Souza, Victor Strogatz, Steven H. Townsend, Alex |
| author_facet | Abdalla, Pedro Bandeira, Afonso S. Kassabov, Martin Souza, Victor Strogatz, Steven H. Townsend, Alex |
| contents | 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 \geq (1 + \varepsilon) (\log n) / n$, the homogeneous Kuramoto model on the Erdős-Rényi 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2210_12788 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Expander graphs are globally synchronizing Abdalla, Pedro Bandeira, Afonso S. Kassabov, Martin Souza, Victor Strogatz, Steven H. Townsend, Alex Combinatorics Dynamical Systems Optimization and Control Probability 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 \geq (1 + \varepsilon) (\log n) / n$, the homogeneous Kuramoto model on the Erdős-Rényi 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$. |
| title | Expander graphs are globally synchronizing |
| topic | Combinatorics Dynamical Systems Optimization and Control Probability |
| url | https://arxiv.org/abs/2210.12788 |