# A global synchronization theorem for oscillators on a random graph

Martin Kassabov  Department of Mathematics, Cornell University, Ithaca, NY
14853  Steven H. Strogatz  Department of Mathematics, Cornell University,
Ithaca, NY 14853  Alex Townsend  Department of Mathematics, Cornell
University, Ithaca, NY 14853

###### Abstract

Consider $n$ identical Kuramoto oscillators on a random graph. Specifically,
consider Erdős–Rényi random graphs in which any two oscillators are
bidirectionally coupled with unit strength, independently and at random, with
probability $0\leq p\leq 1$. We say that a network is globally synchronizing
if the oscillators converge to the all-in-phase synchronous state for almost
all initial conditions. Is there a critical threshold for $p$ above which
global synchrony is extremely likely but below which it is extremely rare? It
is suspected that a critical threshold exists and is close to the so-called
connectivity threshold, namely, $p\sim\log(n)/n$ for $n\gg 1$. Ling, Xu, and
Bandeira made the first progress toward proving a result in this direction:
they showed that if $p\gg\log(n)/n^{1/3}$, then Erdős–Rényi networks of
Kuramoto oscillators are globally synchronizing with high probability as
$n\rightarrow\infty$. Here we improve that result by showing that
$p\gg\log^{2}(n)/n$ suffices. Our estimates are explicit: for example, we can
say that there is more than a $99.9996\%$ chance that a random network with
$n=10^{6}$ and $p>0.01117$ is globally synchronizing.

††preprint: AIP/123-QED

> Random graphs are fascinating topologies on which to study the dynamics of
> coupled oscillators. Despite the statistical nature of random graphs,
> coherent synchronization seems to be ubiquitous above a critical threshold.
> To investigate this, we consider the homogeneous version of the Kuramoto
> model in which all $n$ oscillators have the same intrinsic frequency. For
> simplicity, the oscillators are arranged on an Erdős–Rényi random graph in
> which any two oscillators are coupled with unit strength by an undirected
> edge, independently at random, with some probability $0\leq p\leq 1$;
> however, our proof strategy can be applied to other random graph models too.
> We say that a network is globally synchronizing if the oscillators converge
> to the all-in-phase synchronous state for almost all initial conditions. For
> what values of $p$ is an Erdős–Rényi random network very likely to be
> globally synchronizing? Here we prove that $p\gg\log^{2}(n)/n$ as
> $n\rightarrow\infty$ is a sufficient condition. Our proof uses trigonometric
> inequalities and an amplification argument involving the first two moments
> of the oscillator phase distribution that must hold for any stable phase-
> locked state. Specifically, we show that the spectral norms of the mean-
> centered adjacency and graph Laplacian matrix can be used to guarantee that
> a network is globally synchronizing. Our analysis is explicit, and we can
> reason about random networks of finite, practical size.

##  I Introduction

Networks of coupled oscillators have long been studied in biology, physics,
engineering, and nonlinear dynamics. winfree1967biological ;
winfree1980geometry ; kuramoto1984chemical ; mirollo1990synchronization ;
watanabe1994constants ; pikovsky2003synchronization ; strogatz2003sync ;
dorfler2014synchronization ; pikovsky2015dynamics ; rodrigues2016kuramoto ;
abrams2016introduction ; boccaletti2018synchronization ; matheny2019exotic
Recently they have begun to attract the attention of other communities as
well. For example, oscillator networks have been recognized as having the
potential to yield “beyond-Moore’s law” computational devices CsabaPorod  for
graph coloring, Wu  image segmentation, Novikov  and approximate maximum graph
cuts. Steinerberger  They have also become a model problem for understanding
the global convergence of gradient descent in nonlinear optimization.
ling2018landscape

In such settings, global issues come to the fore. When performing gradient
descent, for instance, one typically wants to avoid getting stuck in local
minima. Conditions to enforce convergence to the global minimum then become
desirable. Likewise, if an oscillator network has only a single, globally
attracting state, we know exactly how the system will behave in the long run.

We say that a network of oscillators _globally synchronizes_ if it converges
to a state for which all the oscillators are in phase, starting from all
initial conditions except a set of measure zero. Until recently, only a few
global synchronization results were known for networks of oscillators.
mirollo1990synchronization ; watanabe1994constants  These results were
restricted to complete graphs, in which each oscillator is coupled to all the
others. In the past decade, however, several advances have been made for a
wider class of network structures, starting with work by Taylor,
taylor2012there  who proved that if each oscillator in a network of identical
Kuramoto oscillators is connected to at least 94 percent of the others, the
network will fall into perfect synchrony for almost all initial conditions, no
matter what the topology of the network is like in other respects. Taylor’s
result was strengthened by Ling, Xu, and Bandeira ling2018landscape  in 2018
and further progress has been made since then. lu2020synchronization ;
kassabovtownsendstrogatz

Ling et al. ling2018landscape  also made a seminal advance in the study of
_random_ networks. They considered identical Kuramoto oscillators on an
Erdős–Rényi random graph, ErdosRenyi  in which any two oscillators are coupled
with unit strength, independently and at random, with probability $0\leq p\leq
1$; otherwise they are uncoupled. They showed that if $p\gg\log(n)/n^{1/3}$,
then with high probability the network is globally synchronizing as
$n\rightarrow\infty$.

The open question is to find and prove the sharpest result along these lines.
Intuitively, as one increases the value of $p$ from $0$ to $1$, one expects to
find a critical threshold above which global synchrony is extremely likely and
below which it is extremely rare. At the very least, for global synchrony to
be ubiquitous, $p$ must be large enough to ensure that the random network is
connected, and from the theory of random graphs ErdosRenyi  we know that
connectedness occurs with high probability once $p>(1+\varepsilon)\log(n)/n$
for any $\varepsilon>0$. So the critical threshold for global synchronization
cannot be any smaller than this connectivity threshold, and is apt to be a
little above. On the basis of numerical evidence, Ling et al.
ling2018landscape  conjectured, and we agree with them, that if
$p\gg\log(n)/n$ then Erdős–Rényi graphs are globally synchronizing as
$n\rightarrow\infty$, but nobody has proven that yet. The challenge is to see
how close one can get. In this paper, we come within a factor of $\log(n)$ and
prove that $p\gg\log^{2}(n)/n$ is sufficient to give global synchrony with
high probability. With the aid of a computer, we have convincing evidence that
$p\gg\log(n)/n$ is sufficient as $n\rightarrow\infty$ (see Section VI.1).

We study the homogeneous Kuramoto model jadbabaie2004stability ; wiley2006size
; taylor2012there  in which each oscillator has the same frequency $\omega$.
By going into a rotating frame at this frequency, we can set $\omega=0$
without loss of generality. Then phase-locked states in the original frame
correspond to equilibrium states in the rotating frame. So, to explore the
question that concerns us, it suffices to study the following simplified
system of identical Kuramoto oscillators:

$\frac{d\theta_{j}}{dt}=\sum_{k=1}^{n}A_{jk}\sin\\!\left(\theta_{k}-\theta_{j}\right),\quad
1\leq j\leq n,$ (1)

where $\theta_{j}(t)$ is the phase of oscillator $j$ (in the rotating frame)
and the adjacency matrix $A$ is randomly generated. In particular,
$A_{jk}=A_{kj}=1$ with probability $p$, with $A_{jk}=A_{kj}=0$ otherwise,
independently for $1\leq j,k\leq n$. Thus, all interactions are assumed to be
symmetric, equally attractive, and of unit strength. We take the unusual
convention that the network can have self-loops so that oscillator $i$ is
connected to itself with probability $p$, i.e.,
$\mathbb{P}\left[A_{jj}=1\right]=p$. Since $\sin(0)=0$, this convention does
not alter the dynamics of the oscillators but it does make proof details
easier to write down.

Finally, since the adjacency matrix $A$ is symmetric, we know that (1) is a
gradient system. wiley2006size ; jadbabaie2004stability  Thus, all the
attractors of (1) are equilibrium points, which means we do not need to
concern ourselves with the possibility of more complicated attracting
invariant sets like limit cycles, tori, or strange attractors.

We find it helpful to visualize the oscillators on the unit circle, where
oscillator $j$ is positioned at the coordinate
$(\cos(\theta_{j}),\sin(\theta_{j}))$. From this perspective, a network is
globally synchronizing if starting from any initial positions (except a set of
measure zero), all the oscillators eventually end up at the same point on the
circle. Due to periodicity, we assume that the phases, $\theta_{j}$, take
values in the interval $[-\pi,\pi)$.

One cannot determine whether a network is globally synchronizing by numerical
simulation of (1), as it is impossible to try all initial conditions. Of
course, one can try millions of random initial conditions of the oscillators’
phases and then watch the dynamics of (1). But even if all observed initial
states eventually fall into the all-in-phase state, one cannot conclude the
system is globally synchronizing because other stable equilibria could still
exist; their basins might be minuscule but could nevertheless have positive
measure.

With that caveat in mind, we note that such numerical experiments have been
conducted, and they suggest that $p\gg\log(n)/n$ is sufficient for global
synchronization. ling2018landscape  In this paper, we investigate global
synchrony via theoretical study. We show that $p\gg\log^{2}(n)/n$ is good
enough to ensure global synchronization with high probability, improving on
$p\gg\log(n)/n^{1/3}$ proved by Ling et al., ling2018landscape  and bringing
us closer to the connectivity threshold of Erdős–Rényi graphs.

Although we focus on Erdős–Rényi graphs, many of the inequalities we derive
hold for any random or deterministic network. To highlight this, we state many
of our findings for a general graph $G$ and a general parameter
$p\in\mathbb{R}$. In the end, we restrict ourselves back to Erdős–Rényi graphs
and take $p$ to be the probability of a connection between any two
oscillators.

Our results depend on both the adjacency matrix $A$ and the graph Laplacian
matrix $L=D-A$, where $D$ is a diagonal matrix and $D_{ii}$ is the degree of
vertex $i$ (counting self-loops). For any $p\in\mathbb{R}$, denote the shifted
adjacency and graph Laplacian matrix by

$\Delta_{A}=A-pJ_{n},\qquad\Delta_{L}=L-pJ_{n}+npI_{n},$ (2)

where $J_{n}$ is the $n\times n$ matrix of all ones and $I_{n}$ is the
$n\times n$ identity matrix. It is worth noting that for Erdős–Rényi graphs,
the shifts are precisely the expectation of the matrices as
$\mathbb{E}\left[A\right]=pJ_{n}$ and
$\mathbb{E}\left[L\right]=pJ_{n}-npI_{n}$. Remarkably, we show that the global
synchrony of a network can be guaranteed by ensuring that the spectral norms
$\|\Delta_{A}\|$ and $\|\Delta_{L}\|$ satisfy particular inequalities. The
spectral norm of a symmetric matrix is the maximum eigenvalue in absolute
magnitude, and $\|\Delta_{A}\|$ and $\|\Delta_{L}\|$ are extensively studied
in the random matrix literature. FK ; Vu  What is remarkable is that no other
information about the network’s structure is needed; the norms of these two
matrices alone encapsulate the structural aspects that matter for global
synchronization. We also find it appealing that the spectral norm of the graph
Laplacian matrix appears naturally in our analysis, as it has been used
previously to study the dynamics of networks of oscillators Pecora  as well as
diffusion on graphs.

While we focus in this paper on global synchronization of identical
oscillators, Medvedev and his collaborators have considered other aspects of
synchronization for non-identical oscillators on Erdős–Rényi graphs, as well
as on other graphs such as Cayley and Watts–Strogatz graphs, often in the
continuum limit. Medvedev1 ; Medvedev2 ; Medvedev3 ; ChibaMedvedevMizuhara
Their findings have a similar overarching message that synchronization occurs
spontaneously above a critical threshold.

##  II Overview of our proof strategy

To prove that a random graph is globally synchronizing with high probability,
we bridge the gap between spectral graph theory and coupled oscillator theory.
The literature contains many good probabilistic estimates for the spectral
norm of a random graph’s adjacency and graph Laplacian matrices, which we use
to control the long-time dynamics of (1). The key to our proof is to establish
conditions on these two spectral norms that force any stable equilibrium to
have phases that lie within a half-circle. Confining the phases in this way
then guarantees global synchronization, because it is known that the only
stable equilibrium of (1) with phases confined to a half-circle is the all-in-
phase synchronized state. jadbabaie2004stability ; dorfler2014synchronization

Our first attempt at controlling the phases is the inequality we state below
as (9), which can be used to guarantee that very dense Erdős–Rényi graphs are
globally synchronizing with high probability; as an aside, when $p=1$ this
inequality provides a new proof that a complete graph of identical Kuramoto
oscillators is globally synchronizing. watanabe1994constants  A similar
inequality to (9) was derived by Ling, Xu, and Bandeira ling2018landscape  to
show that $p\gg\log(n)/n^{1/3}$ is sufficient for global synchrony with high
probability.

To improve on (9), our argument becomes more intricate. We carefully examine
the possible distribution of edges between oscillators whose phases lie on
different arcs of the circle, and show that any equilibrium is destabilized if
there are too many edges between oscillators that have disparate phases (see
Lemma 8 and Figure 2).

##  III Bounds on the order parameter and its higher-order moments

An important quantity in the study of Kuramoto oscillators is the so-called
complex order parameter, $\rho_{1}$. The magnitude of $\rho_{1}$ is between
$0$ and $1$ and measures the synchrony of the oscillators in the network. We
find it useful to also look at second-order moments of the oscillator
distribution for analyzing the synchrony of random networks. Higher-order
moments are also called Daido order parameters and can be used to analyze
oscillators with all-to-all coupling, corresponding to a complete graph.
daido1992order ; Perez_97 ; pikovsky2015dynamics ; terada2020linear

For an equilibrium $\theta=(\theta_{1},\ldots,\theta_{n})$, we define the
first- and second-order moments as

$\rho_{1}=\frac{1}{n}\sum_{j}e^{i\theta_{j}},\qquad\rho_{2}=\frac{1}{n}\sum_{j}e^{2i\theta_{j}}.$

(For convenience, we use the notation $\sum_{j}$ to mean $\sum_{j=1}^{n}$.)
Without loss of generality, we may assume that the complex order parameter
$\rho_{1}$ is real-valued and non-negative. To see this, write
$\rho_{1}=|\rho_{1}|e^{i\psi}$ for some $\psi$. Then,
$\hat{\theta}=(\theta_{1}-\psi,\ldots,\theta_{n}-\psi)$ is also an equilibrium
of (1) with the same stability properties as $\theta$ since (1) is invariant
under a global shift of all phases by $\psi$. Therefore, for the rest of this
paper, we assume that $\psi=0$ for any equilibrium of interest with
$0\leq\rho_{1}\leq 1$. When $\rho_{1}=1$, the oscillators are in pure
synchrony and when $\rho_{1}\approx 0$, the phases are scattered around the
unit circle without a dominant phase.

To avoid working with complex numbers, it is convenient to consider the
quantity $|\rho_{2}|^{2}$. For $m=1,2$, we have

$|\rho_{m}|^{2}=\frac{1}{n^{2}}\left(\sum_{k}e^{im\theta_{k}}\sum_{j}e^{-im\theta_{j}}\right)=\frac{1}{n^{2}}\sum_{j,k}\cos(m(\theta_{k}-\theta_{j})).$
(3)

By analyzing $\rho_{1}^{2}$ and $|\rho_{2}|^{2}$, one hopes to witness the
rough statistics of an equilibrium to understand its potential for synchrony
without concern for its precise pattern of phases.

Let $q_{\theta}=(e^{i\theta_{1}},\dots,e^{i\theta_{n}})^{\top}$ and note that

$\sum_{j,k}A_{jk}\cos(\theta_{k}-\theta_{j})=\overline{q_{\theta}}^{\top}Aq_{\theta},$

where $A$ is the adjacency matrix, $\overline{q_{\theta}}$ is the complex
conjugate of $q_{\theta}$, and ⊤ denotes the transpose of a vector. Since
$\cos^{2}(\theta_{k}-\theta_{j})=\frac{1}{2}(\cos(2(\theta_{k}-\theta_{j}))+1)$,
we have

$\sum_{j,k}A_{jk}\cos^{2}(\theta_{k}-\theta_{j})=\frac{1}{2}\overline{q_{2\theta}}^{\top}Aq_{2\theta}+\frac{1}{2}\mathbf{1}^{\top}A\mathbf{1},$

where $\mathbf{1}$ is the vector of all ones and
$q_{2\theta}=(e^{i2\theta_{1}},\dots,e^{i2\theta_{n}})^{\top}$.

We would like to know when a stable equilibrium is close to the all-in-phase
state, and we know this when $\rho_{1}$ is close to $1$. Therefore, we begin
by deriving a lower bound on $\rho_{1}$ for any stable equilibrium of (1).
Similar inequalities involving $\rho_{1}^{2}$ and $|\rho_{2}|^{2}$ have been
used to demonstrate that sufficiently dense Kuramoto networks are globally
synchronizing. ling2018landscape ; kassabovtownsendstrogatz

######  Lemma 1.

Let $G$ be a connected graph and $\theta$ a stable equilibrium of (1). For any
$p>0$, we have

$\rho_{1}^{2}\geq\frac{1+|\rho_{2}|^{2}}{2}-\frac{2\|\Delta_{A}\|}{np},$ (4)

where the mean-shifted adjacency matrix, $\Delta_{A}$, is defined in (2).

###### Proof.

Since $\Delta_{A}=A-pJ_{n}$, we have

$\overline{q_{\theta}}^{\top}Aq_{\theta}=p\overline{q_{\theta}}^{\top}J_{n}q_{\theta}+\overline{q_{\theta}}^{\top}\Delta_{A}q_{\theta}.$

One finds that $\overline{q_{\theta}}^{\top}J_{n}q_{\theta}=n^{2}\rho_{1}^{2}$
by (3) and that
$|\overline{q_{\theta}}^{\top}\Delta_{A}q_{\theta}|\leq\|\Delta_{A}\|\|q_{\theta}\|^{2}\leq
n\|\Delta_{A}\|$ so

$\left|\sum_{j,k}A_{jk}\cos(\theta_{k}-\theta_{j})-n^{2}p\rho_{1}^{2}\right|\leq
n\|\Delta_{A}\|.$ (5)

By the same reasoning for $\overline{q_{2\theta}}^{\top}Aq_{2\theta}$, we find
that

$\left|\sum_{j,k}A_{jk}\cos(2(\theta_{k}-\theta_{j}))-n^{2}p|\rho_{2}|^{2}\right|\leq
n\|\Delta_{A}\|.$

Moreover,
$\mathbf{1}^{\top}A\mathbf{1}=\mathbf{1}^{\top}\Delta_{A}\mathbf{1}+n^{2}p$,
so $\left|\mathbf{1}^{\top}A\mathbf{1}-n^{2}p\right|\leq n\|\Delta_{A}\|$. We
conclude that

$\left|\sum_{j,k}A_{jk}\cos^{2}(\theta_{k}-\theta_{j})-n^{2}p\frac{|\rho_{2}|^{2}+1}{2}\right|\leq
n\|\Delta_{A}\|.$ (6)

Since $\theta$ is stable equilibrium for (1), it is known that

$\sum_{j,k}A_{jk}\cos(\theta_{k}-\theta_{j})(1-\cos(\theta_{k}-\theta_{j}))\geq
0$

as shown by Ling et al. ling2018landscape  on p. 1893 of their paper. From (5)
and (6), we must have

$n^{2}p\rho_{1}^{2}+n\|\Delta_{A}\|\geq
n^{2}p\frac{|\rho_{2}|^{2}+1}{2}-n\|\Delta_{A}\|,$

which is equivalent to the statement of the lemma. ∎

To maximize the lower bound on $\rho_{1}^{2}$ from Lemma 1, one can optimize
over $p$. For a random graph where each edge has a fixed probability of being
present, independently of the other edges, we usually just select $p$ to be
that probability. Regardless, to make the lower bound on $\rho_{1}^{2}$ in
Lemma 1 useful, we need to find a nontrivial lower bound on $|\rho_{2}|^{2}$,
since this quantity appears in the right hand side of (4). To obtain such a
bound we use the following technical lemma.

######  Lemma 2.

Let $G$ be a connected graph and $\theta$ a stable equilibrium. We have

$\|\Delta_{A}q_{\theta}\|^{2}\geq
n^{2}p^{2}\rho_{1}^{2}\left(\sum_{j}\sin^{2}(\theta_{j})+\sum_{j,\cos(\theta_{j})\leq
0}\cos^{2}(\theta_{j})\right),$

where $\|\cdot\|$ is the Euclidean norm.

###### Proof.

Select any $j$ such that $1\leq j\leq n$. From the fact that $\theta$ is an
equilibrium, we have $\sum_{k}A_{jk}\sin(\theta_{k}-\theta_{j})=0$. Moreover,
because the equilibrium is stable, we also have
$\sum_{k}A_{jk}\cos(\theta_{k}-\theta_{j})\geq 0$, which follows as the
diagonal entries of the Hessian matrix must be nonnegative at a stable
equilibrium (see (2.3) of Ling et al. ling2018landscape ). These inequalities
can be written as

${\rm Re\,}(e^{-i\theta_{j}}e_{j}^{\top}Aq_{\theta})\geq 0\quad\mbox{and
}\quad{\rm Im\,}(e^{-i\theta_{j}}e_{j}^{\top}Aq_{\theta})=0,$

where $e_{j}$ is the $j$th unit vector. Since $\Delta_{A}=A-pJ_{n}$ and using
that $J_{n}q_{\theta}=n\rho_{1}\mathbf{1}$, we find that

$|{\rm
Im\,}(e^{-i\theta_{j}}e_{j}^{\top}\Delta_{A}q_{\theta})|=np\rho_{1}\left|\sin(\theta_{j})\right|.$

If $\cos\theta_{j}\leq 0$, then we also have

$\displaystyle{\rm Re\,}(e^{-i\theta_{j}}e_{j}^{\top}$
$\displaystyle\Delta_{A}q_{\theta})=\sum_{k}(A_{jk}-p)\cos(\theta_{k}-\theta_{j})$
$\displaystyle=$
$\displaystyle\sum_{k}A_{jk}\cos(\theta_{k}-\theta_{j})-np\rho_{1}\cos\theta_{j}\geq
np\rho_{1}\left|\cos\theta_{j}\right|.$

The inequality in the lemma follows by squaring the above inequalities,
summing over $j$, and noting that $|e^{-i\theta_{j}}|=1$. ∎

To see how Lemma 2 can be used to derive a lower bound on $|\rho_{2}|^{2}$ for
any stable equilibrium state, we start by dropping the second sum in Lemma 2.
By using the upper bound $\|\Delta_{A}q_{\theta}\|^{2}\leq
n\|\Delta_{A}\|^{2}$, we find that
$\sum_{j}\sin^{2}(\theta_{j})\leq\|\Delta_{A}\|^{2}/(np^{2}\rho_{1}^{2})$.
Since $n{\rm
Re}\\!\left(\rho_{2}\right)=\sum_{j}\cos(2\theta_{j})=\sum_{j}\left(1-2\sin^{2}(\theta_{j})\right)$,
we have the following lower bound on $|\rho_{2}|$:

$|\rho_{2}|\geq{\rm
Re}(\rho_{2})=\frac{1}{n}\sum_{j}\left(1-2\sin^{2}(\theta_{j})\right)\geq
1-\frac{2\|\Delta_{A}\|^{2}}{n^{2}p^{2}\rho_{1}^{2}}.$ (7)

From (4) and (7), we observe that when $\|\Delta_{A}\|\ll np$, then $\rho_{1}$
and $|\rho_{2}|$ must both be close to $1$. Intuitively, this should mean that
the corresponding stable equilibrium, $\theta$, must be close to the all-in-
phase state with the possible exception of a small number of stray
oscillators. However, our goal is to prove global synchrony, which is a more
stringent condition, and we must completely rule out the existence of stray
oscillators.

To precisely control the number of stray oscillators, we define a set of
indices for oscillators whose phases lie outside of a sector of half-angle
$\phi$ (centered about the all-in-phase state):

$C_{\phi}=\left\\{k:\cos(\theta_{k})\leq\cos(\phi),\,\,1\leq k\leq n\right\\}$
(8)

for any angle $0\leq\phi\leq\pi$ (see Figure 1). If we can prove that
$C_{\pi/2}$ is empty, then we know that all the phases in the equilibrium
state lie strictly inside a half-circle. That would give us what we want,
because by a basic theorem for the homogeneous Kuramoto model, the only stable
equilibrium $\theta$ with all its phases confined to a half-circle is the all-
in-phase state. jadbabaie2004stability ; dorfler2014synchronization  In terms
of bounds, since $|C_{\pi/2}|$ is integer-valued, if we can show that
$|C_{\pi/2}|<1$ then we know that $C_{\pi/2}$ is the empty set.

$1$$2$$3$$5$$6$$7$$8$$\phi$ Figure 1: When viewing the phases of the
oscillators on the unit circle, the set $C_{\phi}$ contains the indices of
stray oscillators whose phases have cosines less than or equal to
$\cos(\phi)$. In the example shown here, we have $8$ oscillators, and only the
oscillator with phase $\theta_{3}$ has strayed outside the sector of half-
angle $\phi$. Hence $C_{\phi}=\left\\{3\right\\}$.

From Lemma 2 and $\|\Delta_{A}q_{\theta}\|^{2}\leq n\|\Delta_{A}\|^{2}$, we
find that

$n\|\Delta_{A}\|^{2}\geq n^{2}p^{2}\rho_{1}^{2}\sum_{j\in
C_{\phi}}\sin^{2}(\theta_{j})\geq
n^{2}p^{2}\rho_{1}^{2}|C_{\phi}|\sin^{2}(\phi).$ (9)

Therefore, by plugging in $\phi=\pi/2$, we see that
$|C_{\pi/2}|\leq\|\Delta_{A}\|^{2}/(np^{2}\rho_{1}^{2})$. Thus, if
$\|\Delta_{A}\|^{2}<np^{2}\rho_{1}^{2}$ then $C_{\pi/2}$ must be the empty set
and the network is globally synchronizing.

Unfortunately, this kind of reasoning is not sufficient to prove global
synchrony for graphs of interest to us here. For example, for an Erdős–Rényi
random graph, we know that $\|\Delta_{A}\|^{2}\approx 4p(1-p)n$ with high
probability for large $n$ (see Section VI). So the upper bound on
$|C_{\pi/2}|$ is approximately $4(1-p)/(p\rho_{1}^{2})$, which for $p<1/2$ is
certainly not good enough to conclude that $C_{\pi/2}$ is empty. Instead, we
must further improve our bounds on $|C_{\pi/2}|$ by using a recursive
refinement strategy that we refer to as an “amplification" argument (see
Section V).

##  IV Bounds on the number of edges and sizes of sets in graphs

The precise amplification argument that we use requires bounds on the number
of edges and sizes of vertex sets of a graph expressed in terms of the
spectral norms of $\Delta_{A}$ and $\Delta_{L}$. It is worth noting that these
bounds hold for both deterministic and random graphs. For a vertex set $C$ of
a graph $G$, we denote the characteristic vector by $v_{C}$, i.e.,
$(v_{C})_{j}=1$ if $j\in C$ and $(v_{C})_{j}=0$ if $j\not\in C$. We use
$v_{C}^{\top}$ to denote the vector transpose of $v_{C}$. We write $|C|$ to be
the number of vertices in $C$ and denote the number of edges in $G$ between
two vertex sets $C$ and $C^{\prime}$ as $E_{C,C^{\prime}}$. For Erdős–Rényi
graphs, one expects to have $E_{C,C^{\prime}}\approx p|C||C^{\prime}|$.
However, for our argument to work, expectations are not adequate; instead we
need to have bounds on the difference between $E_{C,C^{\prime}}$ and
$p|C||C^{\prime}|$. The results in this section are proved by classical
techniques and closely related bounds are well known. We give the proofs of
the precise inequalities that we need so that the paper is self-contained.

We first show that for any vertex set $C$, the number of edges connecting a
vertex in $C$ to another vertex in $C$ deviates from $p|C|^{2}$ by at most
$\|\Delta_{A}\||C|$, for any $0\leq p\leq 1$.

######  Lemma 3.

Let $G$ be a graph of size $n$ with vertex set $V_{G}$ and adjacency matrix
$A$. For any $0\leq p\leq 1$, we have

$\max_{C\subseteq
V_{G}}\frac{\left|E_{C,C}-p|C|^{2}\right|}{|C|}\leq\|\Delta_{A}\|,$

where $\Delta_{A}$ is defined in (2).

###### Proof.

Let $v_{C}$ be the characteristic vector for $C$. By the min-max theorem,
Golub  we have $\max_{C\subseteq
V_{G}}(v_{C}^{\top}\Delta_{A}v_{C})/(v_{C}^{\top}v_{C})\leq\|\Delta_{A}\|$.
Finally, we note that $\Delta_{A}=A-pJ_{n}$, $v_{C}^{\top}v_{C}=|C|$,
$v_{C}^{\top}J_{n}v_{C}=|C|^{2}$, and $v_{C}^{\top}Av_{C}=E_{C,C}$. ∎

Lemma 3 controls the number of edges connecting a set of vertices. The
following result controls the number of edges leaving a vertex set. We denote
the vertices of $G$ that are not in $C_{1}$ by $V_{G}\setminus C_{1}$.

######  Lemma 4.

Let $G$ be a graph of size $n$ with vertex set $V_{G}$ and graph Laplacian
$L$. For any $0\leq p\leq 1$, we have

$\max_{C_{1}\subseteq V_{G},C_{2}=V_{G}\setminus
C_{1}}\frac{\left|E_{C_{1},C_{2}}-p|C_{1}||C_{2}|\rule{0.0pt}{8.61108pt}\right|}{|C_{1}||C_{2}|}\leq\frac{\|\Delta_{L}\|}{n},$

where $\Delta_{L}$ is defined in (2).

###### Proof.

Let $v_{C_{1}}$ and $v_{C_{2}}$ be the characteristic vectors for the sets
$C_{1}$ and $C_{2}$, respectively, and
$w=(|C_{2}|/n)v_{C_{1}}-(|C_{1}|/n)v_{C_{2}}$. By the min-max theorem, we have

$\max_{C_{1}\subseteq V_{G},C_{2}=V_{G}\setminus
C_{1}}\\!\\!\frac{w^{\top}\Delta_{L}w}{w^{\top}w}\leq\|\Delta_{L}\|.$

Finally, we note that $\Delta_{L}=L-pJ_{n}+npI_{n}$,
$w^{\top}w=\frac{|C_{2}|^{2}|C_{1}|}{n^{2}}+\frac{|C_{2}||C_{1}|^{2}}{n^{2}}=\frac{|C_{2}||C_{1}|}{n}$
as $|C_{1}|+|C_{2}|=n$, $w^{\top}(-pJ_{n}+npI_{n})w=p|C_{1}||C_{2}|$, and
$w^{\top}Lw=E_{C_{1},C_{2}}$. ∎

When a bound on $\|\Delta_{L}\|$ is available, Lemma 4 can be used to ensure
that $G$ is connected. In particular, Lemma 4 tells us that a graph of size
$n$ is connected if $\|\Delta_{L}\|<np$ for some $0\leq p\leq 1$.

Since $0\leq E_{C_{1},C_{2}}\leq|C_{1}||C_{2}|$, we know that
$\left|E_{C_{1},C_{2}}-p|C_{1}||C_{2}|\right|\leq\max\\{p,1-p\\}|C_{1}||C_{2}|$.
Therefore, Lemma 4 is only a useful bound when $\|\Delta_{L}\|\ll np$. We can
take Lemma 4 a step further and bound the number of edges between _any_ two
sets of vertices of $G$ using $\|\Delta_{L}\|$. We denote the union of the
vertex sets $C_{1}$ and $C_{2}$ by $C_{1}\sqcup C_{2}$.

######  Lemma 5.

Let $G$ be a graph of size $n$ with vertex set $V_{G}$ and graph Laplacian
matrix $L$. For any $0\leq p\leq 1$, we have

$\max_{\begin{subarray}{c}C_{1}\subseteq V_{G},C_{2}\subseteq V_{G}\setminus
C_{1},\\\ C_{3}=V_{G}\setminus(C_{1}\sqcup
C_{2})\end{subarray}}\frac{\left|E_{C_{1},C_{2}}-p|C_{1}||C_{2}|\rule{0.0pt}{8.61108pt}\right|}{|C_{1}||C_{2}|+|C_{1}||C_{3}|+|C_{2}||C_{3}|}\leq\frac{\|\Delta_{L}\|}{n},$

where $\Delta_{L}$ is defined in (2).

###### Proof.

For any partitioning of the vertices of $G$ into three sets $C_{1}$, $C_{2}$,
and $C_{3}$, we have $2E_{C_{1},C_{2}}=E_{C_{1},C_{2}\sqcup
C_{3}}+E_{C_{2},C_{1}\sqcup C_{3}}-E_{C_{3},C_{1}\sqcup C_{2}}$. By Lemma 4,
$E_{C_{1},C_{2}\sqcup C_{3}}$ is bounded between
$p(|C_{1}||C_{2}|+|C_{1}||C_{3}|)\pm\|\Delta_{L}\||C_{1}|(|C_{2}|+|C_{3}|)/n$,
$E_{C_{2},C_{1}\sqcup C_{3}}$ is bounded between
$p(|C_{2}||C_{1}|+|C_{2}||C_{3}|)\pm\|\Delta_{L}\||C_{2}|(|C_{1}|+|C_{3}|)/n$,
and $E_{C_{3},C_{1}\sqcup C_{2}}$ is bounded between
$p(|C_{3}||C_{1}|+|C_{3}||C_{2}|)\pm\|\Delta_{L}\||C_{3}|(|C_{1}|+|C_{2}|)/n$.
Hence, $E_{C_{1},C_{2}}$ deviates from $p|C_{1}||C_{2}|$ by less than
$\|\Delta_{L}\|(|C_{1}||C_{2}|+|C_{2}||C_{3}|+|C_{1}||C_{3}|)/(2n)$. ∎

Lemma 3 and Lemma 5 can be combined to obtain the following result.

######  Theorem 6.

Let $G$ be a graph of size $n$ with adjacency matrix $A$ and graph Laplacian
matrix $L$. Suppose that $C_{1}$, $C_{2}$, and $C_{3}$ is a partition of the
vertices of $G$ into three sets such that (i) $E_{C_{1},C_{3}}\leq\lambda
E_{C_{3},C_{3}}$ for some number $\lambda$ and (ii) $|C_{2}|<|C_{1}|$. Then,
for any $0\leq p\leq 1$, we have

$|C_{2}|+|C_{3}|\geq\left(\frac{n\left(p|C_{1}|-p\lambda|C_{3}|-\lambda\|\Delta_{A}\|\right)}{\|\Delta_{L}\||C_{1}|}-1\right)|C_{3}|,$

where $\Delta_{A}$ and $\Delta_{L}$ are defined in (2).

###### Proof.

By Lemma 3, $E_{C_{3},C_{3}}$ deviates from $p|C_{3}|^{2}$ by less than
$\|\Delta_{A}\||C_{3}|$ and, by Lemma 5, $E_{C_{1},C_{3}}$ deviates from
$p|C_{1}||C_{3}|$ by less than
$\|\Delta_{L}\|(|C_{1}||C_{2}|+|C_{2}||C_{3}|+|C_{3}||C_{1}|)/n$. Since
$E_{C_{1},C_{3}}\leq\lambda E_{C_{3},C_{3}}$, we must have

$\displaystyle p|C_{1}||C_{3}|-$
$\displaystyle\frac{\|\Delta_{L}\|}{n}(|C_{1}||C_{2}|+|C_{2}||C_{3}|+|C_{3}||C_{1}|)$
$\displaystyle\qquad\qquad\leq\lambda\left(p|C_{3}|^{2}+\|\Delta_{A}\||C_{3}|\right).$

By rearranging this inequality, we find that

$|C_{2}|+|C_{3}|\geq\left(\frac{n\left(p|C_{1}|-p\lambda|C_{3}|-\lambda\|\Delta_{A}\|\right)}{\|\Delta_{L}\||C_{1}|}-\frac{|C_{2}|}{|C_{1}|}\right)|C_{3}|.$

The result follows as $|C_{2}|<|C_{1}|$. ∎

##  V Amplification argument

We are finally ready for our amplification argument, which is a way to improve
the bounds on $|C_{\pi/2}|$ from (9). We first write down a new inequality
that holds for any stable equilibrium. We write it down using a kernel
function $K$ that later allows us to improve our argument with the aid of a
computer (see Section VI.1).

######  Lemma 7.

Let $G$ be a graph with adjacency matrix $A$. Let $K$ be a kernel function
defined on $[-\pi,\pi)\times[-\pi,\pi)$, given by

$K(\alpha,\beta)=\begin{cases}\sin(|\alpha|-|\beta|),&|\alpha|,|\beta|\leq\frac{\pi}{2},\\\
-\cos(\alpha),&|\alpha|\leq\frac{\pi}{2},|\beta|>\frac{\pi}{2},\\\
1,&|\alpha|>\frac{\pi}{2}.\end{cases}$

Then any stable equilibrium $\theta$ of (1) must satisfy
$\sum_{j}A_{jk}K(\theta_{j},\theta_{k})\geq 0$ for any $1\leq k\leq n$.

###### Proof.

Let $k$ be an integer between $1$ and $n$. Due to periodicity, we may assume
that the phases, $\theta_{j}$, take values in the interval $[-\pi,\pi)$. We
split the proof into three cases depending on the value of $\theta_{k}$.

Case 1: $0\leq\theta_{k}\leq\pi/2$. We first show that
$\sin(\theta_{j}-\theta_{k})\leq K(\theta_{j},\theta_{k})$ for all $j$ by
checking the three possible subcases: (i) If $0\leq\theta_{j}\leq\pi/2$ then
$\sin(\theta_{j}-\theta_{k})=\sin(|\theta_{j}|-|\theta_{k}|)=K(\theta_{j},\theta_{k})$;
(ii) If $|\theta_{j}|>\pi/2$ then $\sin(\theta_{j}-\theta_{k})\leq
1=K(\theta_{j},\theta_{k})$; and (iii) If $-\pi/2\leq\theta_{j}<0$ then
$\sin(\theta_{j}-\theta_{k})=\sin(|\theta_{j}|-|\theta_{k}|-2|\theta_{j}|)\leq\sin(|\theta_{j}|-|\theta_{k}|)=K(\theta_{j},\theta_{k})$,
where the inequality holds because
$-\pi/2\leq|\theta_{j}|-|\theta_{k}|\leq\pi/2$ and $0\leq
2|\theta_{j}|\leq\pi$. The inequality follows from the equilibrium condition
$\sum_{j}A_{jk}\sin(\theta_{j}-\theta_{k})=0$.

Case 2: $-\pi/2\leq\theta_{k}<0$. We first show that
$\sin(\theta_{j}-\theta_{k})\geq-K(\theta_{j},\theta_{k})$ for all $j$ by
checking the three possible subcases: (i) If $0\leq\theta_{j}\leq\pi/2$ then
$\sin(\theta_{j}-\theta_{k})=\sin(|\theta_{j}|-|\theta_{k}|+2|\theta_{k}|)\geq-\sin(|\theta_{j}|-|\theta_{k}|)=-K(\theta_{j},\theta_{k})$,
where the inequality holds because
$-\pi/2\leq|\theta_{j}|-|\theta_{k}|\leq\pi/2$ and $0\leq
2|\theta_{k}|\leq\pi$; (ii) If $|\theta_{j}|>\pi/2$ then
$\sin(\theta_{j}-\theta_{k})\geq-1=-K(\theta_{j},\theta_{k})$; and (iii) If
$-\pi/2\leq\theta_{j}<0$ then
$\sin(\theta_{j}-\theta_{k})=\sin(-|\theta_{j}|+|\theta_{k}|)=-\sin(|\theta_{j}|-|\theta_{k}|)=-K(\theta_{j},\theta_{k})$.
The inequality follows from the equilibrium condition
$\sum_{j}A_{jk}\sin(\theta_{j}-\theta_{k})=0$.

Case 3: $|\theta_{k}|>\pi/2$. From the fact that $\theta$ is an equilibrium,
we have $\sum_{j}A_{jk}\sin(\theta_{k}-\theta_{j})=0$. Moreover,
$\sum_{j}A_{jk}\cos(\theta_{k}-\theta_{j})\geq 0$, because the diagonal
entries of the Hessian matrix must be nonnegative at a stable equilbrium (see
(2.3) of Ling et al. ling2018landscape ). By a trigonometric identity, we find
that
$0=\sum_{k}A_{jk}\sin(\theta_{k}-\theta_{j})=\sin(\theta_{k})\sum_{j}A_{jk}\cos(\theta_{j})+\cos(\theta_{k})\sum_{j}A_{jk}\sin(\theta_{j})$
and hence,

$\sum_{j}A_{jk}\sin(\theta_{j})=\frac{\sin(\theta_{k})}{\cos(\theta_{k})}\sum_{j}A_{jk}\cos(\theta_{j}),$
(10)

where we note that $\cos(\theta_{k})\neq 0$ as $\theta_{k}\neq\pm\pi/2$.
Moreover, from another trigonometric identity, we have
$0\leq\sum_{j}A_{jk}\cos(\theta_{k}-\theta_{j})=\cos(\theta_{k})\sum_{j}A_{jk}\cos(\theta_{j})+\sin(\theta_{k})\sum_{j}A_{jk}\sin(\theta_{j})$,
which together with (10) gives

$\left(\cos(\theta_{k})+\frac{\sin^{2}(\theta_{k})}{\cos(\theta_{k})}\right)\sum_{j}A_{jk}\cos(\theta_{j})\geq
0.$

Multiplying this inequality by $\cos(\theta_{k})$ (note that
$\cos(\theta_{k})<0$ as $|\theta_{k}|>\pi/2$) and using
$\cos^{2}(\theta_{k})+\sin^{2}(\theta_{k})=1$, we conclude that
$\sum_{j}A_{jk}\cos(\theta_{j})\leq 0$. To reach the desired inequality in the
statement of the lemma, we now check the two possible subcases: (i) If
$|\theta_{j}|\leq\pi/2$ then $\cos(\theta_{j})=-K(\theta_{j},\theta_{k})$ and
(ii) If $|\theta_{j}|>\pi/2$ then
$\cos(\theta_{j})\geq-1=-K(\theta_{j},\theta_{k})$. This means that
$0\geq\sum_{j}A_{jk}\cos(\theta_{j})\geq-\sum_{j}A_{jk}K(\theta_{j},\theta_{k})$
as desired. ∎

In preliminary work we have found indications that Lemma 7 can be used to
prove stronger results than those we report below; see Section VI.1 for
further discussion. But we are not sure yet how to write down an argument that
uses the full strength of Lemma 7 in a readily digestible fashion. So for now
we use the following simplified lemma instead. It is a key step in our
amplification argument. Ultimately it leads to a global synchronization
theorem whose proof is comparatively straightforward.

######  Lemma 8.

Let $G$ be a graph and $\theta$ a stable equilibrium of (1), and let
$0<\alpha<\beta<\pi/2$. We have

$E_{C_{\beta},C_{\beta}}\geq\sin(\beta-\alpha)E_{C_{\beta},\overline{C_{\alpha}}},$

where $C_{\alpha}$ and $C_{\beta}$ are defined in (8). Here,
$\overline{C_{\alpha}}=V_{G}\setminus C_{\alpha}$.

###### Proof.

This follows from the previous lemma by carefully bounding
$K(\theta_{j},\theta_{k})$ when $k\in C_{\beta}$ (which implies that
$|\theta_{k}|>\beta$). We check the three possible subcases: (i) If $j\in
C_{\beta}$ then we might have $|\theta_{j}|>\pi/2$ so the best we can say is
$K(\theta_{j},\theta_{k})\leq 1$; (ii) If $j\in C_{\alpha}\setminus C_{\beta}$
(which implies that $|\theta_{j}|\leq\pi/2$) then either $|\theta_{k}|>\pi/2$
so that $K(\theta_{j},\theta_{k})=-\cos(\theta_{j})\leq 0$ or
$\beta<|\theta_{k}|\leq\pi/2$ so that
$K(\theta_{j},\theta_{k})=\sin(|\theta_{j}|-|\theta_{k}|)\leq 0$ as
$|\theta_{j}|\leq|\theta_{k}|$. Either way, we have
$K(\theta_{j},\theta_{k})\leq 0$ when $j\in C_{\alpha}\setminus C_{\beta}$;
and (iii) If $j\not\in C_{\alpha}$ (which implies that $|\theta_{j}|<\alpha$)
then either $|\theta_{k}|>\pi/2$ so that
$K(\theta_{j},\theta_{k})=-\cos(\theta_{j})\leq-\cos(\alpha)=-\sin(\pi/2-\alpha)\leq-\sin(\beta-\alpha)$
or $\beta<|\theta_{k}|\leq\pi/2$ so that
$K(\theta_{j},\theta_{k})=\sin(|\theta_{j}|-|\theta_{k}|)\leq-\sin(\beta-\alpha)$.
Either way, $K(\theta_{j},\theta_{k})\leq-\sin(\beta-\alpha)$ when $j\not\in
C_{\alpha}$. We conclude that

$K(\theta_{j},\theta_{k})\leq\begin{cases}1,&j\in C_{\beta},\\\ 0,&j\in
C_{\alpha}\setminus C_{\beta},\\\ -\sin(\beta-\alpha),&j\not\in
C_{\alpha}\end{cases}$

and hence, by Lemma 7, we have

$0\leq\\!\sum_{k\in
C_{\beta}}\\!\sum_{j}A_{jk}K(\theta_{j},\theta_{k})\leq\\!\\!\underbrace{\sum_{j,k\in
C_{\beta}}\\!\\!A_{jk}}_{=E_{C_{\beta},C_{\beta}}}-\sin(\beta-\alpha)\\!\\!\underbrace{\sum_{j\not\in
C_{\alpha},k\in
C_{\beta}}\\!\\!A_{jk}}_{=E_{C_{\beta},\overline{C_{\alpha}}}}$

as desired. ∎

We now show that if $\theta$ is a stable equilibrium and $|C_{\alpha}|$ is
small, then $|C_{\beta}|$ must be even smaller for $0<\alpha<\beta<\pi/2$;
otherwise, the oscillators in the set $C_{\alpha}\setminus C_{\beta}$ would
destabilize the equilibrium (see Figure 2). Since we know that
$|C_{\beta}|\leq|C_{\alpha}|$, the next bound is useful when
$\|\Delta_{L}\|/(np)>1/4$.

$1$$2$$3$$5$$6$$7$$8$$\alpha$$\beta$ Figure 2: Here,
$C_{\alpha}=\left\\{3,5,6,8\right\\}$ and $C_{\beta}=\left\\{3,5\right\\}$. We
illustrate a hypothetical equilibrium such that $C_{\pi/2}$ is empty and so
must be unstable; however, it might be that (9) is not tight enough to show
that $|C_{\pi/2}|<1$. To still conclude that $C_{\pi/2}$ is empty, we first
show in Lemma 8 that for an equilibrium to be stable there must be enough
edges coupling the oscillators in $C_{\beta}$ together, compared to those
between $C_{\beta}$ and $\overline{C_{\alpha}}$. For the illustrated
equilibrium, we are comparing the number of internal edges between oscillators
$3$ and $5$ and the number of outgoing edges to oscillators $1,2$, and $7$.

######  Corollary 9.

Let $G$ be a graph of size $n$, $\theta$ a stable equilibrium of (1), and
$0<p\leq 1$. If for some $0<\alpha<\beta<\pi/2$ we have $|C_{\alpha}|\leq
n/2$, $|C_{\beta}|\leq 2\|\Delta_{A}\|/p$ and $\sin(\beta-\alpha)\geq
12\|\Delta_{A}\|/(np)$, then

$|C_{\beta}|\leq\left(\frac{np}{2\|\Delta_{L}\|}-1\right)^{-1}|C_{\alpha}|,$

where $\Delta_{A}$ and $\Delta_{L}$ are defined in (2) and $C_{\alpha}$ and
$C_{\beta}$ in (8).

###### Proof.

Let $\lambda=np/(12\|\Delta_{A}\|)$. By Lemma 8, we have
$E_{C_{\beta},\overline{C_{\alpha}}}\leq(1/\sin(\beta-\alpha))E_{C_{\beta},C_{\beta}}\leq\lambda
E_{C_{\beta},C_{\beta}}$. Hence, by Theorem 6 (with
$C_{1}=\overline{C_{\alpha}}$, $C_{2}=C_{\alpha}\setminus C_{\beta}$, and
$C_{3}=C_{\beta}$), we find that

$\displaystyle|C_{\alpha}|$
$\displaystyle\geq\left(\frac{n(p|\overline{C_{\alpha}}|-p\lambda|C_{\beta}|-\lambda\|\Delta_{A}\|)}{\|\Delta_{L}\||\overline{C_{\alpha}}|}\right)|C_{\beta}|$
$\displaystyle=\left(\frac{np}{\|\Delta_{L}\|}-\frac{n\lambda(p|C_{\beta}|+\|\Delta_{A}\|)}{\|\Delta_{L}\||\overline{C_{\alpha}}|}\right)|C_{\beta}|$
$\displaystyle\geq\left(\frac{np}{2\|\Delta_{L}\|}-1\right)|C_{\beta}|,$

where the last inequality holds if
$\lambda\leq\frac{\|\Delta_{L}\||\overline{C_{\alpha}}|}{n(p|C_{\beta}|+\|\Delta_{A}\|)}\left(\frac{np}{2\|\Delta_{L}\|}+1\right)$.
Since $|\overline{C_{\alpha}}|\geq n/2$ and $|C_{\beta}|\leq
2\|\Delta_{A}\|/p$, we find that $\lambda=np/(12\|\Delta_{A}\|)$ satisfies
this upper bound. ∎

Note that it is only possible to have an $\alpha$ and $\beta$ such that
$\sin(\beta-\alpha)\geq 12\|\Delta_{A}\|/(np)$ in Corollary 9 when
$\|\Delta_{A}\|/(np)<1/12$. Corollary 9 can be used in a recursive fashion to
improve the bound on $|C_{\pi/2}|$. Below, we start at $\alpha$ and
incrementally increase $\beta$ to conclude that $C_{\pi/2}$ is empty.

######  Lemma 10.

Let $G$ be a graph of size $n$, $\theta$ a stable equilibrium of (1), $0<p\leq
1$, $\|\Delta_{A}\|/(np)<1/12$, and $\|\Delta_{L}\|/(np)<1/4$. If for some
$\alpha<\pi/2$ we have (i) $|C_{\alpha}|<2\|\Delta_{A}\|/p$, and (ii)

$\frac{\pi/2-\alpha}{\sin^{-1}\\!\left(\frac{12\|\Delta_{A}\|}{np}\right)}>\frac{\log(n/6)}{\log\\!\left(\frac{np}{2\|\Delta_{L}\|}-1\right)}+1,$

then $C_{\pi/2}$ is empty and $\theta$ is the all-in-phase state.

###### Proof.

Set $\beta_{k}=\alpha+k\sin^{-1}\left(12\|\Delta_{A}\|/(np)\right)$. Since we
need $\beta_{k}<\pi/2$, we can take $0\leq k\leq M$, where

$M=\Bigg{\lceil}\frac{\pi/2-\alpha}{\sin^{-1}\left(\frac{12\|\Delta_{A}\|}{np}\right)}-1\Bigg{\rceil}.$

By Corollary 9 and the fact that $|C_{\alpha}|<2\|\Delta_{A}\|/p<n/6$ (which
ensures that $|C_{\alpha}|\leq n/2$), we have

$\displaystyle|C_{\beta_{M}}|$
$\displaystyle\leq\left(\frac{np}{2\|\Delta_{L}\|}-1\right)^{\\!-1}\\!\\!\\!\\!|C_{\beta_{M-1}}|$
$\displaystyle\qquad\qquad\vdots$
$\displaystyle\leq\left(\frac{np}{2\|\Delta_{L}\|}-1\right)^{\\!-M}\\!\\!\\!\\!|C_{\alpha}|.$

Since $|C_{\pi/2}|\leq|C_{\beta_{M}}|$ and $|C_{\alpha}|\leq n/6$, to conclude
that $|C_{\pi/2}|<1$ we need $(np/(2\|\Delta_{L}\|)-1)^{-M}n/6<1$, i.e.,
$M>\log(n/6)/\log(np/(2\|\Delta_{L}\|)-1)$ and the result follows. ∎

Finally, we summarize our findings. In particular, we can now provide a list
of technical criteria that ensure that the network is globally synchronizing.

######  Theorem 11.

Let $G$ be a graph with $n$ vertices and $0<p<1$. If (i)
$\|\Delta_{A}\|/(np)<1/12$, (ii) $\|\Delta_{L}\|/(np)<1/4$, and (iii)

$\frac{\pi/4}{\sin^{-1}\\!\left(\frac{12\|\Delta_{A}\|}{np}\right)}>\frac{\log(n/6)}{\log\\!\left(\frac{np}{2\|\Delta_{L}\|}-1\right)}+1,$

then the only stable equilibrium of (1) is the all-in-phase state.

###### Proof.

Let $\theta$ be any stable equilibrium of (1) on $G$. By combining (4) and
(7), we find that

$\rho_{1}^{6}-(1-2a)\rho_{1}^{4}+2a^{2}\rho_{1}^{2}-2a^{4}\geq 0,\qquad
a=\frac{\|\Delta_{A}\|}{np}.$ (11)

Since $a<1/12$ by (i) (which implies that $a<1/5$), (11) ensures that
$\rho_{1}^{2}>a$. Now select $\phi=\pi/4$. By (9), we find that
$|C_{\pi/4}|\leq 2\|\Delta_{A}\|^{2}/(np^{2}\rho_{1}^{2})<2\|\Delta_{A}\|/p$
as $\rho_{1}^{2}>\|\Delta_{A}\|/(np)$. By taking $\alpha=\pi/4$ in Lemma 10
and as (ii) holds, we find that $\theta$ is the all-in-phase state when (iii)
is satisfied. ∎

Theorem 11 shows that a graph’s global synchrony can be ensured by the size of
$\|\Delta_{A}\|$ and $\|\Delta_{L}\|$ alone. This is particularly beneficial
for random networks as $\|\Delta_{A}\|$ and $\|\Delta_{L}\|$ are quantities
that are studied in the random matrix literature.

##  VI The global synchrony of Erdős–Rényi graphs

For an Erdős–Rényi random graph with probability $0<p<1$, we have
ling2018landscape  (also, see Theorem 6.6.1 of Ref. Tropp ):

$\mathbb{P}\left[\|\Delta_{A}\|\geq
f(n,p)\right]<2n^{-1},\quad\mathbb{P}\left[\|\Delta_{L}\|\geq
2f(n,p)\right]<2n^{-1},$

where $f(n,p)=2\sqrt{n\log n\,p(1-p)}+4(\log n)/3$. Stronger probability
bounds on $\|\Delta_{A}\|$ are available in the work of Füredi and Komlós FK
and Vu Vu ; however, the bounds involve implicit constants that are difficult
to track down. Since we desire explicit, and not just asymptotic statements,
we start by not using these stronger probability bounds.

Now, let $p>0.256$ and $n=10^{6}$. One can verify that $f(n,p)/(np)<1/12$ and
$2f(n,p)/(np)<1/4$ so that with probability $>0.999996$, (i) and (ii) in
Theorem 11 hold. Moreover, one can also check that

$\frac{\pi/4}{\sin^{-1}\\!\left(\frac{12f(n,p)}{np}\right)}>\frac{\log(n/6)}{\log\\!\left(\frac{np}{4f(n,p)}-1\right)}+1.$
(12)

Therefore, by Theorem 11, an Erdős–Rényi graph with $p>0.256$ and $n=10^{6}$
is globally synchronizing with probability $>0.999996$. For $n=10^{7}$, we
find that $p>0.0474$ suffices.

To ensure that (12) holds as $n\rightarrow\infty$, we see that the left hand
side of (12) must grow at least as fast as $\log(n)$. By taking
$p=c\log^{\gamma}(n)/n$ for some $c>0$ and $\gamma>1$, we see that $f(n,p)$
shrinks like $\log^{1/2-\gamma/2}(n)$. Therefore, we need $\gamma>3$, i.e.,

$p\gg\log^{3}(n)/n$

for this argument to guarantee global synchrony. But as we mentioned, even
stronger asymptotic probability bounds are available FeigeOfek  on
$\|\Delta_{A}\|$ and $\|\Delta_{L}\|$, where $f(n,p)=O(\sqrt{np(1-p)})$. With
these stronger probability bounds, we find that

$p\gg\log^{2}(n)/n$

as $n\rightarrow\infty$ is sufficient to conclude global synchrony of
Erdős–Rényi graphs.

###  VI.1 Optimizing our bounds using a computer

For a given $n$, one can significantly improve the range of $p$ for which the
corresponding Erdős–Rényi graph is globally synchronizing by using a computer
(see Table 1). Our computer program can be turned into a proof and thus for
$p$ above the thresholds in Table 1, the Erdős–Rényi networks are globally
synchronizing with probability $>1-4/n$. However, writing the proofs down is
unwieldy since the program works with bounds on $|C_{\phi}|$ for a thousand
different values of $\phi$ and iteratively refines those bounds a hundred
thousand times over.

By starting with $\rho_{1}=0$ and $\rho_{2}=0$, one can alternate between (4)
and (7)—in an iterative fashion—to obtain a lower bound on $\rho_{1}$. The
lower bound on $\rho_{1}$ can be substituted in (9) to give initial upper
bounds on $|C_{\phi}|$ for $0\leq\phi\leq\pi/2$. One can then use Corollary 9
to progressively improve the bounds on $|C_{\phi}|$ for $0\leq\phi\leq\pi/2$.
To do so, one selects $0<\alpha<\beta<\pi/2$ and attempts to apply Corollary
9. If the application of Corollary 9 is successful, then one also has
$|C_{\phi}|\leq|C_{\beta}|$ for $\beta\leq\phi\leq\pi/2$. Since $|C_{\phi}|$
is integer-valued, any upper bound that is $<1$ implies that $C_{\phi}$ is
empty. We repeat this procedure a hundred thousand times to refine the upper
bounds on $|C_{\phi}|$ for $0\leq\phi\leq\pi/2$. If at any point we have
$|C_{\pi/2}|<1$, then we conclude that the Erdős–Rényi graph is globally
synchronizing with probability $>1-4/n$. In Table 1, we used the explicit
value of $f(n,p)=2\sqrt{n\log n\,p(1-p)}+4(\log n)/3$ to bound the spectral
norms of $\Delta_{A}$ and $\Delta_{L}$.

$n$ | $10^{4}$ | $10^{5}$ | $10^{6}$ | $10^{7}$
---|---|---|---|---
$p$ |  $>0.33237$ |  $>0.07168$ |  $>0.01117$ |  $>0.00157$
Table 1: The values of $p$ in the Erdős–Rényi random graph model for which we
can prove global synchrony for $n=10^{4},10^{5},10^{6}$, and $10^{7}$ with
probability $>1-4/n$. We used a computer to recursively apply inequalities in
our paper to obtain refined bounds on $|C_{\pi/2}|$. We include this table to
demonstrate that our results are meaningful for Erdős–Rényi graphs of finite,
practical size. It is possible that these lower bounds on $p$ can be improved
by careful optimizations.

There are several further improvements to our computer program that we tried:
(1) Using stronger probability bounds FK ; Vu  for $\|\Delta_{A}\|$; (2) Using
Lemma 7 instead of Lemma 8; and (3) Doing additional optimizations to improve
the upper bounds for $|C_{\phi}|$. For example, by selecting triples
$0<\alpha<\beta_{1}<\beta_{2}<\pi/2$ and proving a generalization of Corollary
9, we get bounds for $|C_{\beta_{1}}|$ in terms of $|C_{\alpha}|$ and
$|C_{\beta_{2}}|$ and bounds for $|C_{\beta_{2}}|$ in terms of $|C_{\alpha}|$
and $|C_{\beta_{1}}|$. There are similar generalizations for more than three
angles. For example, when $n=10^{20}$, by using Lemma 8 we can only show that
$p>1.58\times 10^{-15}$ guarantees that an Erdős–Rényi graph is globally
synchronizing with high probability, but with these extra improvements we find
that $p>3.50\times 10^{-16}$ suffices. These improvements also provide good
evidence—but not a proof—that Erdős–Rényi networks with $p\gg\log(n)/n$
globally synchronize with high probability as $n\rightarrow\infty$.

##  VII Discussion

We have demonstrated how spectral properties of a graph’s adjacency and graph
Laplacian matrix can be used to understand the global synchrony of a Kuramoto
model with identical oscillators coupled according to a network. For
Erdős–Rényi graphs, we prove that $p\gg\log^{2}(n)/n$ is sufficient to ensure
global synchrony with high probability as $n\rightarrow\infty$. As conjectured
by Ling, Xu, and Bandeira, ling2018landscape  we also believe that the global
synchrony threshold is close to the connectivity threshold of
$p\sim\log(n)/n$. With the aid of a computer and Lemma 7, we have convincing
evidence that Erdős–Rényi networks with $p\gg\log(n)/n$ are globally
synchronizing with high probability as $n\rightarrow\infty$ and it is a future
challenge to write down a formal proof. While Section VI focuses on
Erdős–Rényi graphs, most of our analysis applies to any network and we hope
that it can deliver intriguing results for other random graph models.

###### Acknowledgements.

Research supported by Simons Foundation Grant 713557 to M. K., NSF Grants No.
DMS-1513179 and No. CCF-1522054 to S. H. S., and NSF Grants No. DMS-1818757,
No. DMS-1952757, and No. DMS-2045646 to A. T. We thank Lionel Levine and
Mikael de la Salle on MathOverFlow for references on bounding $\|\Delta_{A}\|$
and $\|\Delta_{L}\|$ for Erdős–Rényi graphs.

## Data Availability

The data that supports the findings of this study are available within the
article.

## References

## References

  * (1) A. T. Winfree, “Biological rhythms and the behavior of populations of coupled oscillators,” J. Theor. Biol. 16, 15 (1967).
  * (2) A. T. Winfree, The Geometry of Biological Time (Springer, 1980).
  * (3) Y. Kuramoto, Chemical Oscillations, Waves, and Turbulence (Springer, 1984).
  * (4) R. E. Mirollo and S. H. Strogatz, “Synchronization of pulse-coupled biological oscillators,” SIAM J. Appl. Math. 50, 1645 (1990).
  * (5) S. Watanabe and S. H. Strogatz, “Constants of motion for superconducting Josephson arrays,” Physica D 74, 197 (1994).
  * (6) A. Pikovsky, M. Rosenblum, and J. Kurths, Synchronization: A Universal Concept in Nonlinear Sciences (Cambridge University Press, 2003).
  * (7) S. Strogatz, Sync: The Emerging Science of Spontaneous Order (Hyperion, 2003).
  * (8) F. Dörfler and F. Bullo, “Synchronization in complex networks of phase oscillators: A survey,” Automatica 50, 1539 (2014).
  * (9) A. Pikovsky and M. Rosenblum, “Dynamics of globally coupled oscillators: Progress and perspectives,” Chaos 25, 097616 (2015).
  * (10) F. A. Rodrigues, T. K. DM. Peron, P. Ji, and J. Kurths, “The Kuramoto model in complex networks,” Phys. Rep. 610, 1 (2016).
  * (11) D. M. Abrams, L. M. Pecora, and A. E. Motter, “Introduction to Focus Issue: Patterns of network synchronization,” Chaos 26, 094601 (2016).
  * (12) S. Boccaletti, A. N. Pisarchik, C. I. Del Genio, and A. Amann, Synchronization: From Coupled Systems to Complex Networks (Cambridge University Press, 2018).
  * (13) M. H. Matheny, J. Emenheiser, W. Fon, A. Chapman, A. Salova, M. Rohden, J. Li, M. H. de Badyn, M. Pósfai, L. Duenas-Osorio et al., “Exotic states in a simple network of nanoelectromechanical oscillators,” Science 363, eaav7932 (2019).
  * (14) G. Csaba and W. Porod, “Coupled oscillators for computing: A review and perspective,” Appl. Phys. Rev. 7, 011302 (2020).
  * (15) C. W. Wu, “Graph coloring via synchronization of coupled oscillators,” IEEE Trans Circ. Syst. I: Fund. Theory Appl. 45, 974 (1998).
  * (16) A. Novikov and E. Benderskaya, “Oscillatory network based on Kuramoto model for image segmentation,” In Proc. 13th Inter. Conf. Para. Comput. Techn. 9251, 210 (Springer, 2015).
  * (17) S. Steinerberger, “Max-cut via Kuramoto-type oscillators,” arXiv:2102.04931 (2021).
  * (18) S. Ling, R. Xu, and A. S. Bandeira, “On the landscape of synchronization networks: A perspective from nonconvex optimization,” SIAM J. Optim. 29, 1807 (2019).
  * (19) R. Taylor, “There is no non-zero stable fixed point for dense networks in the homogeneous Kuramoto model,” J. Phys. A: Math. Theor. 45, 055102 (2012).
  * (20) J. Lu and S. Steinerberger, “Synchronization of Kuramoto oscillators in dense networks,” Nonlinearity 33, 5905 (2020).
  * (21) M. Kassabov, S. H. Strogatz, and A. Townsend, “Sufficiently dense Kuramoto networks are globally synchronizing,” Chaos 31, 073135 (2021).
  * (22) P. Erdős and A. Rényi.  “On the evolution of random graphs,” Publ. Math. Inst. Hung. Acad. Sci. 5, 1 (1960).
  * (23) A. Jadbabaie, N. Motee, and M. Barahona, “On the stability of the Kuramoto model of coupled nonlinear oscillators,” In Proc. 2004 Amer. Contr. Conf. 5, 4296 (2004).
  * (24) D. A. Wiley, S. H. Strogatz, and M. Girvan, “The size of the sync basin,” Chaos 16, 015103 (2006).
  * (25) Z. Füredi and J. Komlós, “The eigenvalues of random symmetric matrices,” Combinatorica 1, 233 (1981).
  * (26) V. H. Vu, “Spectral norm of random matrices,” Combinatorica 27, 721 (2007).
  * (27) M. Barahona and L. M. Pecora, “Synchronization in small-world systems,” Phys. Rev. Lett. 89 (2002).
  * (28) G. S. Medvedev, “Small-world networks of Kuramoto oscillators,” Physica D 266, 13 (2014).
  * (29) G. S. Medvedev and X. Tang, “Stability of twisted states in the Kuramoto model on Cayley and random graphs,”J. Nonlin. Sci. 25, 6 (2015).
  * (30) G. S. Medvedev and X. Tang, “The Kuramoto model on power law graphs: synchronization and contrast states,” J. Nonlin. Sci. 30, 2405 (2020).
  * (31) H. Chiba, G. S. Medvedev, and M. S. Mizuhara, “Bifurcations in the Kuramoto model on graphs,” Chaos 28, 073109 (2018).
  * (32) H. Daido, “Order function and macroscopic mutual entrainment in uniformly coupled limit-cycle oscillators,” Prog. Theor. Phys. 88, 1213 (1992).
  * (33) J. C. Perez and F. Ritort, “A moment-based approach to the dynamical solution of the Kuramoto model,” J. Phys. A: Math. Gen. 30, 8095 (1997).
  * (34) Y. Terada and Y. Y. Yamaguchi, “Linear response theory for coupled phase oscillators with general coupling functions,” J. Phys. A: Math. Gen. 53, 044001 (2020).
  * (35) G. H. Golub and C. F. Van Loan, Matrix Computations (John Hopkins University Press, 2013).
  * (36) J. A. Tropp, “An introduction to matrix concentration inequalities,” arXiv:1501.01571 (2015).
  * (37) U. Feige and E. Ofek, “Spectral techniques applied to sparse random graphs,” Random Structures & Algorithms 27, 251 (2005).