Emergence of synchronization in Kuramoto model with general digraph

Xiongtao Zhang ^{${\dagger}$ ,}^$\S$ and Tingting Zhu ^{${\ddagger}$ ,}^{$\S$ ,}^*

Abstract.

In this paper, we study the complete synchronization of the Kuramoto model with general network containing a spanning tree, when the initial phases are distributed in an open half circle. As lack of uniform coercivity in general digraph, in order to capture the dissipation structure on a general network, we apply the node decomposition criteria in [22] to yield a hierarchical structure, which leads to the hypo-coercivity. This drives the phase diameter into a small region after finite time in a large coupling regime, and the uniform boundedness of the diameter eventually leads to the emergence of exponentially fast synchronization.

Key words and phrases:

Synchronization, Kuramoto model, general digraph, spanning tree, hypo-coercivity

^† Center for Mathematical Sciences, Huazhong University of Science and Technology, Wuhan, China ([email protected])

^‡ School of Mathematics and Statistics, Huazhong University of Science and Technology, Wuhan, China ([email protected])

^§ The authors X. Zhang and T. Zhu contribute equally to the work.

^∗ Corresponding author.

The work of X. Zhang is supported by the National Natural Science Foundation of China (Grant No. 11801194).

1. Introduction

Emergent collective behaviors in complex systems are ubiquitous around the world, such as aggregation of bacteria, flocking of birds, synchronous flashing of fireflies and so forth [7, 8, 9, 27, 31, 32, 33, 34], in which self-propelled agents organize themselves into a particular motion via limited environmental information and simple rules. In order to study the driven mechanism of the emergence of collective behaviors, various dynamic models have been proposed in recent years such as Cucker-Smale model [6], Kuraomoto model [24], and Winfree model [34], etc.. These seminal models have received lots of attention and have been systematically studied due to their potential applications in biology and engineer, to name a few, modeling of cell and filament orientation, sensor networks, formation control of robots and unmanned aerial vehicles [25, 27, 28], etc.

In the present paper, we focus on the emergence of synchronization in Kuramoto model with general interaction network. The terminology synchronization represents the phenomena in which coupled oscillators adjust their rhythms through weak interaction [1, 29], and Kuramoto model is a classical model to study the emergence of synchronization. The emergent dynamics of the Kuramoto model has been extensively studied in literature [2, 3, 5, 13, 14, 16, 17, 18, 19, 23, 26, 30]. In our work, to fix the idea, we consider a digraph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ consisting of a finite set $\mathcal{V}=\{1,\ldots,N\}$ of vertices and a set $\mathcal{E}\subset\mathcal{V}\times\mathcal{V}$ of directed arcs. We assume that Kuramoto oscillators are located at vertices and interact with each other via the underlying network topology. For each vertex $i$ , we denote the set of its neighbors by $\mathcal{N}_{i}$ , which is the set of vertices that directly influence vertex $i$ . Now, let $\theta_{i}=\theta_{i}(t)$ be the phase of the Kuramoto oscillator at vertex $i$ , and define the $(0,1)$ -adjacency matrix $(\chi_{ij})$ as follows:

\chi_{ij}=\begin{cases}\displaystyle 1\quad\mbox{if the $j$th oscillator influences the $i$th oscillator},\\ \displaystyle 0\quad\mbox{otherwise}.\end{cases}

Then, the set of neighbors of $i$ -th oscillator is actually $\mathcal{N}_{i}:=\{j:\chi_{ij}>0\}$ . In this setting, the dynamics of phase $\theta_{i}$ is governed by the following ordinary differential system:

(1.1)

\begin{cases}\displaystyle\dot{\theta}_{i}(t)=\Omega_{i}+\kappa\underset{j\in\mathcal{N}_{i}}{\sum}\sin(\theta_{j}(t)-\theta_{i}(t)),\quad t>0,\quad i\in\mathcal{V},\\ \displaystyle\theta_{i}(0)=\theta_{i0}.\end{cases}

where $\kappa>0$ is the uniform coupling strength and $\Omega_{i}$ represents the intrinsic natural frequency of the $i$ th oscillator drawn from some distribution function $g=g(\Omega)$ . The motivation to consider general network is very natural, since the non all-to-all or non-symmetric interactions are common in the real world. For instance, flying birds can make a flocking cluster via the influence from several neighbors, while the sheep can form a group by following the leader. Therefore, study on the dynamical system on a general digraph is natural and important, and gradually attracts a lot of researchers from different areas. We refer the readers to the following references for more details of the background [4, 10, 11, 12, 15, 20, 21, 22].

There are few works [10, 12, 21] on the synchronization of the Kuramoto model on a general digraph in contrast with the complete graph. More precisely, the authors in [12] studied the generalized Kuramoto model with directed coupling topology, which is allowed to be non-symmetric. They showed the frequency synchronization when the initial phases of oscillators are distributed over the open half circle for a large class of coupling structure. However, they required any pair of oscillators have one common neighbor, so that the dissipation structure can be captured by the good property of sine function. In [21], the authors provided an asymptotic formation of phase-locked states for the ensemble of Kuramoto oscillators with a symmetric and connected network, when the initial configuration is distributed in a half circle. More precisely, they exploit the gradient structure and use energy method to derive complete synchronization whereas there is no information about the convergence rate. In literature [11], the authors studied a network structure containing a spanning tree (see Definition 2.1) on the collective behaviors of Kuramoto oscillators. Actually, they lift the Kuramoto model to second-order system such that the second-order formulation enjoys several similar mathematical structures as for the Cucker-Smale flocking model [10]. But this method only works when initial phases are confined in a quarter circle, since the cosine function becomes negative if $\frac{\pi}{2}<\theta<\pi$ .

So far, if the ensemble distributed in half circle, the dissipation structure of the Kuramoto model with general digragh is still unclear. The main difficulty is that, when considering the ensemble in half circle, there is no uniform coercive inequality to yield the dissipation, which is due to the non-all-to-all and non-symmetric structure. For example, the time derivative of the diameter may be zero in the general digraph. Therefore, we switch to construct the hypo-coercivity similar as in [22], which will help us to capture the dissipation structure. Comparing to [22] which deals with the Cucker-Smale model on a general digraph, the interactions in Kuramoto model lack the monotonic property since $\sin(x)$ is not monotonic in half circle. Therefore, we choose more delicate constructions and estimates of the convex combinations to fit the special structure of Kuramoto model, which eventually yields the following main theorem.

Theorem 1.1.

Suppose that the network topology $(\chi_{ij})$ contains a spanning tree, and let $\theta_{i}$ be a solution to (1.1). Moreover, assume that the initial data and the quantity $\eta$ satisfy

(1.2)

D(\theta(0))<\alpha<\gamma<\pi,\quad\eta>\max\left\{\frac{1}{\sin\gamma},\frac{2}{1-\frac{\alpha}{\gamma}}\right\},

where $\alpha,\gamma$ are constants. Then, we can find a sufficiently small positive constant $D^{\infty}<\min\left\{\alpha,\frac{\pi}{2}\right\}$ and a corresponding time $t_{*}$ such that

D(\theta(t))<D^{\infty},\qquad t\in(t_{*},+\infty),

provided the coupling strength $\kappa$ satisfies

(1.3)

\kappa>\left(1+\frac{(d+1)\alpha}{\alpha-D(\theta(0))}\right)\frac{(4c)^{d}\tilde{c}}{\beta^{d+1}D^{\infty}},

where $d$ is the number of general nodes which is smaller than $N$ (see Section 2) and

c=\frac{(2N+1)(\sum_{j=1}^{N-1}\eta^{j}A(2N,j)+1)\gamma}{\sin\gamma},\quad\tilde{c}=\frac{D(\Omega)(\sum_{j=1}^{N-1}\eta^{j}A(2N,j)+1)\gamma}{\sin\gamma}.

Note that Theorem 1.1 only shows the small and uniform boundedness of the ensemble, then we can directly apply the methods and results in [22] or [11] to yield the exponentially fast emergence of frequency synchronization. Therefore, we will only show the detailed proof of Theorem 1.1.

The rest of the paper is organized as follows. In Section 2, we recall some concepts on the network topology and provide an a priori local-in-time estimate about phase diameter of the ensemble. In Section 3, we consider a strong connected ensemble for which the initial phases are distributed in the open half circle. We show that the phase diameter is uniformly bounded and will be confined in a small region after some finite time in a large coupling regime. In Section 4, we study the general network with a spanning tree structure. In our framework, the coupling strength is sufficiently large and the initial data is confined in an open half circle. We use the inductive argument and show that the phase diameter of the whole digraph will concentrate into a small region of a quarter circle after some finite time, which yields the exponential emergence of synchronization. Section 5 is devoted to a brief summary.

2. Preliminaries

In this section, we introduce some basic concepts such as spanning tree and node decomposition of a general network (1.1). Then, we will provide some necessary notations and an a priori estimate that will be frequently used in later sections.

2.1. Spanning tree

Roughly speaking, spanning tree means we can find an oscillator which affects all the other oscillators directly or in-directly. In other words, a system without spanning tree can be separated into two parts without any interactions. Therefore, this is the most important structure for emergence of collective behavior on a general digraph.

More precisely, let the network topology be registered by the neighbor set $\mathcal{N}_{i}$ which consists of all neighbors of the $i$ th oscillator. Then, for a given set of $\{\mathcal{N}_{i}\}_{i=1}^{N}$ in system (1.1), we have the following definition.

Definition 2.1.

(1)

The Kuramoto digraph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ associated to (1.1) consists of a finite set $\mathcal{V}=\{1,2,\ldots,N\}$ of vertices, and a set $\mathcal{E}\subset\mathcal{V}\times\mathcal{V}$ of arcs with ordered pair $(j,i)\in\mathcal{E}$ if $j\in\mathcal{N}_{i}$ .
(2)

A path in $\mathcal{G}$ from $i_{1}$ to $i_{k}$ is a sequence $i_{1},i_{2},\ldots,i_{k}$ such that

$i_{s}\in\mathcal{N}_{i_{s+1}}\quad\mbox{for}\ 1\leq s\leq k-1.$

If there exists a path from $j$ to $i$ , then vertex $i$ is said to be reachable from vertex $j$ .
(3)

The Kuramoto digraph contains a spanning tree if we can find a vertex such that any other vertex of $\mathcal{G}$ is reachable from it.

According to the discussion of spanning tree in the beginning of this part, in order to guarantee the emergence of synchronization, we will always assume the existence of a spanning tree throughout the paper. Now we recall the concepts of root and general root in [22]. Let $l,k\in\mathbb{N}$ with $1\leq l\leq k\leq N$ , and let $C_{l,k}=(c_{l},c_{l+1},\ldots,c_{k})$ be a vector in $\mathbb{R}^{k-l+1}$ such that

c_{i}\geq 0,\quad l\leq i\leq k\quad\mbox{and}\quad\sum_{i=l}^{k}c_{i}=1.

For an ensembel of $N$ -oscillators with phase $\{\theta_{i}\}_{i=1}^{N}$ , we set $\mathcal{L}_{l}^{k}(C_{l,k})$ to be a convex combination of $\{\theta_{i}\}_{i=l}^{k}$ with the coefficient $C_{l,k}$ :

\mathcal{L}_{l}^{k}(C_{l,k}):=\sum_{i=l}^{k}c_{i}\theta_{i}.

Note that each $\theta_{i}$ is a convex combination of itself, and particularly $\theta_{N}=\mathcal{L}_{N}^{N}(1)$ and $\theta_{1}=\mathcal{L}_{1}^{1}(1)$ .

Definition 2.2.

(Root and general root)

(1)

We say $\theta_{k}$ is a root if it is not affected by the rest oscillators, i.e., $j\notin\mathcal{N}_{k}$ for any $j\in\{1,2,\ldots,N\}\setminus\{k\}$ .
(2)

We say $\mathcal{L}_{l}^{k}(C_{l,k})$ is a general root if $\mathcal{L}_{l}^{k}(C_{l,k})$ is not affected by the rest oscillators, i.e., for any $i\in\{l,l+1,\ldots,k\}$ and $j\in\{1,2,\ldots,N\}\setminus\{l,l+1,\ldots,k\}$ , we have $j\notin\mathcal{N}_{i}$ .

Lemma 2.1.

[22] The following assertions hold.

(1)

If the network contains a spanning tree, then there is at most one root.
(2)

Assume the network contains a spanning tree. If $\mathcal{L}_{k}^{N}(C_{k,N})$ is a general root, then $\mathcal{L}_{1}^{l}(C_{1,l})$ is not a general root for each $l\in\{1,2,\ldots,k-1\}$ .

2.2. Node decomposition

In this subsection, we will introduce the concept of maximum node. Then, we can introduce node decomposition to represent the whole graph $\mathcal{G}$ (or say vertex set $\mathcal{V}$ ) as a disjoint union of a sequence of nodes. The key point is that the node decomposition shows a hierarchical structure which allows us to apply the induction principle. Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ and $\mathcal{V}_{1}\subset\mathcal{V}$ , a subgraph $\mathcal{G}_{1}=(\mathcal{V}_{1},\mathcal{E}_{1})$ is the digraph with vertex set $\mathcal{V}_{1}$ and arc set $\mathcal{E}_{1}$ which consists of the arcs in $\mathcal{G}$ connecting agents in $\mathcal{V}_{1}$ . For convenience, for a given digraph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ , we will identify a subgraph $\mathcal{G}_{1}=(\mathcal{V}_{1},\mathcal{E}_{1})$ with its vertex set $\mathcal{V}_{1}$ . Now we first introduce the definition of nodes below.

Definition 2.3.

(Node) Let $\mathcal{G}$ be a digraph. A subset $\mathcal{G}_{1}$ of vertices is called a node if it is strongly connected, i.e., for any subset $\mathcal{G}_{2}$ of $\mathcal{G}_{1}$ , $\mathcal{G}_{2}$ is affected by $\mathcal{G}_{1}\setminus\mathcal{G}_{2}$ . Moreover, if $\mathcal{G}_{1}$ is not affected by $\mathcal{G}\setminus\mathcal{G}_{1}$ , we say $\mathcal{G}_{1}$ is a maximum node.

Notably, a node can be understood intuitively in a manner that a set of oscillators can be viewed as a ”large” oscillator. Next, we can exploit the concept of node to simplify the structure of the digraph, and this can help us to catch the attraction effect more clearly in the underlying network topology.

Lemma 2.2.

[22] Any digraph $\mathcal{G}$ contains at least one maximum node. A digraph $\mathcal{G}$ contains a unique maximum node if and only if $\mathcal{G}$ has a spanning tree.

Lemma 2.3.

[22](Node decomposition) Let $\mathcal{G}$ be any digraph. Then we can decompose $\mathcal{G}$ to be a union as $\mathcal{G}=\bigcup_{i=0}^{d}(\bigcup_{j=1}^{k_{i}}\mathcal{G}_{i}^{j})$ such that

(1)

$\mathcal{G}_{0}^{j}$ are the maximum nodes of $\mathcal{G}$ , where $1\leq j\leq k_{0}$ .
(2)

For any $p,q$ where $1\leq p\leq d$ and $1\leq q\leq k_{p}$ , $\mathcal{G}_{p}^{q}$ are the maximum nodes of $\mathcal{G}\setminus(\bigcup_{i=0}^{p-1}(\bigcup_{j=1}^{k_{i}}\mathcal{G}_{i}^{j}))$ .

Remark 2.1.

Lemma 2.3 shows a clear hierarchical structure on a general digraph. For the convenience of later analysis, we give some comments on important notations and properties to be used throughout the paper.

(1)

According to the definition of maximum node, we know $\mathcal{G}_{p}^{q}$ and $\mathcal{G}_{p}^{q^{\prime}}$ do not influence each other for $1\leq q\neq q^{\prime}\leq k_{p}$ . Actually, $\mathcal{G}_{p}^{q}$ will only be affected by $\mathcal{G}_{0}$ and $\mathcal{G}_{i}^{j}$ , where $1\leq i\leq p-1,\ 1\leq j\leq k_{i}$ . Therefore without loss of generality, we may assume $k_{i}=1$ for all $1\leq i\leq d$ in the proof of our main theorem (see Theorem 1.1). Thus, the decomposition can be expressed by

$\mathcal{G}=\bigcup_{i=0}^{d}\mathcal{G}_{i},$

where $\mathcal{G}_{p}$ is a maximum node of $\mathcal{G}\setminus(\bigcup_{i=0}^{p-1}\mathcal{G}_{i})$ .
(2)

Given an oscillator $\theta_{i}^{k+1}\in\mathcal{G}_{k+1}$ , we denote by $\bigcup_{j=0}^{k+1}\mathcal{N}_{i}^{k+1}(j)$ the set of neighbors of $\theta_{i}^{k+1}$ , where $\mathcal{N}_{i}^{k+1}(j)$ represents the neighbors of $\theta_{i}^{k+1}$ in $\mathcal{G}_{j}$ . The node decomposition and spanning tree structure in $\mathcal{G}$ guarantee that $\bigcup_{j=0}^{k}\mathcal{N}_{p}^{k+1}(j)\neq\emptyset$ .

2.3. Notations and local estimates

In this part, for simplicity, we introduce some notations, such as the extreme phase, phase diameter of $\mathcal{G}$ and the first $k+1$ nodes, frequency diameter, and cardinality of subdigraph:

	$\displaystyle\theta_{M}=\max_{1\leq k\leq N}\{\theta_{k}\}=\max_{0\leq i\leq d}\max_{1\leq j\leq N_{i}}\{\theta_{j}^{i}\},\quad\theta_{m}=\min_{1\leq k\leq N}\{\theta_{k}\}=\min_{0\leq i\leq d}\min_{1\leq j\leq N_{i}}\{\theta_{j}^{i}\},$
	$\displaystyle D(\theta)=\theta_{M}-\theta_{m},\quad D_{k}(\theta)=\max_{0\leq i\leq k}\max_{1\leq j\leq N_{i}}\{\theta_{j}^{i}\}-\min_{0\leq i\leq k}\min_{1\leq j\leq N_{i}}\{\theta_{j}^{i}\},$
	$\displaystyle\Omega_{M}=\max_{0\leq i\leq d}\max_{1\leq j\leq N_{i}}\{\Omega_{j}^{i}\},\quad\Omega_{m}=\min_{0\leq i\leq d}\min_{1\leq j\leq N_{i}}\{\Omega_{j}^{i}\},\quad D(\Omega)=\Omega_{M}-\Omega_{m},$
	$\displaystyle N_{i}=\|\mathcal{G}_{i}\|,\quad S_{k}=\sum_{i=0}^{k}N_{i},\quad 0\leq k\leq d,\quad\sum_{i=0}^{d}N_{i}=N.$

Finally, we provide an a priori local-in-time estimate on the phase diameter to finish the section, which shows the diameter of the ensemble remains less than $\pi$ in short time.

Lemma 2.4.

Let $\theta_{i}$ be a solution to system (1.1) and suppose the initial phase diameter satisfies $D(\theta(0))<\alpha<\gamma<\pi$ . Then there exists time $\bar{t}$ such that

(2.1)

D(\theta(t))<\alpha,\quad\forall\ t\in[0,\bar{t}),

where $\alpha,\gamma$ are constants and $\bar{t}=\frac{\alpha-D(\theta(0))}{D(\Omega)}$ .

Proof.

According to system (1.1), we have

\dot{\theta}_{M}=\Omega_{M}+\kappa\sum_{j\in\mathcal{N}_{M}}\sin(\theta_{j}-\theta_{M}),\qquad\dot{\theta}_{m}=\Omega_{m}+\kappa\sum_{j\in\mathcal{N}_{m}}\sin(\theta_{j}-\theta_{m}).

When the phase diameter is located in $[D(\theta(0)),\alpha]$ , it is obvious that

\sum_{j\in\mathcal{N}_{M}}\sin(\theta_{j}-\theta_{M})\leq 0,\quad\sum_{j\in\mathcal{N}_{m}}\sin(\theta_{j}-\theta_{m})\geq 0.

Hence, the dynamics of phase diameter of all nodes can be estimated as follows

(2.2)

\dot{D}(\theta(t))=\frac{d}{dt}(\theta_{M}-\theta_{m})\leq D(\Omega).

That is to say, the growth of phase diameter is less than the linear growth with slope $D(\Omega)$ if $D(\theta(t))\in[D(\theta(0)),\alpha]$ . Set $\bar{t}=\frac{\alpha-D(\theta(0))}{D(\Omega)}$ . Then according to (2.2), it can be seen that $D(\theta(t))$ is less than $\alpha$ before time $\bar{t}$ , i.e.,

D(\theta(t))<\alpha,\quad\forall\ t\in[0,\bar{t}),

∎

3. Strong connected case

We will first study the special case when the network is strongly connected. Without loss of generality, we denote the strong connected graph by $\mathcal{G}_{0}$ . According to Definition 2.3, Lemma 2.2 and Lemma 2.3, this means the network contains only one maximum node. Then, we will show the emergence of complete synchronization in the strong connected case. We now introduce an algorithm to construct a proper convex combination of the oscillators, which can involve the dissipation from interaction of general network. More precisely, the algorithm for $\mathcal{G}_{0}$ consists of the following three steps:

Step 1. For any given time $t$ , we reorder the oscillator indexes to make the oscillator phases from minimum to maximum. More specifically, by relabeling the agents at time $t$ , we set

(3.1)

\theta_{1}^{0}(t)\leq\theta_{2}^{0}(t)\leq\ldots\leq\theta_{N_{0}}^{0}(t).

In order to introduce the following steps, we first provide the process of iterations for $\bar{\mathcal{L}}_{k}^{N_{0}}(\bar{C}_{k,N_{0}})$ and $\underline{\mathcal{L}}_{1}^{l}(\underline{C}_{1,l})$ as follows:

$\bullet$ ( $\mathcal{A}_{1}$ ): If $\bar{\mathcal{L}}_{k}^{N_{0}}(\bar{C}_{k,N_{0}})$ is not a general root, then we construct

\bar{\mathcal{L}}_{k-1}^{N_{0}}(\bar{C}_{k-1,N_{0}})=\frac{\bar{a}_{k-1}\bar{\mathcal{L}}_{k}^{N_{0}}(\bar{C}_{k,N_{0}})+\theta^{0}_{k-1}}{\bar{a}_{k-1}+1}.

$\bullet$ ( $\mathcal{A}_{2}$ ): If $\underline{\mathcal{L}}_{1}^{l}(\underline{C}_{1,l})$ is not a general root, then we construct

\underline{\mathcal{L}}_{1}^{l+1}(\underline{C}_{1,l+1})=\frac{\underline{a}_{l+1}\underline{\mathcal{L}}_{1}^{l}(\underline{C}_{1,l})+\theta^{0}_{l+1}}{\underline{a}_{l+1}+1}

Step 2. According to the strong connectivity of $\mathcal{G}_{0}$ , we immediately know that $\bar{\mathcal{L}}_{1}^{N_{0}}(\bar{C}_{1,N_{0}})$ is a general root, and $\bar{\mathcal{L}}_{k}^{N_{0}}(\bar{C}_{k,N_{0}})$ is not a general root for $k>1$ . Therefore, we may start from $\theta^{0}_{N_{0}}$ and follow the process $\mathcal{A}_{1}$ to construct $\bar{\mathcal{L}}_{k}^{N_{0}}(\bar{C}_{k,N_{0}})$ until $k=1$ .

Step 3. Similarly, we know that $\underline{\mathcal{L}}_{1}^{N_{0}}(\underline{C}_{1,N_{0}})$ is a general root and $\underline{\mathcal{L}}_{1}^{l}(\underline{C}_{1,l})$ is not a general root for $l<N_{0}$ . Therefore, we may start from $\theta^{0}_{1}$ and follow the process $\mathcal{A}_{2}$ until $l=N_{0}$ .

We emphasize that the order of the oscillators will change along time $t$ , but at each time $t$ , the above algorithm works. For convenience, the algorithm from Step 1 to Step 3 will be referred as Algorithm $\mathcal{A}$ . Then, according to Algorithm $\mathcal{A}$ , we will show a monotone property about the function $\sin x$ , and provide a priori estimates which will be crucially used later in the proof of uniform boundness of phase diameter.

Lemma 3.1.

Let $\theta_{i}=\{\theta^{0}_{i}\}$ be a solution to system (1.1) with srong connected network $\mathcal{G}_{0}$ . Moreover at time $t$ , for the digraph $\mathcal{G}_{0}$ , we also assume that the oscillators are well-ordered as (3.1), the phase diameter and the quantity $\eta$ satisfiy the following condition:

D_{0}(\theta(t))<\gamma,\quad\eta>\max\left\{\frac{1}{\sin\gamma},\frac{2}{1-\frac{\alpha}{\gamma}}\right\},

where $\alpha,\gamma$ are given in the condition (1.2). Then at time $t$ , we have

\begin{cases}\displaystyle\sum_{i=n}^{N_{0}}(\eta^{i-n}\underset{j\leq i}{\min_{j\in\mathcal{N}^{0}_{i}(0)}}\sin(\theta_{j}^{0}-\theta_{i}^{0}))\leq\sin(\theta^{0}_{\bar{k}_{n}}-\theta^{0}_{N_{0}}),\quad\bar{k}_{n}=\min_{j\in\cup_{i=n}^{N_{0}}\mathcal{N}^{0}_{i}(0)}j,\quad 1\leq n\leq N_{0}.\\ \displaystyle\sum_{i=1}^{n}(\eta^{n-i}\underset{j\geq i}{\max_{j\in\mathcal{N}^{0}_{i}(0)}}\sin(\theta_{j}^{0}-\theta_{i}^{0}))\geq\sin(\theta^{0}_{\underline{k}_{n}}-\theta_{1}^{0}),\quad\underline{k}_{n}=\max_{j\in\cup_{i=1}^{n}\mathcal{N}^{0}_{i}(0)}j,\quad 1\leq n\leq N_{0}.\end{cases}

Proof.

We will only prove the first inequality, the second relation can be proved in a similar manner. In fact, if $N_{0}=1$ , i.e., $N_{0}$ is a (general) root, we are done. Now we consider the case $N_{0}\geq 2$ . Due to the strong connectivity of the digraph $\mathcal{G}_{0}$ , $\bar{\mathcal{L}}_{1}^{N_{0}}(\bar{C}_{1,N_{0}})$ is a general root while $\bar{\mathcal{L}}_{k}^{N_{0}}(\bar{C}_{k,N_{0}})$ is not a general root for $k>1$ .

For any given $n\in[1,N_{0}]$ , we have $\bar{k}_{n}=\min\limits_{j\in\cup_{i=n}^{N_{0}}\mathcal{N}^{0}_{i}(0)}j$ . Hence, there exists $l_{0}\in[n,N_{0}]$ such that $\bar{k}_{n}\in\mathcal{N}^{0}_{l_{0}}(0)$ due to the fact $\bar{k}_{n}\in\cup_{i=n}^{N_{0}}\mathcal{N}^{0}_{i}(0)$ . For $l_{0}$ , since $\bar{\mathcal{L}}_{l_{0}+1}^{N_{0}}(\bar{C}_{l_{0}+1,N_{0}})$ is not a general root, there exist $j_{0}\leq l_{0}$ and $l_{1}\in[l_{0}+1,N_{0}]$ such that $j_{0}\in\mathcal{N}^{0}_{l_{1}}(0)$ . For $l_{1}$ , as $\bar{\mathcal{L}}_{l_{1}+1}^{N_{0}}(\bar{C}_{l_{1}+1,N_{0}})$ is not a general root, there exist $j_{1}\leq l_{1}$ and $l_{2}\in[l_{1}+1,N_{0}]$ such that $j_{1}\in\mathcal{N}_{l_{2}}^{0}(0)$ . we repeat the process until find some $l_{p}=N_{0}$ and $j_{p-1}\leq l_{p-1}$ such that $j_{p-1}\in\mathcal{N}^{0}_{l_{p}}(0)=\mathcal{N}_{N_{0}}^{0}(0)$ . Obviously, we have

(3.2)	$\displaystyle\sum_{i=n}^{N_{0}}(\eta^{i-n}\underset{j\leq i}{\min_{j\in\mathcal{N}^{0}_{i}(0)}}\sin(\theta_{j}^{0}-\theta_{i}^{0}))$	$\displaystyle\leq\overbrace{\eta^{N_{0}-n}\sin(\theta_{j_{p-1}}^{0}-\theta^{0}_{N_{0}})+\eta^{l_{p-1}-n}\sin(\theta^{0}_{j_{p-2}}-\theta^{0}_{l_{p-1}})}^{\mathcal{I}_{1}}$
		$\displaystyle+\eta^{l_{p-2}-n}\sin(\theta^{0}_{j_{p-3}}-\theta^{0}_{l_{p-2}})+\cdots+\eta^{l_{2}-n}\sin(\theta^{0}_{j_{1}}-\theta^{0}_{l_{2}})$
	$\displaystyle+\eta^{l_{1}-n}\sin(\theta^{0}_{j_{0}}-\theta^{0}_{l_{1}})+\eta^{l_{0}-n}\sin(\theta^{0}_{\bar{k}_{n}}}-\theta^{0}_{l_{0}).\hfil$

where we have the following relations

j_{k}\leq l_{k},\quad l_{k}<l_{k+1},\quad k=0,1,\ldots,p-1.

In the following, we plan to add all the terms on the right-hand side of (3.2) together to yield the desired estimate. We only consider the case $\gamma>\frac{\pi}{2}$ , and the situation $\gamma\leq\frac{\pi}{2}$ can be similarly dealt with. We first deal with $\mathcal{I}_{1}$ in (3.2). If $\theta^{0}_{N}-\theta^{0}_{j_{p-1}}\leq\frac{\pi}{2}$ , we obtain that $0<\theta^{0}_{N}-\theta^{0}_{l_{p-1}}\leq\theta^{0}_{N}-\theta^{0}_{j_{p-1}}\leq\frac{\pi}{2}$ due to $j_{p-1}\leq l_{p-1}$ . Hence, according to $l_{p-1}<N_{0}$ , the following assertion can be obtained

(3.3)

\eta^{N_{0}-n}\sin(\theta^{0}_{j_{p-1}}-\theta^{0}_{N})\leq\eta^{l_{p-1}-n}\sin(\theta^{0}_{j_{p-1}}-\theta^{0}_{N})\leq\eta^{l_{p-1}-n}\sin(\theta^{0}_{l_{p-1}}-\theta^{0}_{N}),

On the other hand, if $\frac{\pi}{2}<\theta^{0}_{N}-\theta^{0}_{j_{p-1}}\leq D_{0}(\theta(t))<\gamma$ . It’s clear that $\sin(\theta^{0}_{N}-\theta^{0}_{j_{p-1}})>\sin\gamma$ . Then according to the strict inequality $l_{p-1}<N_{0}$ and $\eta>\frac{1}{\sin\gamma}\geq 1$ , we can obtain that

(3.4)

\displaystyle\eta^{N_{0}-n}\sin(\theta^{0}_{j_{p-1}}-\theta^{0}_{N_{0}})\leq-\eta^{N_{0}-n-1}\eta\sin\gamma\leq-\eta^{N_{0}-n-1}\leq-\eta^{l_{p-1}-n}\leq\eta^{l_{p-1}-n}\sin(\theta^{0}_{l_{p-1}}-\theta^{0}_{N}),

where the last inequality holds due to the fact $\sin x\geq-1$ . Therefore, combining above estimates (3.3) and (3.4), we obtain that

(3.5)

\eta^{N_{0}-n}\sin(\theta^{0}_{j_{p-1}}-\theta^{0}_{N_{0}})\leq\eta^{l_{p-1}-n}\sin(\theta^{0}_{l_{p-1}}-\theta^{0}_{N_{0}}).

Next, we apply (3.5) and the concave property of $\sin x$ in half circle to estimate the term $\mathcal{I}_{1}$ as follows:

(3.6)

\mathcal{I}_{1}\leq\eta^{l_{p-1}-n}\sin(\theta^{0}_{l_{p-1}}-\theta^{0}_{N})+\eta^{l_{p-1}-n}\sin(\theta^{0}_{j_{p-2}}-\theta^{0}_{l_{p-1}})\leq\eta^{l_{p-1}-n}\sin(\theta^{0}_{j_{p-2}}-\theta^{0}_{N}).

Finally, we repeat the similar argument in (3.5) and (3.6) to obtain that

	$\displaystyle\sum_{i=n}^{N_{0}}(\eta^{i-n}\underset{j\leq i}{\min_{j\in\mathcal{N}^{0}_{i}(0)}}\sin(\theta^{0}_{j}-\theta^{0}_{i}))$	$\displaystyle\leq\eta^{l_{0}-n}\sin(\theta^{0}_{l_{0}}-\theta^{0}_{N_{0}})+\eta^{l_{0}-n}\sin(\theta^{0}_{\bar{k}_{n}}-\theta^{0}_{l_{0}})$
		$\displaystyle\leq\eta^{l_{0}-n}\sin(\theta^{0}_{\bar{k}_{n}}-\theta^{0}_{N_{0}})\leq\sin(\theta^{0}_{\bar{k}_{n}}-\theta^{0}_{N_{0}}),$

where the last inequality holds since $l_{0}\geq n$ . Therefore we derive the desired result. ∎

Based on a priori estimates in Lemma 3.1, we next design a proper convex combination so that we can capture the dissipation structure. Recall the strongly connected ensemble $\mathcal{G}_{0}$ , and denote by $\theta_{i}^{0}\ (i=1,2,\ldots,N_{0})$ the members in $\mathcal{G}_{0}$ . Now we assume that at time $t$ , the oscillators in $\mathcal{G}_{0}$ are well-ordered as follows,

\theta^{0}_{1}(t)\leq\theta^{0}_{2}(t)\leq\ldots\leq\theta^{0}_{N_{0}}(t).

Then we apply the process $\mathcal{A}_{1}$ from $\theta^{0}_{N_{0}}$ to $\theta^{0}_{1}$ and the process $\mathcal{A}_{2}$ from $\theta^{0}_{1}$ to $\theta^{0}_{N_{0}}$ to respectively construct

(3.7)			$\displaystyle\bar{\mathcal{L}}_{k-1}^{N_{0}}(\bar{C}_{k-1,N_{0}})\ \mbox{with}\ \bar{a}^{0}_{N_{0}}=0,\ \bar{a}^{0}_{k-1}=\eta(2N_{0}-k+2)(\bar{a}^{0}_{k}+1),\quad 2\leq k\leq N_{0},$
(3.7)			$\displaystyle\underline{\mathcal{L}}_{1}^{k+1}(\underline{C}_{1,k+1})\ \mbox{with}\ \underline{a}^{0}_{1}=0,\ \underline{a}^{0}_{k+1}=\eta(k+1+N_{0})(\underline{a}^{0}_{k}+1),\quad 1\leq k\leq N_{0}-1,$

where $N_{0}$ is the cardinality of $\mathcal{G}_{0}$ and $\eta$ is given in the condition (1.2). By induction, we can derive explict expressions about the constructed coefficients:

(3.8)			$\displaystyle\bar{a}^{0}_{k-1}=\sum_{j=1}^{N_{0}-k+1}\eta^{j}A(2N_{0}-k+2,j),\quad 2\leq k\leq N_{0},$
(3.8)			$\displaystyle\underline{a}^{0}_{k+1}=\sum_{j=1}^{k}\eta^{j}A(k+1+N_{0},j),\quad 1\leq k\leq N_{0}-1.$

Note that $\bar{a}^{0}_{N_{0}+1-i}=\underline{a}^{0}_{i},\ i=1,2\ldots,N_{0}$ . And we set

(3.9)

\bar{\theta}^{0}_{k}:=\bar{\mathcal{L}}_{k}^{N_{0}}(\bar{C}_{k,N_{0}}),\quad\underline{\theta}^{0}_{k}:=\underline{\mathcal{L}}_{1}^{k}(\underline{C}_{1,k}),\quad 1\leq k\leq N_{0}.

We define $Q^{0}=\bar{\theta}_{0}-\underline{\theta}_{0}$ where $\bar{\theta}_{0}=\bar{\theta}^{0}_{1}$ and $\underline{\theta}_{0}=\underline{\theta}^{0}_{N_{0}}$ . Note that $Q^{0}(t)$ is Lipschitz continuous with respect to $t$ . We then establish the comparison relation between $Q^{0}$ and the phase diameter $D_{0}(\theta)$ of $\mathcal{G}_{0}$ in the following lemma.

Lemma 3.2.

Let $\theta_{i}=\{\theta^{0}_{i}\}$ be a solution to system (1.1) with strong connected digraph $\mathcal{G}_{0}$ . Assume that for the group $\mathcal{G}_{0}$ , the coefficients $\bar{a}_{k}^{0}$ ’s and $\underline{a}_{k}^{0}$ ’s satisfy the scheme (3.7). Then at each time $t$ , we have the following relation

\beta D_{0}(\theta(t))\leq Q^{0}(t)\leq D_{0}(\theta(t)),\quad\beta=1-\frac{2}{\eta},

where $\eta$ satisfies the condition (1.2).

Proof.

From the convex combination structure of $\bar{\theta}_{0}$ and $\underline{\theta}_{0}$ , we immediately have

Q^{0}(t)=\bar{\theta}_{0}-\underline{\theta}_{0}\leq\theta^{0}_{N_{0}}(t)-\theta^{0}_{1}(t)=D_{0}(\theta(t)).

We now prove the left part of the desired relation. In fact, we have the following estimate about $Q^{0}(t)$ :

(3.10)	$\displaystyle Q^{0}(t)$	$\displaystyle=\bar{\theta}_{0}(t)-\underline{\theta}_{0}(t)=\bar{\theta}_{0}(t)-\theta_{N_{0}}^{0}(t)+\theta_{N_{0}}^{0}(t)-\theta_{1}^{0}(t)+\theta^{0}_{1}(t)-\underline{\theta}_{0}(t)$
		$\displaystyle=\theta_{N_{0}}^{0}(t)-\theta_{1}^{0}(t)+\bar{\theta}_{0}(t)-\theta_{N_{0}}^{0}(t)+\theta^{0}_{1}(t)-\underline{\theta}_{0}(t)$
		$\displaystyle=\theta_{N_{0}}^{0}(t)-\theta_{1}^{0}(t)+\left(\frac{\theta_{1}^{0}(t)}{\bar{a}_{1}^{0}+1}+\frac{\prod_{l=1}^{N_{0}-1}\bar{a}_{l}^{0}}{\prod_{l=1}^{N_{0}-1}(\bar{a}^{0}_{l}+1)}\theta^{0}_{N_{0}}(t)+\sum_{i=2}^{N_{0}-1}\frac{\prod_{l=1}^{i-1}\bar{a}^{0}_{l}}{\prod_{l=1}^{i}(\bar{a}^{0}_{l}+1)}\theta_{i}^{0}(t)-\theta^{0}_{N_{0}}(t)\right)$
		$\displaystyle+\left(\theta^{0}_{1}(t)-\frac{\theta^{0}_{N_{0}}(t)}{\underline{a}_{N_{0}}^{0}+1}-\frac{\prod_{l=2}^{N_{0}}\underline{a}_{l}^{0}}{\prod_{l=2}^{N_{0}}(\underline{a}_{l}^{0}+1)}\theta^{0}_{1}(t)-\sum_{i=2}^{N_{0}-1}\frac{\prod_{l=i+1}^{N_{0}}\underline{a}_{l}^{0}}{\prod_{l=i}^{N_{0}}(\underline{a}_{l}^{0}+1)}\theta^{0}_{i}(t)\right)$
		$\displaystyle=\theta_{N_{0}}^{0}(t)-\theta_{1}^{0}(t)+\frac{1}{\bar{a}_{1}^{0}+1}(\theta^{0}_{1}(t)-\theta^{0}_{N_{0}}(t))+\sum_{i=2}^{N_{0}-1}\frac{\prod_{l=1}^{i-1}\bar{a}^{0}_{l}}{\prod_{l=1}^{i}(\bar{a}^{0}_{l}+1)}(\theta_{i}^{0}(t)-\theta^{0}_{N_{0}}(t))$
		$\displaystyle+\frac{1}{\underline{a}_{N_{0}}^{0}+1}(\theta^{0}_{1}(t)-\theta^{0}_{N_{0}}(t))+\sum_{i=2}^{N_{0}-1}\frac{\prod_{l=i+1}^{N_{0}}\underline{a}_{l}^{0}}{\prod_{l=i}^{N_{0}}(\underline{a}_{l}^{0}+1)}(\theta^{0}_{1}(t)-\theta^{0}_{i}(t)),$

where we apply the property that the coefficients sum of convex combination structure of $\bar{\theta}_{0}$ and $\underline{\theta}_{0}$ are respectively equal to $1$ . According to the design of coefficients (3.7) and (3.8), it is known that

\bar{a}^{0}_{N_{0}+1-i}=\underline{a}^{0}_{i},\quad i=1,2\ldots,N_{0}.

Thus, we immediately have

(3.11)

\frac{\prod_{l=i+1}^{N_{0}}\underline{a}_{l}^{0}}{\prod_{l=i}^{N_{0}}(\underline{a}_{l}^{0}+1)}=\frac{\prod_{l=1}^{N_{0}-i}\bar{a}_{l}^{0}}{\prod_{l=1}^{N_{0}+1-i}(\bar{a}_{l}^{0}+1)}.

Then we combine (3.10) and (3.11)to obtain that

	$\displaystyle Q^{0}(t)$	$\displaystyle\geq\theta_{N_{0}}^{0}(t)-\theta_{1}^{0}(t)+\frac{1}{\bar{a}_{1}^{0}+1}(\theta^{0}_{1}(t)-\theta^{0}_{N_{0}}(t))+\sum_{i=2}^{N_{0}-1}\frac{\prod_{l=1}^{i-1}\bar{a}^{0}_{l}}{\prod\limits_{l=1}^{i}(\bar{a}^{0}_{l}+1)}(\theta_{1}^{0}(t)-\theta^{0}_{N_{0}}(t))$
		$\displaystyle+\frac{1}{\bar{a}_{1}^{0}+1}(\theta^{0}_{1}(t)-\theta^{0}_{N_{0}}(t))+\sum_{i=2}^{N_{0}-1}\frac{\prod_{l=1}^{N_{0}-i}\bar{a}_{l}^{0}}{\prod_{l=1}^{N_{0}+1-i}(\bar{a}_{l}^{0}+1)}(\theta^{0}_{1}(t)-\theta^{0}_{N_{0}}(t))$
		$\displaystyle=\theta_{N_{0}}^{0}(t)-\theta_{1}^{0}(t)-\left(\frac{2}{\bar{a}_{1}^{0}+1}+\sum_{i=2}^{N_{0}-1}\frac{\prod_{l=1}^{i-1}\bar{a}^{0}_{l}}{\prod_{l=1}^{i}(\bar{a}^{0}_{l}+1)}+\sum_{i=2}^{N_{0}-1}\frac{\prod_{l=1}^{N_{0}-i}\bar{a}_{l}^{0}}{\prod_{l=1}^{N_{0}+1-i}(\bar{a}_{l}^{0}+1)}\right)(\theta^{0}_{N_{0}}(t)-\theta^{0}_{1}(t)),$

where we exploit the property of well-ordering, i.e.,

\theta_{1}^{0}\leq\theta_{i}^{0}\leq\theta_{N_{0}}^{0},\quad 1\leq i\leq N_{0}.

From (3.7), it is obvious that the value of coefficients $\bar{a}^{0}_{k}$ ’s is increasing as the subscript is decreasing, in particular,

\bar{a}^{0}_{l}\geq\bar{a}^{0}_{N_{0}-1}=\eta(N_{0}+2),\quad 1\leq l\leq N_{0}-1.

Then for $2\leq i\leq N_{0}-1$ , we have the following estimates,

		$\displaystyle\frac{1}{\bar{a}_{1}^{0}+1}\leq\frac{1}{\eta(N_{0}+2)+1},\quad\frac{\prod_{l=1}^{i-1}\bar{a}^{0}_{l}}{\prod_{l=1}^{i}(\bar{a}^{0}_{l}+1)}\leq\frac{1}{\bar{a}_{i}^{0}+1}\leq\frac{1}{\eta(N_{0}+2)+1},$
		$\displaystyle\frac{\prod_{l=1}^{N_{0}-i}\bar{a}_{l}^{0}}{\prod_{l=1}^{N_{0}+1-i}(\bar{a}_{l}^{0}+1)}\leq\frac{1}{\bar{a}_{N_{0}+1-i}^{0}+1}\leq\frac{1}{\eta(N_{0}+2)+1}.$

Therefore we immediately obtain that

Q^{0}(t)\geq\theta_{N_{0}}^{0}(t)-\theta_{1}^{0}(t)-\frac{2(N_{0}-1)}{\eta(N_{0}+2)+1}(\theta_{N_{0}}^{0}(t)-\theta_{1}^{0}(t))=D_{0}(\theta(t))-\frac{2(N_{0}-1)}{\eta(N_{0}+2)+1}D_{0}(\theta(t)).

Since $\frac{2(N_{0}-1)}{\eta(N_{0}+2)+1}\leq\frac{2N_{0}}{\eta N_{0}}=\frac{2}{\eta}$ , it can be obtained that

Q^{0}(t)\geq(1-\frac{2}{\eta})D_{0}(\theta(t)),

thus we derive the desired result. ∎

In the following, we exploit Algorithm $\mathcal{A}$ and Lemma 3.1 to estimate the dynamics of the constructed quantity $Q^{0}$ , i.e., the relative distance between $\bar{\mathcal{L}}_{1}^{N_{0}}(\bar{C}_{1,N_{0}})$ and $\underline{\mathcal{L}}_{1}^{N_{0}}(\underline{C}_{1,N_{0}})$ , which will be presented in the lemma below.

Lemma 3.3.

Let $\theta_{i}=\{\theta^{0}_{i}\}$ be the solution to system (1.1) with strong connected digraph $\mathcal{G}_{0}$ . Moreover, for a given sufficiently small $D^{\infty}<\min\left\{\frac{\pi}{2},\alpha\right\}$ , assume the following conditions hold,

(3.12)

D_{0}(\theta(0))<\alpha<\gamma<\pi,\quad\eta>\max\left\{\frac{1}{\sin\gamma},\frac{2}{1-\frac{\alpha}{\gamma}}\right\},\quad\kappa>\left(1+\frac{\alpha}{\alpha-D(\theta(0))}\right)\frac{\tilde{c}}{\beta D^{\infty}},

where $\alpha,\gamma$ are constants and

\tilde{c}=\frac{D(\Omega)(\sum_{j=1}^{N_{0}-1}\eta^{j}A(2N_{0},j)+1)\gamma}{\sin\gamma}.

Then, the dynamics of $Q^{0}(t)$ is governed by the following equation

\dot{Q}^{0}(t)\leq D(\Omega)-\frac{\kappa}{\sum_{j=1}^{N_{0}-1}(\eta^{j}A(2N_{0},j))+1}\frac{\sin\gamma}{\gamma}Q^{0}(t),\quad t\in[0,+\infty),

and the phase diameter of the graph $\mathcal{G}_{0}$ is uniformly bounded by $\gamma$ :

D_{0}(\theta(t))<\gamma,\quad t\in[0,+\infty).

Proof.

As the proof is rather lengthy, we put it in Appendix A. ∎

Lemma 3.3 states that the phase diameter of the digraph $\mathcal{G}_{0}$ is uniformly bounded and can be confined in half circle. We next show that there exists some time $t_{0}$ after which the phase diameter of the digraph $\mathcal{G}_{0}$ enters into a small region.

Lemma 3.4.

Let $\theta_{i}=\{\theta^{0}_{i}\}$ be a solution to system (1.1), and supose the assumptions of Lemma 3.3 hold. Then there exists time $t_{0}$ such that

D_{0}(\theta(t))\leq D^{\infty},\quad\mbox{for}\ t\in[t_{0},+\infty),

where $t_{0}$ can be estimated as below and bounded by $\bar{t}$ given in Lemma 2.4

(3.13)

t_{0}<\frac{\alpha}{\kappa\frac{\sin\gamma}{(\sum_{j=1}^{N_{0}-1}\eta^{j}A(2N_{0},j)+1)\gamma}\beta D^{\infty}-D(\Omega)}<\bar{t}.

Proof.

In Lemma 3.3, we have obtained that the dynamics of quantity $Q^{0}(t)$ is governed by the following equation

(3.14)

\dot{Q}^{0}(t)\leq D(\Omega)-\kappa\frac{1}{\sum_{j=1}^{N_{0}-1}(\eta^{j}A(2N_{0},j))+1}\frac{\sin\gamma}{\gamma}Q^{0}(t),\quad t\in[0,+\infty).

In the subsequence, we will find some time $t_{0}$ after which the quantity $Q^{0}$ in (3.14) is uniformly bounded. We consider two cases separately.

$\diamond$ Case 1. We first consider the case that $Q^{0}(0)>\beta D^{\infty}$ . When $Q^{0}(t)\in[\beta D^{\infty},Q^{0}(0)]$ , according to (A.15), we have

(3.15)		$\displaystyle\dot{Q}^{0}(t)$	$\displaystyle\leq D(\Omega)-\kappa\frac{\sin\gamma}{(\sum_{j=1}^{N_{0}-1}(\eta^{j}A(2N_{0},j))+1)\gamma}Q^{0}(t)$
(3.15)			$\displaystyle\leq D(\Omega)-\kappa\frac{\sin\gamma}{(\sum_{j=1}^{N_{0}-1}(\eta^{j}A(2N_{0},j))+1)\gamma}\beta D^{\infty}<0.$

This means that when $Q^{0}(t)$ is located in the interval $[\beta D^{\infty},Q^{0}(0)]$ , $Q^{0}(t)$ will keep decreasing with a uniform rate. Therefore we can define a stopping time $t_{0}$ as follows,

t_{0}=\inf\{t\geq 0\ |\ Q^{0}(t)\leq\beta D^{\infty}\}.

Then, according to the definition of $t_{0}$ , we know that $Q^{0}$ will decrease before $t_{0}$ and has the following property at $t_{0}$ ,

(3.16)

Q^{0}(t_{0})=\beta D^{\infty}.

Moerover, according to (3.15), it is obvious that the stopping time $t_{0}$ satisfies the following upper bound estimate,

(3.17)

t_{0}\leq\frac{Q^{0}(0)-\beta D^{\infty}}{\kappa\frac{\sin\gamma}{(\sum_{j=1}^{N_{0}-1}\eta^{j}A(2N_{0},j)+1)\gamma}\beta D^{\infty}-D(\Omega)}.

Now we study the upper bound of $Q^{0}$ on $[t_{0},+\infty)$ . Coming back to (3.15), we can apply (3.16) and the same argument in (A.16) to derive

(3.18)

Q^{0}(t)\leq\beta D^{\infty},\ t\in[t_{0},+\infty).

$\diamond$ Case 2. For another case that $Q^{0}(0)\leq\beta D^{\infty}$ . Applying the same analysis in (A.16), we get

(3.19)

Q^{0}(t)\leq\beta D^{\infty},\quad t\in[0,+\infty).

This allows us to directly set $t_{0}=0$ .

Thus we apply (3.18), (3.19), and Lemma 3.2 to estimate the upper bound of $D_{0}(\theta)$ on $[t_{0},\infty)$ as below

(3.20)

D_{0}(\theta(t))\leq\frac{Q^{0}(t)}{\beta}\leq D^{\infty},\quad\mbox{for}\ t\in[t_{0},+\infty).

On the other hand, in order to verify (3.13), we do further estimates on $t_{0}$ in (3.20). It is known from (3.17) in Case 1 and $t_{0}=0$ in Case 2 that

(3.21)

t_{0}<\frac{\alpha}{\kappa\frac{\sin\gamma}{(\sum_{j=1}^{N_{0}-1}\eta^{j}A(2N_{0},j)+1)\gamma}\beta D^{\infty}-D(\Omega)}.

Here, we use the truth that $Q^{0}(0)<\alpha$ . Thus, from the assumption of $\kappa$ in (3.12), i.e.,

\kappa>\left(1+\frac{\alpha}{\alpha-D(\theta(0))}\right)\frac{\tilde{c}}{\beta D^{\infty}},\quad\tilde{c}=\frac{D(\Omega)(\sum_{j=1}^{N_{0}-1}\eta^{j}A(2N_{0},j)+1)\gamma}{\sin\gamma}.

it yields that the time $t_{0}$ has the following estimate,

(3.22)

t_{0}<\frac{\alpha}{(1+\frac{\alpha}{\alpha-D(\theta(0))})D(\Omega)-D(\Omega)}=\frac{\alpha-D(\theta(0))}{D(\Omega)}=\bar{t}.

Thus, we derive the desired results (3.20), (3.21) and (3.22). ∎

4. General network

Now, we focus on the general network, and provide a proof of Theorem 1.1 for the emergence of complete synchronization in Kuramoto model with general network containing a spanning tree. According to Definition 2.3 and Lemma 2.2, the digraph $\mathcal{G}$ associated to system (1.1) has a unique maximum node if it contains a spanning tree structure. From Remark 2.1, without loss of generality, $\mathcal{G}$ can be decomposed into a union as $\mathcal{G}=\bigcup_{i=0}^{d}\mathcal{G}_{i}$ , where $\mathcal{G}_{p}$ is a maximum node of $\mathcal{G}\setminus(\bigcup_{i=0}^{p-1}\mathcal{G}_{i})$ .

In Section 3, for the situation that $d=0$ , we showed that the phase diameter of the digraph $\mathcal{G}_{0}$ is uniformly bounded and can be confined in a quarter circle after some finite time. However, for the case that $d>0$ , $\mathcal{G}_{k}$ ’s are not maximum nodes in $\mathcal{G}$ for $k\geq 1$ . Hence, we can not directly apply the same method in Lemma 3.3 and Lemma 3.4 for the situation $d=0$ . More precisely, the oscillators in $\mathcal{G}_{i}$ with $i<k$ perform as an attraction source and influence the agents in $\mathcal{G}_{k}$ . Thus we can not ignore the information from $\mathcal{G}_{i}$ with $i<k$ when we study the behavior of agents in $\mathcal{G}_{k}$ .

From Remark 2.1 and node decomposition, the graph $\mathcal{G}$ can be represented as

\mathcal{G}=\bigcup_{k=0}^{d}\mathcal{G}_{k},\quad|\mathcal{G}_{k}|=N_{k},

and we denote the oscillators in $\mathcal{G}_{k}$ by $\theta^{k}_{i}$ with $1\leq i\leq N_{k}$ . Then we assume that at time $t$ , the oscillators in each $\mathcal{G}_{k}$ are well-ordered as below:

(4.1)

\theta^{k}_{1}(t)\leq\theta^{k}_{2}(t)\leq\ldots\leq\theta^{k}_{N_{k}}(t),\quad 0\leq k\leq d.

For each subdigraph $\mathcal{G}_{k}$ with $k\geq 0$ which is strongly connected, we follow the process in Algorithm $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$ to construct $\bar{\mathcal{L}}_{l-1}^{N_{k}}(\bar{C}_{l-1,N_{k}})$ and $\underline{\mathcal{L}}_{1}^{l+1}(\underline{C}_{1,l+1})$ by redesigning the coefficients $\bar{a}^{k}_{l}$ and $\underline{a}_{l}^{k}$ of convex combination as below:

(4.2)

\begin{cases}\displaystyle\bar{\mathcal{L}}_{l-1}^{N_{k}}(\bar{C}_{l-1,N_{k}})\ \mbox{with}\ \bar{a}^{k}_{N_{k}}=0,\ \bar{a}^{k}_{l-1}=\eta(2N-l+2)(\bar{a}^{k}_{l}+1),\quad 2\leq l\leq N_{k},\\ \displaystyle\underline{\mathcal{L}}_{1}^{l+1}(\underline{C}_{1,l+1})\ \mbox{with}\ \underline{a}^{k}_{1}=0,\ \underline{a}^{k}_{l+1}=\eta(l+1+2N-N_{k})(\underline{a}^{k}_{l}+1),\quad 1\leq l\leq N_{k}-1,\end{cases}

By induction principle, we deduce that

(4.3)

\begin{cases}\displaystyle\bar{a}^{k}_{l-1}=\sum_{j=1}^{N_{k}-l+1}\eta^{j}A(2N-l+2,j),\quad 2\leq l\leq N_{k},\\ \displaystyle\underline{a}^{k}_{l+1}=\sum_{j=1}^{l}\eta^{j}A(l+1+2N-N_{k},j),\quad 1\leq l\leq N_{k}-1.\end{cases}

Note that $\bar{a}^{k}_{N_{k}+1-i}=\underline{a}^{k}_{i},\ i=1,2\ldots,N_{k}$ . By simple calculation, we have

(4.4)

\bar{a}^{k}_{1}=\sum^{N_{k}-1}_{j=1}(\eta^{j}A(2N,j)),\quad\bar{a}^{k}_{1}\leq\sum^{N-1}_{j=1}(\eta^{j}A(2N,j)),\quad 0\leq k\leq d.

And we set the following notations,

(4.5)		$\displaystyle\bar{\theta}^{k}_{l}:=\bar{\mathcal{L}}_{l}^{N_{k}}(\bar{C}_{l,N_{k}}),\quad\underline{\theta}^{k}_{l}:=\underline{\mathcal{L}}_{1}^{l}(\underline{C}_{1,l}),\quad 1\leq l\leq N_{k},\quad 0\leq k\leq d,$
(4.6)		$\displaystyle\bar{\theta}_{k}:=\bar{\mathcal{L}}_{1}^{N_{k}}(\bar{C}_{1,N_{k}}),\quad\underline{\theta}_{k}:=\underline{\mathcal{L}}_{1}^{N_{k}}(\underline{C}_{1,N_{k}}),\quad 0\leq k\leq d,$
(4.7)		$\displaystyle Q^{k}(t):=\max_{0\leq i\leq k}\{\bar{\theta}_{i}\}-\min_{0\leq i\leq k}\{\underline{\theta}_{i}\},\quad 0\leq k\leq d.$

Due to the analyticity of the solution, $Q^{k}(t)$ is Lipschitz continuous. Similar as in Section 3, in the following, we will first establish the comparison relation between the quantity $Q^{k}(t)$ and phase diameter $D_{k}(\theta(t))$ of the first $k+1$ nodes, which plays an important role in the later analysis.

Lemma 4.1.

Let $\theta_{i}$ be a solution to system (1.1) and assume that for each subdigraph $\mathcal{G}_{k}$ , the coefficients $\bar{a}^{k}_{l}$ and $\underline{a}^{k}_{l}$ of convex combination in Algorithm $\mathcal{A}$ satisfy the scheme (4.2). Then at each time $t$ , we have the following relation

\beta D_{k}(\theta(t))\leq Q^{k}(t)\leq D_{k}(\theta(t)),\quad 0\leq k\leq d,\quad\beta=1-\frac{2}{\eta},

where $D_{k}(\theta)=\max\limits_{0\leq i\leq k}\max\limits_{1\leq j\leq N_{i}}\{\theta_{j}^{i}\}-\min\limits_{0\leq i\leq k}\min\limits_{1\leq j\leq N_{i}}\{\theta_{j}^{i}\}$ and $\eta$ satisfies the condition (1.2).

Proof.

Without loss of generality, assume that at time $t$ , the oscillators in each subdigraph $\mathcal{G}_{k}$ are all well-ordered as below

(4.8)

\theta^{k}_{1}\leq\theta^{k}_{2}\leq\ldots\leq\theta^{k}_{N_{k}},\quad 0\leq k\leq d.

From the definition of the quantity $Q^{k}(t)$ in (4.7) and the convex combination structure of $\bar{\theta}_{k}$ and $\underline{\theta}_{k}$ in (4.6), it can be directly derived that

(4.9)

\bar{\theta}_{k}\leq\theta^{k}_{N_{k}},\quad\underline{\theta}_{k}\geq\theta^{k}_{1},\quad Q^{k}(t)=\max_{0\leq i\leq k}\{\bar{\theta}_{i}\}-\min_{0\leq i\leq k}\{\underline{\theta}_{i}\}\leq\max_{0\leq i\leq k}\{\theta^{i}_{N_{i}}\}-\min_{0\leq i\leq k}\{\theta^{i}_{1}\}.

This means that

Q^{k}(t)\leq D_{k}(\theta(t))=\max_{0\leq i\leq k}\max\limits_{1\leq j\leq N_{i}}\{\theta_{j}^{i}\}-\min_{0\leq i\leq k}\min\limits_{1\leq j\leq N_{i}}\{\theta_{j}^{i}\}.

Next we will prove the left part of this Lemma. In fact, we denote the extreme phases of the first $k+1$ nodes by

(4.10)

\theta^{p}_{N_{p}}:=\max_{0\leq i\leq k}\max_{1\leq j\leq N_{i}}\{\theta^{i}_{j}\},\quad\theta^{q}_{1}:=\min_{0\leq i\leq k}\min_{1\leq j\leq N_{i}}\{\theta^{i}_{j}\},\quad 0\leq p\leq k,\ 0\leq q\leq k.

It is clear that $D_{k}(\theta(t))=\theta^{p}_{N_{p}}-\theta^{q}_{1}$ . We consider two cases separately.

$\bullet$ Case 1. If the index satisfy the relation $p=q$ , we have

Q^{k}(t)=\max_{0\leq i\leq k}\{\bar{\theta}_{i}\}-\min_{0\leq i\leq k}\{\underline{\theta}_{i}\}\geq\bar{\theta}_{p}-\underline{\theta}_{p}=\theta^{p}_{N_{p}}-\theta^{p}_{1}+\bar{\theta}_{p}-\theta^{p}_{N_{p}}+\theta^{p}_{1}-\underline{\theta}_{p}.

In this case, applying the same arguments in Lemma 3.2, we obtain that

	$\displaystyle Q^{k}(t)$	$\displaystyle\geq\theta^{p}_{N_{p}}(t)-\theta^{p}_{1}(t)-\frac{2(N_{p}-1)}{\eta(N+2)+1}(\theta_{N_{p}}^{p}(t)-\theta_{1}^{p}(t))=D_{k}(\theta(t))-\frac{2(N_{p}-1)}{\eta(N+2)+1}D_{k}(\theta(t))$
		$\displaystyle\geq(1-\frac{2}{\eta})D_{k}(\theta(t))=\beta D_{k}(\theta(t)).$

Here, in the above estimates, based on the construction of coefficients of convex combination in (4.2), we used the inequalities

(4.11)

\bar{a}^{k}_{l}\geq\bar{a}^{k}_{N_{k}-1}=\eta(2N-N_{k}+2)\geq\eta(N+2),\quad 0\leq k\leq d,\ 1\leq l\leq N_{k}-1,

and applied the symmetric property

(4.12)

\bar{a}^{k}_{N_{k}+1-l}=\underline{a}^{k}_{l},\quad 1\leq l\leq N_{k},\ 0\leq k\leq d.

$\bullet$ Case 2. Consider the case that $p\neq q$ , then we have

(4.13)	$\displaystyle Q^{k}(t)$	$\displaystyle=\max_{0\leq i\leq k}\{\bar{\theta}_{i}\}-\min_{0\leq i\leq k}\{\underline{\theta}_{i}\}\geq\bar{\theta}_{p}-\underline{\theta}_{q}=\bar{\theta}_{p}(t)-\theta_{N_{p}}^{p}(t)+\theta_{N_{p}}^{p}(t)-\theta_{1}^{q}(t)+\theta^{q}_{1}(t)-\underline{\theta}_{q}(t)$
		$\displaystyle=\theta_{N_{p}}^{p}(t)-\theta_{1}^{q}(t)+\bar{\theta}_{p}(t)-\theta_{N_{p}}^{p}(t)+\theta^{q}_{1}(t)-\underline{\theta}_{q}(t)$
		$\displaystyle=\theta_{N_{p}}^{p}(t)-\theta_{1}^{q}(t)+\left(\frac{\theta_{1}^{p}(t)}{\bar{a}_{1}^{p}+1}+\frac{\prod_{l=1}^{N_{p}-1}\bar{a}_{l}^{p}}{\prod_{l=1}^{N_{p}-1}(\bar{a}^{p}_{l}+1)}\theta^{p}_{N_{p}}(t)+\sum_{i=2}^{N_{p}-1}\frac{\prod_{l=1}^{i-1}\bar{a}^{p}_{l}}{\prod_{l=1}^{i}(\bar{a}^{p}_{l}+1)}\theta_{i}^{p}(t)-\theta^{p}_{N_{p}}(t)\right)$
		$\displaystyle+\left(\theta^{q}_{1}(t)-\frac{\theta^{q}_{N_{q}}(t)}{\underline{a}_{N_{q}}^{q}+1}-\frac{\prod_{l=2}^{N_{q}}\underline{a}_{l}^{q}}{\prod_{l=2}^{N_{q}}(\underline{a}_{l}^{q}+1)}\theta^{q}_{1}(t)-\sum_{i=2}^{N_{q}-1}\frac{\prod_{l=i+1}^{N_{q}}\underline{a}_{l}^{q}}{\prod_{l=i}^{N_{q}}(\underline{a}_{l}^{q}+1)}\theta^{q}_{i}(t)\right)$
		$\displaystyle=\theta_{N_{p}}^{p}(t)-\theta_{1}^{q}(t)+\frac{1}{\bar{a}_{1}^{p}+1}(\theta^{p}_{1}(t)-\theta^{p}_{N_{p}}(t))+\sum_{i=2}^{N_{p}-1}\frac{\prod_{l=1}^{i-1}\bar{a}^{p}_{l}}{\prod_{l=1}^{i}(\bar{a}^{p}_{l}+1)}(\theta_{i}^{p}(t)-\theta^{p}_{N_{p}}(t))$
		$\displaystyle+\frac{1}{\underline{a}_{N_{q}}^{q}+1}(\theta^{q}_{1}(t)-\theta^{q}_{N_{q}}(t))+\sum_{i=2}^{N_{q}-1}\frac{\prod_{l=i+1}^{N_{q}}\underline{a}_{l}^{q}}{\prod_{l=i}^{N_{q}}(\underline{a}_{l}^{q}+1)}(\theta^{q}_{1}(t)-\theta^{q}_{i}(t)),$

where we apply the property that the coefficients sum of convex combination of $\bar{\theta}_{k}$ and $\underline{\theta}_{k}$ with $0\leq k\leq d$ are respectively equal to $1$ . Moreover, we know from (4.10) that

\theta^{p}_{i}\geq\theta^{q}_{1},\ i=1,2,\ldots,N_{p}-1,\qquad\theta^{q}_{i}\leq\theta^{p}_{N_{p}},\ i=2,\ldots,N_{q}-1,N_{q}.

This implies that

(4.14)

\theta^{p}_{i}-\theta^{p}_{N_{p}}\geq\theta^{q}_{1}-\theta^{p}_{N_{p}},\ i=1,2,\ldots,N_{p}-1,\quad\theta^{q}_{1}-\theta^{q}_{i}\geq\theta^{q}_{1}-\theta^{p}_{N_{p}},\ i=2,\ldots,N_{q}-1,N_{q}.

Moreover, exlpoiting the symmetric property (4.12), we immediately have

(4.15)

\frac{\prod_{l=i+1}^{N_{q}}\underline{a}_{l}^{q}}{\prod_{l=i}^{N_{q}}(\underline{a}_{l}^{q}+1)}=\frac{\prod_{l=1}^{N_{q}-i}\bar{a}_{l}^{q}}{\prod_{l=1}^{N_{q}+1-i}(\bar{a}_{l}^{q}+1)}.

Therefore, combining (4.13), (4.14) and (4.15), we obtain that

	$\displaystyle Q^{k}(t)$	$\displaystyle\geq\theta_{N_{p}}^{p}(t)-\theta_{1}^{q}(t)+\frac{1}{\bar{a}_{1}^{p}+1}(\theta^{q}_{1}(t)-\theta^{p}_{N_{p}}(t))+\sum_{i=2}^{N_{p}-1}\frac{\prod_{l=1}^{i-1}\bar{a}^{p}_{l}}{\prod_{l=1}^{i}(\bar{a}^{p}_{l}+1)}(\theta_{1}^{q}(t)-\theta^{p}_{N_{p}}(t))$
		$\displaystyle+\frac{1}{\bar{a}_{1}^{q}+1}(\theta^{q}_{1}(t)-\theta^{p}_{N_{p}}(t))+\sum_{i=2}^{N_{q}-1}\frac{\prod_{l=1}^{N_{q}-i}\bar{a}_{l}^{q}}{\prod_{l=1}^{N_{q}+1-i}(\bar{a}_{l}^{q}+1)}(\theta^{q}_{1}(t)-\theta^{p}_{N_{p}}(t))$
		$\displaystyle=\theta_{N_{p}}^{p}(t)-\theta_{1}^{q}(t)$
		$\displaystyle-\left(\underbrace{\frac{1}{\bar{a}_{1}^{p}+1}+\sum_{i=2}^{N_{p}-1}\frac{\prod_{l=1}^{i-1}\bar{a}^{p}_{l}}{\prod_{l=1}^{i}(\bar{a}^{p}_{l}+1)}+\frac{1}{\bar{a}_{1}^{q}+1}+\sum_{i=2}^{N_{q}-1}\frac{\prod_{l=1}^{N_{q}-i}\bar{a}_{l}^{q}}{\prod_{l=1}^{N_{q}+1-i}(\bar{a}_{l}^{q}+1)}}\right)(\theta_{N_{p}}^{p}(t)-\theta_{1}^{q}(t)).$

We apply (4.11) and estimate the items in the above brace respectively,

		$\displaystyle\frac{1}{\bar{a}_{1}^{p}+1}\leq\frac{1}{\eta(N+2)+1},\quad\frac{1}{\bar{a}_{1}^{q}+1}\leq\frac{1}{\eta(N+2)+1},$
		$\displaystyle\frac{\prod_{l=1}^{i-1}\bar{a}^{p}_{l}}{\prod_{l=1}^{i}(\bar{a}^{p}_{l}+1)}\leq\frac{1}{\bar{a}_{i}^{p}+1}\leq\frac{1}{\eta(N+2)+1},\quad 2\leq i\leq N_{p}-1,$
		$\displaystyle\frac{\prod_{l=1}^{N_{q}-i}\bar{a}_{l}^{q}}{\prod_{l=1}^{N_{q}+1-i}(\bar{a}_{l}^{q}+1)}\leq\frac{1}{\bar{a}_{N_{q}+1-i}^{q}+1}\leq\frac{1}{\eta(N+2)+1},\quad 2\leq i\leq N_{q}-1.$

Thus, based on the above estimates, we have

Q^{k}(t)\geq\theta_{N_{p}}^{p}(t)-\theta_{1}^{q}(t)-\frac{N_{p}+N_{q}-2}{\eta(N+2)+1}(\theta_{N_{p}}^{p}(t)-\theta_{1}^{q}(t))=D_{k}(\theta(t))-\frac{N_{p}+N_{q}-2}{\eta(N+2)+1}D_{k}(\theta(t).

Since $\frac{N_{p}+N_{q}-2}{\eta(N+2)+1}\leq\frac{2N}{\eta N}=\frac{2}{\eta}$ and from (4.10), we immediately have

Q^{k}(t)\geq(1-\frac{2}{\eta})D_{k}(\theta(t))=\beta D_{k}(\theta(t)).

Thus combining the above analysis, we derive the desired result. ∎

Now, we are ready to prove the main Theorem 1.1. We will follow similar arguments as in Section 3 to finish the proof. Actually, we will study the constructed quantity $Q^{k}(t)$ which contains the information from $\mathcal{G}_{i}$ with $i<k$ , and then yield the hypo-coercivity of the diameter. Following similar arguments in Lemma 3.3 and Lemma 3.4, we have the following estimates for the first maximal node $\mathcal{G}_{0}$ .

Lemma 4.2.

Suppose that the network topology contains a spanning tree, and let $\theta_{i}$ be a solution to (1.1). Moreover, assume that the initial data and the quantity $\eta$ satisfy

(4.16)

D(\theta(0))<\alpha<\gamma<\pi,\quad\eta>\max\left\{\frac{1}{\sin\gamma},\frac{2}{1-\frac{\alpha}{\gamma}}\right\},

where $\alpha,\gamma$ are positive constants. For a given sufficiently small $D^{\infty}<\min\{\frac{\pi}{2},\alpha\}$ , if the coupling strength $\kappa$ satisfies

(4.17)

\kappa>\left(1+\frac{(d+1)\alpha}{\alpha-D(\theta(0))}\right)\frac{(4c)^{d}\tilde{c}}{\beta^{d+1}D^{\infty}},

where $d$ is the number of general nodes and

c=\frac{(2N+1)(\sum_{j=1}^{N-1}\eta^{j}A(2N,j)+1)\gamma}{\sin\gamma},\quad\tilde{c}=\frac{D(\Omega)(\sum_{j=1}^{N-1}\eta^{j}A(2N,j)+1)\gamma}{\sin\gamma},

then the following two assertions hold for the maximum node $\mathcal{G}_{0}$ :

(1)

The dynamics of $Q^{0}(t)$ is governed by the following equation

\dot{Q}^{0}(t)\leq D(\Omega)-\frac{\kappa}{\sum_{j=1}^{N-1}(\eta^{j}A(2N,j))+1}\frac{\sin\gamma}{\gamma}Q^{0}(t),\quad t\in[0,+\infty),

(2)

there exists time $t_{0}$ such that

D_{0}(\theta(t))\leq\frac{\beta^{d}D^{\infty}}{(4c)^{d}},\quad\mbox{for}\ t\in[t_{0},+\infty),

where $t_{0}$ can be estimated as below and bounded by $\bar{t}$ given in Lemma 2.4

t_{0}<\frac{\alpha}{\kappa\frac{\sin\gamma}{(\sum_{j=1}^{N-1}\eta^{j}A(2N,j)+1)\gamma}\frac{\beta^{d+1}D^{\infty}}{(4c)^{d}}-D(\Omega)}<\bar{t}.

Since the proof is almost the same as that in Lemma 3.3 and Lemma 3.4, we omit its details. Inspiring from Lemma 4.2, we make the following reasonable ansatz for $Q^{k}(t)$ for $0\leq k\leq d$ .

Ansatz:

(1)

The dynamics of $Q^{k}(t)$ is governed by the following differential inequality,

(4.18)

\dot{Q}^{k}(t)\leq D(\Omega)-\frac{\kappa}{\sum_{j=1}^{N-1}(\eta^{j}A(2N,j))+1}\frac{\sin\gamma}{\gamma}Q^{k}(t)+\kappa(2N+1)D_{k-1}(\theta(t)),\quad t\in[0,+\infty),

where we assume $D_{-1}(\theta(t))=0$ .

(2)

There exists a finite time $t_{k}$ such that, the phase diameter $D_{k}(\theta)$ of $\bigcup_{i=0}^{k}\mathcal{G}_{i}$ is uniformly bounded after $t_{k}$ , i.e.,

(4.19)

D_{k}(\theta(t))\leq\frac{\beta^{d-k}D^{\infty}}{(4c)^{d-k}},\quad\mbox{for}\ t\in[t_{k},+\infty),

where $t_{k}$ can be estimated as below

(4.20)

t_{k}<\frac{(k+1)\alpha}{\kappa\frac{\sin\gamma}{(\sum_{j=1}^{N-1}\eta^{j}A(2N,j)+1)\gamma}\frac{\beta^{d+1}D^{\infty}}{(4c)^{d}}-D(\Omega)}<\bar{t}=\frac{\alpha-D(\theta(0))}{D(\Omega)}.

In the following, we will verify the ansatz respectively in two lemmas by induction criteria. More precisely, suppose the ansatz holds for $Q^{k}$ and $D_{k}(\theta)$ with $0\leq k\leq d-1$ , we will prove that the ansatz also holds for $Q^{k+1}$ and $D_{k+1}(\theta)$ .

Lemma 4.3.

Suppose the conditions in Lemma 4.2 are fulfilled, and the ansatz in (4.18), (4.19) and (4.20) holds for some $k$ with $0\leq k\leq d-1$ . Then the ansatz (4.18) holds for $k+1$ .

Proof.

Similar as before, we will use proof by contradiction criteria to verify the ansatz for $Q^{k+1}$ . To this end, we first define a set below,

\mathcal{B}_{k+1}=\{T>0\ :\ D_{k+1}(\theta(t))<\gamma,\ \forall\ t\in[0,T)\}.

From Lemma 2.4, we know that

D_{k+1}(\theta(t))\leq D(\theta(t))<\alpha<\gamma,\quad\forall\ t\in[0,\bar{t}).

It is clear that $\bar{t}\in\mathcal{B}_{k+1}$ . Thus the set $\mathcal{B}_{k+1}$ is not empty. We define $T^{*}=\sup\mathcal{B}_{k+1}$ , and will prove by contradiction that $T^{*}=+\infty$ . Suppose not, i.e., $T^{*}<+\infty$ . It is obvious that

(4.21)

\bar{t}\leq T^{*},\quad D_{k+1}(\theta(t))<\gamma,\ \forall\ t\in[0,T^{*}),\quad D_{k+1}(\theta(T^{*}))=\gamma.

Since the solution to system (1.1) is analytic, in the finite time interval $[0,T^{*})$ , $\bar{\theta}_{i}$ and $\bar{\theta}_{j}$ either collide finite times or always stay together. Similar to the analysis in Lemma 3.3, without loss of generality, we only consider the situation that there is no pair of $\bar{\theta}_{i}$ and $\bar{\theta}_{j}$ staying together through all period $[0,T^{*})$ . That means the order of $\{\bar{\theta}_{i}\}_{i=0}^{k+1}$ will only exchange finite times in $[0,T^{*})$ , so does $\{\underline{\theta}_{i}\}_{i=0}^{k+1}$ . Thus, we divide the time interval $[0,T^{*})$ into a finite union as below

[0,T^{*})=\bigcup_{l=1}^{r}J_{l},\quad J_{l}=[t_{l-1},t_{l}).

such that the orders of both $\{\bar{\theta}_{i}\}_{i=0}^{k+1}$ and $\{\underline{\theta}_{i}\}_{i=0}^{k+1}$ are preseved in each interval $J_{l}$ . In the following, we will show the contradiction in two steps.

$\star$ Step 1. In this step, we first verify the Claim (4.18) holds for $Q^{k+1}$ on $[0,T^{*})$ , i.e.,

(4.22)

\dot{Q}^{k+1}(t)\leq D(\Omega)-\kappa\frac{1}{\sum_{j=1}^{N-1}(\eta^{j}A(2N,j))+1}\frac{\sin\gamma}{\gamma}Q^{k+1}(t)+\kappa(2N+1)D_{k}(\theta(t)),\quad\mbox{on}\ [0,T^{*}).

As the proof is rather lengthy, we put the detailed proof in Appendix B.

$\star$ Step 2. In this step, we will study the upper bound of $Q^{k+1}$ in (4.22) in time interval $[t_{k},T^{*})$ , where $t_{k}$ is defined in Ansatz $\eqref{F-2}$ for $D_{k}(\theta)$ . For the sake of discussion, we rewrite the equation (4.22)

(4.23)

\dot{Q}^{k+1}(t)\leq-\kappa\frac{\sin\gamma}{(\sum_{j=1}^{N-1}(\eta^{j}A(2N,j))+1)\gamma}\left(Q^{k+1}(t)-cD_{k}(\theta(t))-\frac{\tilde{c}}{\kappa}\right),\quad t\in[0,T^{*}),

where the expressions of $c$ and $\tilde{c}$ are given as below

(4.24)

c=\frac{(2N+1)(\sum_{j=1}^{N-1}(\eta^{j}A(2N,j))+1)\gamma}{\sin\gamma}\quad\mbox{and}\quad\tilde{c}=\frac{D(\Omega)(\sum_{j=1}^{N-1}(\eta^{j}A(2N,j))+1)\gamma}{\sin\gamma}.

For the term $D_{k}(\theta)$ in (4.23), by induction principle, we have assumed that the Claim (4.19) holds for $D_{k}(\theta)$ , i.e., there exists time $t_{k}$ such that

(4.25)

D_{k}(\theta(t))\leq\frac{\beta^{d-k}D^{\infty}}{(4c)^{d-k}},\quad\ t\in[t_{k},+\infty),\quad t_{k}<\bar{t}.

For the term $\frac{\tilde{c}}{\kappa}$ in (4.23), from the condition (1.3), it is obvious that

\kappa>\left(1+\frac{(d+1)\alpha}{\alpha-D(\theta(0))}\right)\frac{(4c)^{d}\tilde{c}}{\beta^{d+1}D^{\infty}}>\frac{(4c)^{d}\tilde{c}}{\beta^{d+1}D^{\infty}},

which directly yields that

(4.26)

\frac{\tilde{c}}{\kappa}<\frac{\beta^{d+1}D^{\infty}}{(4c)^{d}}<\frac{\beta^{d-k}D^{\infty}}{4^{d-k}c^{d-k-1}},\quad\mbox{where}\ 0\leq k\leq d-1,\quad\beta<1,\quad c>1.

Then we add the esimates of the two terms $D_{k}(\theta)$ and $\frac{\tilde{c}}{\kappa}$ in (4.25) and (4.26) to get

(4.27)

cD_{k}(\theta(t))+\frac{\tilde{c}}{\kappa}<c\frac{\beta^{d-k}D^{\infty}}{(4c)^{d-k}}+\frac{\beta^{d-k}D^{\infty}}{4^{d-k}c^{d-k-1}}<\frac{\beta^{d-k}D^{\infty}}{2(4c)^{d-k-1}}<\frac{\beta^{d-k}D^{\infty}}{(4c)^{d-k-1}},\quad t\in[t_{k},+\infty).

Since $t_{k}<\bar{t}\leq T^{*}$ where $\bar{t}$ is obtained in Lemma 2.4, it makes sense when we consider the time interval $[t_{k},T^{*})$ . Now based on the above estiamte (4.27), we apply the differential equation (4.23) and study the upper bound of $Q^{k+1}$ on $[t_{k},T^{*})$ . We claim that

(4.28)

Q^{k+1}(t)\leq\max\left\{Q^{k+1}(t_{k}),\frac{\beta^{d-k}D^{\infty}}{(4c)^{d-k-1}}\right\}:=M_{k+1},\quad t\in[t_{k},T^{*}).

Suppose not, then there exists some $\tilde{t}\in(t_{k},T^{*})$ such that $Q^{k+1}(\tilde{t})>M_{k+1}$ . We construct a set

\mathcal{C}_{k+1}:=\{t_{k}\leq t<\tilde{t}:Q^{k+1}(t)\leq M_{k+1}\}.

Since $Q^{k+1}(t_{k})\leq M_{k+1}$ , the set $\mathcal{C}_{k+1}$ is not empty. Then we denote $t^{*}=\sup\mathcal{C}_{k+1}$ . It is easy to see that

(4.29)

t^{*}<\tilde{t},\quad Q^{k+1}(t^{*})=M_{k+1},\quad Q^{k+1}(t)>M_{k+1}\quad\mbox{for}\ t\in(t^{*},\tilde{t}].

According to the construction of $M_{k+1}$ , (4.27) and (4.29), it is clear that for $t\in(t^{*},\tilde{t}]$

		$\displaystyle-\kappa\frac{\sin\gamma}{(\sum_{j=1}^{N-1}(\eta^{j}A(2N,j))+1)\gamma}\left(Q^{k+1}(t)-cD_{k}(\theta(t))-\frac{\tilde{c}}{\kappa}\right)$
		$\displaystyle<-\kappa\frac{\sin\gamma}{(\sum_{j=1}^{N-1}(\eta^{j}A(2N,j))+1)\gamma}\left(M_{k+1}-\frac{\beta^{d-k}D^{\infty}}{(4c)^{d-k-1}}\right)\leq 0.$

Apply the above inequality and integrate on both sides of $\eqref{F-d20}$ from $t^{*}$ to $\tilde{t}$ to get

	$\displaystyle 0<Q^{k+1}(\tilde{t})-M_{k+1}$	$\displaystyle=Q^{k+1}(\tilde{t})-Q^{k+1}(t^{*})$
		$\displaystyle\leq\int_{t^{*}}^{\tilde{t}}-\kappa\frac{\sin\gamma}{(\sum_{j=1}^{N-1}(\eta^{j}A(2N,j))+1)\gamma}\left(Q^{k+1}(t)-cD_{k}(\theta(t))-\frac{\tilde{c}}{\kappa}\right)dt<0,$

which is an obvious contradiction. Thus we complete the proof of (4.28).

$\star$ Step 3. In this step, we will construct a contradiction to (4.21). According to (4.28), Lemma 2.4 and the fact that

\frac{\beta^{d-k}D^{\infty}}{(4c)^{d-k-1}}<D^{\infty},\quad t_{k}<\bar{t},\quad Q^{k+1}(t_{k})\leq D_{k+1}(\theta(t_{k}))\leq D(\theta(t_{k}))<\alpha,

it yields that

Q^{k+1}(t)\leq\max\left\{Q^{k+1}(t_{k}),\frac{\beta^{d-k}D^{\infty}}{(4c)^{d-k-1}}\right\}<\max\{\alpha,D^{\infty}\}=\alpha,\quad t\in[t_{k},T^{*}).

Applying Lemma 4.1 and the condition (1.2), we immediately have

D_{k+1}(\theta(t))\leq\frac{Q^{k+1}(t)}{\beta}<\frac{\alpha}{\beta}<\gamma,\quad t\in[t_{k},T^{*}).

Due to the continuity of $D_{k+1}(\theta(t))$ , we have

D_{k+1}(\theta(T^{*}))=\lim_{t\to(T^{*})^{-}}D_{k+1}(\theta(t))\leq\frac{\alpha}{\beta}<\gamma,

which obviously contradicts to the assumption $D_{k+1}(\theta(T^{*}))=\gamma$ in (4.21).

Thus, we combine all above analysis to conclude that $T^{*}=+\infty$ , that is to say,

(4.30)

D_{k+1}(\theta(t))<\gamma,\quad\forall\ t\in[0,+\infty).

Then for any finite time $T>0$ , according to (4.30), we can repeat the analysis in Step 1 to obtain that the differential inequality (4.18) holds for $Q^{k+1}$ on $[0,T)$ . This yields the dynamics of $Q^{k+1}$ in whole time interval as below:

(4.31)

\dot{Q}^{k+1}(t)\leq D(\Omega)-\kappa\frac{1}{\sum_{j=1}^{N-1}(\eta^{j}A(2N,j))+1}\frac{\sin\gamma}{\gamma}Q^{k+1}(t)+\kappa(2N+1)D_{k}(\theta(t)),\quad\mbox{on}\ [0,+\infty).

Therefore, we complete the proof of the Claim (4.18) for $Q^{k+1}$ .

∎

Lemma 4.4.

Suppose the conditions in Lemma 4.2 are fulfilled, and the ansatz in (4.18), (4.19) and (4.20) holds for some $k$ with $0\leq k\leq d-1$ . Then the ansatz (4.19) and (4.20) holds for $k+1$ .

Proof.

According to Lemma 4.3, we know the dynamic of $Q^{k+1}$ is governed by (4.31). For the sake of discussion, we rewrite the differential equation (4.31) and consider it on $[t_{k},+\infty)$ ,

(4.32)

\dot{Q}^{k+1}(t)\leq-\kappa\frac{\sin\gamma}{(\sum_{j=1}^{N-1}(\eta^{j}A(2N,j))+1)\gamma}\left(Q^{k+1}(t)-cD_{k}(\theta(t))-\frac{\tilde{c}}{\kappa}\right),\quad t\in[t_{k},+\infty),

where $c$ and $\tilde{c}$ are given in (4.24). In the following, we will find time $t_{k+1}$ after which the quantity $Q^{k+1}$ in (4.32) is uniformly bounded. There are two cases we need to consider separately.

$\bullet$ Case 1. We first consider the case that $Q^{k+1}(t_{k})>\frac{\beta^{d-k}D^{\infty}}{(4c)^{d-k-1}}$ . In this case, When $Q^{k+1}(t)\in[\frac{\beta^{d-k}D^{\infty}}{(4c)^{d-k-1}},Q^{k+1}(t_{k})]$ , according to (4.27) and (4.32), we have

(4.33)		$\displaystyle\dot{Q}^{k+1}(t)$	$\displaystyle\leq-\kappa\frac{\sin\gamma}{(\sum_{j=1}^{N-1}(\eta^{j}A(2N,j))+1)\gamma}\left(\frac{\beta^{d-k}D^{\infty}}{(4c)^{d-k-1}}-\frac{\beta^{d-k}D^{\infty}}{2(4c)^{d-k-1}}\right)$
(4.33)			$\displaystyle=-\kappa\frac{\sin\gamma}{(\sum_{j=1}^{N-1}(\eta^{j}A(2N,j))+1)\gamma}\frac{\beta^{d-k}D^{\infty}}{2(4c)^{d-k-1}}<0.$

This means that when $Q^{k+1}(t)$ is located in the interval $[\frac{\beta^{d-k}D^{\infty}}{(4c)^{d-k-1}},Q^{k+1}(t_{k})]$ , $Q^{k+1}(t)$ will keep decreasing with a uniform rate. Therefore, we can define a stopping time $t_{k+1}$ as follows,

t_{k+1}=\inf\{t\geq t_{k}\ |\ Q^{k+1}(t)\leq\frac{\beta^{d-k}D^{\infty}}{(4c)^{d-k-1}}\}.

Then, according to the definition of $t_{k+1}$ , we know that $Q^{k+1}$ will decrease before $t_{k+1}$ and has the following property at $t_{k+1}$ ,

(4.34)

Q^{k+1}(t_{k+1})=\frac{\beta^{d-k}D^{\infty}}{(4c)^{d-k-1}}.

Moreover, according to (4.33), it is obvious the stopping time $t_{k+1}$ satisfies the following upper bound estimate,

(4.35)

t_{k+1}\leq\frac{Q^{k+1}(t_{k})-\frac{\beta^{d-k}D^{\infty}}{(4c)^{d-k-1}}}{\kappa\frac{\sin\gamma}{(\sum_{j=1}^{N-1}(\eta^{j}A(2N,j))+1)\gamma}\frac{\beta^{d-k}D^{\infty}}{2(4c)^{d-k-1}}}+t_{k}.

Now we study the upper bound of $Q^{k+1}$ on $[t_{k+1},+\infty)$ . Coming back to (4.33),we can apply (4.34) and the same arguments as (4.28) to derive

(4.36)

Q^{k+1}(t)\leq\frac{\beta^{d-k}D^{\infty}}{(4c)^{d-k-1}},\quad t\in[t_{k+1},+\infty).

On the other hand, in order to verify (4.20), we do further estimates on $t_{k+1}$ in (4.35). For the first part on the right-hand side of (4.35), according to Lemma 2.4, $t_{k}<\bar{t}$ and the fact that

Q^{k+1}(t_{k})\leq D_{k+1}(\theta(t_{k}))\leq D(\theta(t_{k}))<\alpha,\quad\frac{\beta^{d-k}D^{\infty}}{2(4c)^{d-k-1}}>\frac{\beta^{d+1}D^{\infty}}{(4c)^{d}},

we have the following estimates,

(4.37)

\frac{Q^{k+1}(t_{k})-\frac{\beta^{d-k}D^{\infty}}{(4c)^{d-k-1}}}{\kappa\frac{\sin\gamma}{(\sum_{j=1}^{N-1}(\eta^{j}A(2N,j))+1)\gamma}\frac{\beta^{d-k}D^{\infty}}{2(4c)^{d-k-1}}}<\frac{\alpha}{\kappa\frac{\sin\gamma}{(\sum_{j=1}^{N-1}(\eta^{j}A(2N,j))+1)\gamma}\frac{\beta^{d+1}D^{\infty}}{(4c)^{d}}-D(\Omega)}.

For the term $t_{k}$ in (4.35), based on the assumption (4.20) for $t_{k}$ , we have

(4.38)

t_{k}<\frac{(k+1)\alpha}{\kappa\frac{\sin\gamma}{(\sum_{j=1}^{N-1}\eta^{j}A(2N,j)+1)\gamma}\frac{\beta^{d+1}D^{\infty}}{(4c)^{d}}-D(\Omega)}<\bar{t}=\frac{\alpha-D(\theta(0))}{D(\Omega)}.

Thus it yields from (4.35), (4.37) and (4.38) that the time $t_{k+1}$ can be estimated as below

(4.39)

t_{k+1}<\frac{(k+2)\alpha}{\kappa\frac{\sin\gamma}{(\sum_{j=1}^{N-1}\eta^{j}A(2N,j)+1)\gamma}\frac{\beta^{d+1}D^{\infty}}{(4c)^{d}}-D(\Omega)}.

Moreover, according to (4.17), the coupling strength $\kappa$ satisfies the following inequality

(4.40)

\kappa>\left(1+\frac{(d+1)\alpha}{\alpha-D(\theta(0))}\right)\frac{(4c)^{d}\tilde{c}}{\beta^{d+1}D^{\infty}}>\left(1+\frac{(k+2)\alpha}{\alpha-D(\theta(0))}\right)\frac{(4c)^{d}\tilde{c}}{\beta^{d+1}D^{\infty}},\quad 0\leq k\leq d-1,

thus we combine (4.39) and (4.40) to verify the ansatz (4.20) for $k+1$ in the first case, i.e., the time $t_{k+1}$ has the following estimate,

(4.41)

t_{k+1}<\bar{t}=\frac{\alpha-D(\theta(0))}{D(\Omega)}.

$\bullet$ Case 2. For another case that $Q^{k+1}(t_{k})\leq\frac{\beta^{d-k}D^{\infty}}{(4c)^{d-k-1}}$ . Similar to the analysis in (4.28), we apply (4.33) to conclude that

(4.42)

Q^{k+1}(t)\leq\frac{\beta^{d-k}D^{\infty}}{(4c)^{d-k-1}},\quad t\in[t_{k},+\infty).

This allows us to directly set $t_{k+1}=t_{k}$ . Then, according to (4.38), we know (4.39) and (4.41) hold, which finish the verification of the ansatz (4.20) in the second case.

Finally, we are ready to verify the ansatz (4.19) and (4.20) for $k+1$ . Actually, we can apply (4.36), (4.42) and Lemma 4.1 to have the upper bound of $D_{k+1}(\theta)$ on $[t_{k+1},+\infty)$ as below

(4.43)

\displaystyle D_{k+1}(\theta(t))\leq\frac{Q^{k+1}(t)}{\beta}\leq\frac{\beta^{d-k-1}D^{\infty}}{(4c)^{d-k-1}},\quad t\in[t_{k+1},+\infty),

Then we combine (4.39), (4.41) and (4.43) in Case 1 and similar analysis in Case 2 to conclude that the Claim (4.19) and (4.20) are true for $D^{k+1}(\theta)$ . ∎

Proof of Theorem 1.1: Now, we are ready to prove the main theorem. Combining Lemma 4.2, Lemma 4.3 and Lemma 4.4, we apply inductive criteria to conclude that the ansatz (4.18) –(4.20) hold for all $0\leq k\leq d$ . Then, we immediately obtain from (4.19) that there exists time $t_{d}$ such that

D(\theta(t))=D_{d}(\theta(t))\leq D^{\infty},\quad\mbox{for}\ t\in[t_{d},+\infty),

which yields the desired result in Theorem 1.1.

Remark 4.1.

In Theorem 1.1, we show that the phase diameter will enter into a small region after some finite time, which means $\cos x$ is positive after the finite time. Therefore, we can lift (1.1) to the second-order formulation, which enjoys the similar form to Cucker-Smale model with the interaction function $\cos x$ .

More precisely, we can introduce phase velocity $\omega_{i}(t):=\dot{\theta}_{i}(t)$ for each oscillator, and directly differentiate (1.1) with respect to time $t$ to derive the equivalent Cucker-Smale type second order model as below

(4.44)

\begin{cases}\displaystyle\dot{\theta}_{i}(t)=\omega_{i}(t),\quad t>0,\quad i=1,2,\ldots,N,\\ \displaystyle\dot{\omega}_{i}(t)=\kappa\sum_{j\in\mathcal{N}_{i}}\cos(\theta_{j}(t)-\theta_{i}(t))(\omega_{j}(t)-\omega_{i}(t)),\\ \displaystyle\omega_{i}(0)=\dot{\theta}_{i}(0).\end{cases}

Corollary 4.1.

Let $\theta_{i}$ be a solution to system (4.44) and suppose the assumptions in Lemma 4.2 are fulfilled. Moreover, assume that there exists time $t_{*}>0$ such that

(4.45)

D(\theta(t))\leq D^{\infty},\quad\ t\in[t_{*},+\infty),

where $D^{\infty}<\frac{\pi}{2}$ is a small positive constant. Then there exist positive constants $C_{1}$ and $C_{2}$ such that

D(\omega(t))\leq C_{1}e^{-C_{2}(t-t_{*})},\quad t>t_{*},

where $D(\omega(t))=\max_{1\leq i\leq N}\{\omega_{i}(t)\}-\min_{1\leq i\leq N}\{\omega_{i}(t)\}$ is the diameter of phase velocity.

Proof.

We can apply Theorem 1.1 and the methods and results in the work of Ha et al. [22] for Cucker-Smale model to yield the emergence of exponentially fast synchronization in (1.1) and (4.44). As the proof is almost the same as in [22], we omit the details, and we refer the readers to [22] for more infomation.
∎

5. Summary

In this paper, we presented a sufficient framework for the complete synchronization of the Kuramoto model with general network containing a spanning tree. To this end, we followed a node decomposition introduced in [22] to construct new quantities which are equivalent to phase diameters. In a large coupling strength, when the initial data is confined in an open half circle, we proved that the phase diameter of the whole ensemble will concentrate into a small region, thus we can apply the method in [22] or [11] which yielded that the complete synchronization occurs exponentially fast. However, our analytical method restricts the initial phase configuration to be confined in a half circle. It would be interesting to see whether the restriction on the initial data can be replaced by a generic one. This interesting issue will be further dealt with in our future work.

Appendix A proof of Lemma 3.3

We will split the proof into six steps. In the first step, we show that the phase diameter of $\mathcal{G}_{0}$ is bounded by $\gamma$ in a finite time interval. In the second, third and forth steps, we use induction criteria to construct the differential inequality of $Q^{0}(t)$ in the finite time interval. In the last two steps, we exploit the derived differential inequality of $Q^{0}(t)$ to conclude that phase diameter of $\mathcal{G}_{0}$ is bounded by $\gamma$ on $[0,+\infty)$ , and thus the differential inequality of $Q^{0}(t)$ obtained in second step also holds on $[0,+\infty)$ .

$\bigstar$ Step 1. We first define a set

\mathcal{B}_{0}:=\{T>0:\ D_{0}(\theta(t))<\gamma,\ \forall\ t\in[0,T)\}.

According to Lemma 2.1, the set $\mathcal{B}_{0}$ is non-empty since

D_{0}(\theta(t))<\alpha<\gamma,\quad t\in[0,\bar{t}),

which implies that $\bar{t}\in\mathcal{B}_{0}$ . In the following, we set $T^{*}=\sup\mathcal{B}_{0}$ , and prove $T^{*}=+\infty$ to finish the proof of the lemma. If not, i.e., suppose $T^{*}<+\infty$ , then we apply the continuity of $D_{0}(\theta(t))$ to have

(A.1)

D_{0}(\theta(t))<\gamma,\quad\forall\ t\in[0,T^{*}),\quad D_{0}(\theta(T^{*}))=\gamma.

In particular, we have $\bar{t}\leq T^{*}$ . According to the standard theory of ordinary differential equation, the solution to system (1.1) is analytic. Therefore, in the finite time interval $[0,T^{*})$ , any two oscillators either collide finite times or always stay together. If there are some $\theta_{i}$ and $\theta_{j}$ which always stay together in $[0,T^{*}]$ , we can view them as one oscillator and thus the total number of oscillators that we need to study can be reduced. For this more simpler situation, we can deal with it in a similar method. Therefore, we only consider the case that there is no pair of oscillators staying together in all period $[0,T^{*})$ . In this situation, only finite many collisions occur through $[0,T^{*})$ . Thus, we divide the time interval $[0,T^{*})$ into a finite union as below

[0,T^{*})=\bigcup_{l=1}^{r}J_{l},\quad J_{l}=[t_{l-1},t_{l}),

where the end point $t_{l}$ denotes the collision time. It is clear that there is no collision in the interior of $J_{l}$ . Then we pick out any time interval $J_{l}$ and assume that

(A.2)

\theta_{1}^{0}(t)\leq\theta^{0}_{2}(t)\leq\ldots\leq\theta^{0}_{N_{0}}(t),\quad t\in J_{l}.

$\bigstar$ Step 2. According to the notations in (3.9), we follow the process $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$ to construct $\bar{\theta}^{0}_{n}$ and $\underline{\theta}^{0}_{n},\ 1\leq n\leq N_{0}$ , respecively. We first consider the dynamics of $\bar{\theta}_{N_{0}}^{0}=\theta_{N_{0}}^{0}$ ,

(A.3)

\dot{\theta}_{N_{0}}^{0}(t)=\Omega^{0}_{N_{0}}+\kappa\sum_{j\in\mathcal{N}_{N_{0}}^{0}(0)}\sin(\theta^{0}_{j}-\theta^{0}_{N_{0}})\leq\Omega_{M}+\kappa\min_{j\in\mathcal{N}^{0}_{N_{0}}(0)}\sin(\theta^{0}_{j}-\theta^{0}_{N_{0}}).

The last inequality above holds because of the negative sign of $\sin(\theta^{0}_{j}(t)-\theta^{0}_{N_{0}}(t))$ due to the well-ordered assumption (A.2). For the dynamics of $\bar{\theta}^{0}_{N_{0}-1}$ , according to the process $\mathcal{A}_{1}$ and $\bar{a}^{0}_{N_{0}-1}=\eta(N_{0}+2)$ in (3.7), we have estimates for the derivative of $\bar{\theta}^{0}_{N_{0}-1}$ as follows,

	$\displaystyle\dot{\bar{\theta}}^{0}_{N_{0}-1}$	$\displaystyle=\frac{d}{dt}\left(\frac{\bar{a}^{0}_{N_{0}-1}\theta^{0}_{N_{0}}+\theta^{0}_{N_{0}-1}}{\bar{a}^{0}_{N_{0}-1}+1}\right)=\frac{\bar{a}^{0}_{N_{0}-1}}{\bar{a}^{0}_{N_{0}-1}+1}\dot{\theta}^{0}_{N_{0}}+\frac{1}{\bar{a}^{0}_{N_{0}-1}+1}\dot{\theta}^{0}_{N_{0}-1}$
		$\displaystyle\leq\frac{\bar{a}^{0}_{N_{0}-1}}{\bar{a}^{0}_{N_{0}-1}+1}\left(\Omega_{M}+\kappa\min_{j\in\mathcal{N}^{0}_{N_{0}}(0)}\sin(\theta^{0}_{j}-\theta^{0}_{N_{0}})\right)$
		$\displaystyle+\frac{1}{\bar{a}^{0}_{N_{0}-1}+1}\left(\Omega^{0}_{N_{0}-1}+\kappa\sum_{j\in\mathcal{N}^{0}_{N_{0}-1}(0)}\sin(\theta^{0}_{j}-\theta^{0}_{N_{0}-1})\right)$
(A.4)			$\displaystyle\leq\Omega_{M}+\kappa\frac{\eta(N_{0}+2)}{\bar{a}^{0}_{N_{0}-1}+1}\min_{j\in\mathcal{N}^{0}_{N_{0}}(0)}\sin(\theta^{0}_{j}-\theta^{0}_{N_{0}})$
		$\displaystyle+\kappa\frac{1}{\bar{a}^{0}_{N_{0}-1}+1}\left(\sin(\theta^{0}_{N_{0}}-\theta^{0}_{N_{0}-1})+\underset{j\leq N_{0}-1}{\sum_{j\in\mathcal{N}_{N_{0}-1}^{0}(0)}}\sin(\theta^{0}_{j}-\theta^{0}_{N_{0}})\right)$
		$\displaystyle\leq\Omega_{M}+\kappa\frac{\eta}{\bar{a}^{0}_{N_{0}-1}+1}\min_{j\in\mathcal{N}^{0}_{N_{0}}(0)}\sin(\theta^{0}_{j}-\theta^{0}_{N_{0}})+\kappa\frac{1}{\bar{a}^{0}_{N_{0}-1}+1}\underset{j\leq N_{0}-1}{\min_{j\in\mathcal{N}_{N_{0}-1}^{0}(0)}}\sin(\theta^{0}_{j}-\theta^{0}_{N_{0}-1})$
		$\displaystyle+\kappa\frac{1}{\bar{a}^{0}_{N_{0}-1}+1}\underbrace{\left(\eta\min_{j\in\mathcal{N}^{0}_{N_{0}}(0)}\sin(\theta^{0}_{j}-\theta^{0}_{N_{0}})+\sin(\theta^{0}_{N_{0}}-\theta^{0}_{N_{0}-1})\right)}_{\mathcal{I}_{2}}.$

We now show the term $\mathcal{I}_{2}$ is non-positive. We will only consider the situation $\gamma>\frac{\pi}{2}$ , and the situation $\gamma\leq\frac{\pi}{2}$ can be similarly dealt with. It is obvious that

\min_{j\in\mathcal{N}^{0}_{N_{0}}(0)}\sin(\theta^{0}_{j}-\theta^{0}_{N_{0}})\leq\sin(\theta^{0}_{\bar{k}_{N_{0}}}-\theta^{0}_{N_{0}}),\quad\bar{k}_{N_{0}}=\min_{j\in\mathcal{N}^{0}_{N_{0}}(0)}j.

Note that $\bar{k}_{N_{0}}\leq N_{0}-1$ since $\bar{\mathcal{L}}^{N_{0}}_{N_{0}}(\bar{C}_{N_{0},N_{0}})$ is not a general root. Therefore, if $0\leq\theta^{0}_{N_{0}}(t)-\theta^{0}_{\bar{k}_{N_{0}}}(t)\leq\frac{\pi}{2}$ , we immediately obtain that

0\leq\theta^{0}_{N_{0}}(t)-\theta^{0}_{N_{0}-1}(t)\leq\theta^{0}_{N_{0}}(t)-\theta^{0}_{\bar{k}_{N_{0}}}(t)\leq\frac{\pi}{2},

which implies that

\mathcal{I}_{2}\leq\eta\sin(\theta^{0}_{\bar{k}_{N_{0}}}-\theta^{0}_{N_{0}})+\sin(\theta^{0}_{N_{0}}-\theta^{0}_{N_{0}-1})\leq\sin(\theta^{0}_{\bar{k}_{N_{0}}}-\theta^{0}_{N_{0}})+\sin(\theta^{0}_{N_{0}}-\theta^{0}_{N_{0}-1})\leq 0.

On the other hand, if $\frac{\pi}{2}<\theta^{0}_{N_{0}}(t)-\theta^{0}_{\bar{k}_{N_{0}}}(t)<\gamma$ , we use the fact

\eta>\frac{1}{\sin\gamma}\quad\mbox{and}\quad\sin(\theta^{0}_{N_{0}}(t)-\theta^{0}_{\bar{k}_{N_{0}}}(t))>\sin\gamma,

to conclude that $\eta\sin(\theta^{0}_{\bar{k}_{N_{0}}}-\theta^{0}_{N_{0}})\leq-1$ . Hence, in this case, we still obtain that

\mathcal{I}_{2}\leq\eta\sin(\theta^{0}_{\bar{k}_{N_{0}}}-\theta^{0}_{N_{0}})+\sin(\theta^{0}_{N_{0}}-\theta^{0}_{N_{0}-1})\leq-1+1\leq 0.

Thus, for $t\in J_{l}$ , we combine above analysis to conclude that

(A.5)

\mathcal{I}_{2}=\eta\min_{j\in\mathcal{N}^{0}_{N_{0}}(0)}\sin(\theta^{0}_{j}-\theta^{0}_{N_{0}})+\sin(\theta^{0}_{N_{0}}-\theta^{0}_{N_{0}-1})\leq 0.

Then combining (A.4) and (A.5), we derive that

(A.6)

\dot{\bar{\theta}}^{0}_{N_{0}-1}\leq\Omega_{M}+\kappa\frac{1}{\bar{a}^{0}_{N_{0}-1}+1}\left(\eta\min_{j\in\mathcal{N}^{0}_{N_{0}}(0)}\sin(\theta^{0}_{j}-\theta^{0}_{N_{0}})+\underset{j\leq N_{0}-1}{\min_{j\in\mathcal{N}_{N_{0}-1}^{0}(0)}}\sin(\theta^{0}_{j}-\theta^{0}_{N_{0}-1})\right).

$\bigstar$ Step 3. Now we apply the induction principle to cope with $\bar{\theta}^{0}_{n}$ in (3.9), which are construced in the iteration process $\mathcal{A}_{1}$ . We will prove for $1\leq n\leq N_{0}$ that,

(A.7)

\dot{\bar{\theta}}^{0}_{n}(t)\leq\Omega_{M}+\kappa\frac{1}{\bar{a}^{0}_{n}+1}\sum_{i=n}^{N_{0}}\left(\eta^{i-n}\underset{j\leq i}{\min_{j\in\mathcal{N}_{i}^{0}(0)}}\sin(\theta^{0}_{j}(t)-\theta^{0}_{i}(t))\right).

In fact, (A.7) already holds for $n=N_{0},N_{0}-1$ from (A.3) and (A.6). Then, suppose that for $n\leq l\leq N_{0}$ where $2\leq n\leq N_{0}$ , we have

(A.8)

\dot{\bar{\theta}}^{0}_{l}(t)\leq\Omega_{M}+\kappa\frac{1}{\bar{a}^{0}_{l}+1}\sum_{i=l}^{N_{0}}\left(\eta^{i-l}\underset{j\leq i}{\min_{j\in\mathcal{N}_{i}^{0}(0)}}\sin(\theta^{0}_{j}(t)-\theta^{0}_{i}(t))\right),

we next verify that (A.7) still holds for $l=n-1$ . According to the Algorithm $\mathcal{A}_{1}$ and (A.8), the dynamics of the quantity $\bar{\theta}^{0}_{n-1}(t)$ has following estimates,

	$\displaystyle\dot{\bar{\theta}}^{0}_{n-1}$	$\displaystyle=\frac{d}{dt}\left(\frac{\bar{a}^{0}_{n-1}\bar{\theta}^{0}_{n}+\theta^{0}_{n-1}}{\bar{a}^{0}_{n-1}+1}\right)=\frac{\bar{a}^{0}_{n-1}}{\bar{a}^{0}_{n-1}+1}\dot{\bar{\theta}}^{0}_{n}+\frac{1}{\bar{a}^{0}_{n-1}+1}\dot{\theta}^{0}_{n-1}$
		$\displaystyle\leq\frac{\bar{a}^{0}_{n-1}}{\bar{a}^{0}_{n-1}+1}\left[\Omega_{M}+\kappa\frac{1}{\bar{a}^{0}_{n}+1}\sum_{i=n}^{N_{0}}\left(\eta^{i-n}\underset{j\leq i}{\min_{j\in\mathcal{N}_{i}^{0}(0)}}\sin(\theta^{0}_{j}-\theta^{0}_{i})\right)\right]$
		$\displaystyle+\frac{1}{\bar{a}^{0}_{n-1}+1}\left(\Omega^{0}_{n-1}+\kappa\sum_{j\in\mathcal{N}^{0}_{n-1}(0)}\sin(\theta^{0}_{j}-\theta^{0}_{n-1})\right)$
		$\displaystyle\leq\Omega_{M}+\kappa\frac{\eta(2N_{0}-n+2)}{\bar{a}^{0}_{n-1}+1}\sum_{i=n}^{N_{0}}\left(\eta^{i-n}\underset{j\leq i}{\min_{j\in\mathcal{N}_{i}^{0}(0)}}\sin(\theta^{0}_{j}-\theta^{0}_{i})\right)$
		$\displaystyle+\kappa\frac{1}{\bar{a}^{0}_{n-1}+1}\left(\underset{j\leq n-1}{\sum_{j\in\mathcal{N}^{0}_{n-1}(0)}}\sin(\theta^{0}_{j}-\theta^{0}_{n-1})+\underset{j>n-1}{\sum_{j\in\mathcal{N}^{0}_{n-1}(0)}}\sin(\theta^{0}_{j}-\theta^{0}_{n-1})\right)$
(A.9)			$\displaystyle\leq\Omega_{M}+\underbrace{\kappa\frac{\eta N_{0}}{\bar{a}^{0}_{n-1}+1}\sum_{i=n}^{N_{0}}\left(\eta^{i-n}\underset{j\leq i}{\min_{j\in\mathcal{N}_{i}^{0}(0)}}\sin(\theta^{0}_{j}-\theta^{0}_{i})\right)}_{\mathcal{I}_{3}}$
		$\displaystyle+\kappa\frac{\eta}{\bar{a}^{0}_{n-1}+1}\sum_{i=n}^{N_{0}}\left(\eta^{i-n}\underset{j\leq i}{\min_{j\in\mathcal{N}_{i}^{0}(0)}}\sin(\theta^{0}_{j}-\theta^{0}_{i})\right)+\kappa\frac{1}{\bar{a}^{0}_{n-1}+1}\underset{j\leq n-1}{\min_{j\in\mathcal{N}_{n-1}^{0}(0)}}\sin(\theta^{0}_{j}-\theta^{0}_{n-1})$
		$\displaystyle+\frac{\kappa}{\bar{a}^{0}_{n-1}+1}\left(\underbrace{\eta(N_{0}-n+1)\sum_{i=n}^{N_{0}}\left(\eta^{i-n}\underset{j\leq i}{\min_{j\in\mathcal{N}_{i}^{0}(0)}}\sin(\theta^{0}_{j}-\theta^{0}_{i})\right)+\underset{j>n-1}{\sum_{j\in\mathcal{N}^{0}_{n-1}(0)}}\sin(\theta^{0}_{j}-\theta^{0}_{n-1})}_{\mathcal{I}_{4}}\right).$

In above estimates, we used the fact that

\bar{a}^{0}_{n-1}=\eta(2N_{0}-n+2)(\bar{a}^{0}_{n}+1),\quad\underset{j\leq n-1}{\sum_{j\in\mathcal{N}^{0}_{n-1}(0)}}\sin(\theta^{0}_{j}-\theta^{0}_{n-1})\leq\underset{j\leq n-1}{\min_{j\in\mathcal{N}_{n-1}^{0}(0)}}\sin(\theta^{0}_{j}-\theta^{0}_{n-1}).

It is obvious that $\mathcal{I}_{3}\leq 0$ , and thus we can neglect it. In the subsequence, we will deal with $\mathcal{I}_{4}$ and prove that

(A.10)

\mathcal{I}_{4}\leq 0.

In fact, according to Lemma 3.1, we directly have

(A.11)

\sum_{i=n}^{N_{0}}\left(\eta^{i-n}\underset{j\leq i}{\min_{j\in\mathcal{N}_{i}^{0}(0)}}\sin(\theta^{0}_{j}-\theta^{0}_{i})\right)\leq\sin(\theta^{0}_{\bar{k}_{n}}-\theta^{0}_{N_{0}}),\quad\bar{k}_{n}=\min_{j\in\bigcup_{i=n}^{N_{0}}\mathcal{N}^{0}_{i}(0)}j.

Similar to the analysis in (A.5), we only deal with $\mathcal{I}_{4}$ under the situation $\gamma>\frac{\pi}{2}$ . Now we consider two cases according to the relation of size between $\theta^{0}_{N_{0}}-\theta^{0}_{\bar{k}_{n}}$ and $\frac{\pi}{2}$ .
$\diamond$ For the case that $0\leq\theta^{0}_{N_{0}}(t)-\theta^{0}_{\bar{k}_{n}}(t)\leq\frac{\pi}{2}$ , we immediately obtain that for $j\in\mathcal{N}^{0}_{n-1}(0),\ j>n-1$ ,

0\leq\theta^{0}_{j}(t)-\theta^{0}_{n-1}(t)\leq\theta^{0}_{N_{0}}(t)-\theta^{0}_{n-1}(t)\leq\theta^{0}_{N_{0}}(t)-\theta^{0}_{\bar{k}_{n}}(t)\leq\frac{\pi}{2},

where we use the fact that $\bar{k}_{n}\leq n-1$ as $\bar{\mathcal{L}}^{N_{0}}_{n}(\bar{C}_{n,N_{0}})$ is not a general root. Then, we combine (A.11) to have

	$\displaystyle\mathcal{I}_{4}$	$\displaystyle\leq\eta(N_{0}-n+1)\sin(\theta^{0}_{\bar{k}_{n}}-\theta^{0}_{N_{0}})+\underset{j>n-1}{\sum_{j\in\mathcal{N}^{0}_{n-1}(0)}}\sin(\theta^{0}_{j}-\theta^{0}_{n-1})$
		$\displaystyle\leq(N_{0}-n+1)\sin(\theta^{0}_{\bar{k}_{n}}-\theta^{0}_{N_{0}})+(N_{0}-n+1)\sin(\theta^{0}_{N_{0}}(t)-\theta^{0}_{n-1}(t))\leq 0,$

where we apply the fact $\eta>1$ and the monotone property of sine function in $[0,\frac{\pi}{2}]$ .
$\diamond$ For another case that $\frac{\pi}{2}<\theta^{0}_{N_{0}}(t)-\theta^{0}_{\bar{k}_{n}}(t)<\gamma$ , it is known that

\eta>\frac{1}{\sin\gamma}\quad\mbox{and}\quad\sin(\theta^{0}_{N_{0}}(t)-\theta^{0}_{\bar{k}_{n}}(t))>\sin\gamma,

which means $\eta\sin(\theta^{0}_{\bar{k}_{n}}-\theta^{0}_{N_{0}})\leq-1$ . Thus we obtain that

	$\displaystyle\mathcal{I}_{4}$	$\displaystyle\leq\eta(N_{0}-n+1)\sin(\theta^{0}_{\bar{k}_{n}}-\theta^{0}_{N_{0}})+\underset{j>n-1}{\sum_{j\in\mathcal{N}^{0}_{n-1}(0)}}\sin(\theta^{0}_{j}-\theta^{0}_{n-1})$
		$\displaystyle\leq-(N_{0}-n+1)+(N_{0}-n+1)=0.$

Therefore, (A.10) holds at time $t\in J_{l}$ . Now we combine (A.9) and (A.10) to get

	$\displaystyle\dot{\bar{\theta}}^{0}_{n-1}$	$\displaystyle\leq\Omega_{M}+\kappa\frac{1}{\bar{a}^{0}_{n-1}+1}\left[\sum_{i=n}^{N_{0}}\left(\eta^{i-(n-1)}\underset{j\leq i}{\min_{j\in\mathcal{N}_{i}^{0}(0)}}\sin(\theta^{0}_{j}-\theta^{0}_{i})\right)+\underset{j\leq n-1}{\min_{j\in\mathcal{N}_{n-1}^{0}(0)}}\sin(\theta^{0}_{j}-\theta^{0}_{n-1})\right]$
		$\displaystyle=\Omega_{M}+\kappa\frac{1}{\bar{a}^{0}_{n-1}+1}\sum_{i=n-1}^{N_{0}}\left(\eta^{i-(n-1)}\underset{j\leq i}{\min_{j\in\mathcal{N}_{i}^{0}(0)}}\sin(\theta^{0}_{j}-\theta^{0}_{i})\right).$

So far, we complete the proof of the claim (A.7).

$\bigstar$ Step 4. Now, we set $n=1$ in (A.7) and apply Lemma 3.1 to have

(A.12)		$\displaystyle\dot{\bar{\theta}}^{0}_{1}(t)$	$\displaystyle\leq\Omega_{M}+\kappa\frac{1}{\bar{a}^{0}_{1}+1}\sum_{i=1}^{N_{0}}\left(\eta^{i-1}\underset{j\leq i}{\min_{j\in\mathcal{N}_{i}^{0}(0)}}\sin(\theta^{0}_{j}(t)-\theta^{0}_{i}(t))\right)$
(A.12)			$\displaystyle\leq\Omega_{M}+\kappa\frac{1}{\bar{a}^{0}_{1}+1}\sin(\theta^{0}_{\bar{k}_{1}}-\theta^{0}_{N_{0}})=\Omega_{M}+\kappa\frac{1}{\bar{a}^{0}_{1}+1}\sin(\theta^{0}_{1}-\theta^{0}_{N_{0}}),$

where $\bar{k}_{1}=\min_{j\in\bigcup_{i=1}^{N_{0}}\mathcal{N}^{0}_{i}(0)}j=1$ due to the strong connectivity of $\mathcal{G}_{0}$ . Similarly, we can follow the process $\mathcal{A}_{2}$ to construct $\underline{\theta}^{0}_{k}$ in (3.9) until $k=N_{0}$ . Then, we can apply the similar argument as before to obtain that,

(A.13)		$\displaystyle\frac{d}{dt}\underline{\theta}^{0}_{N_{0}}(t)$	$\displaystyle\geq\Omega_{m}+\kappa\frac{1}{\underline{a}^{0}_{N_{0}}+1}\sum_{i=1}^{N_{0}}\left(\eta^{N_{0}-i}\underset{j\geq i}{\max_{j\in\mathcal{N}_{i}^{0}(0)}}\sin(\theta^{0}_{j}(t)-\theta^{0}_{i}(t))\right)$
(A.13)			$\displaystyle\geq\Omega_{m}+\kappa\frac{1}{\underline{a}^{0}_{N_{0}}+1}\sin(\theta^{0}_{\underline{k}_{N_{0}}}-\theta^{0}_{1})=\Omega_{m}+\kappa\frac{1}{\bar{a}^{0}_{1}+1}\sin(\theta^{0}_{N_{0}}-\theta^{0}_{1}),$

where we use the strong connectivity and the fact that $\underline{k}_{N_{0}}=\max_{j\in\bigcup_{i=1}^{N_{0}}\mathcal{N}^{0}_{i}(0)}j=N_{0}$ and $\underline{a}^{0}_{N_{0}}=\bar{a}^{0}_{1}$ . Then we recall the notations $\bar{\theta}_{0}=\bar{\theta}^{0}_{1}$ and $\underline{\theta}_{0}=\underline{\theta}^{0}_{N_{0}}$ , and combine (A.12) and (A.13) to obtain that

	$\displaystyle\dot{Q}^{0}(t)$	$\displaystyle=\frac{d}{dt}(\bar{\theta}_{0}-\underline{\theta}_{0})\leq D(\Omega)-\kappa\frac{2}{\bar{a}^{0}_{1}+1}\sin(\theta^{0}_{N_{0}}-\theta^{0}_{1})$
		$\displaystyle\leq D(\Omega)-\kappa\frac{1}{\sum_{j=1}^{N_{0}-1}(\eta^{j}A(2N_{0},j))+1}\sin(\theta^{0}_{N_{0}}-\theta^{0}_{1}),$

In the above estimates, we use the property

\bar{a}^{0}_{1}=\sum_{j=1}^{N_{0}-1}(\eta^{j}A(2N_{0},j)).

Since the function $\frac{\sin x}{x}$ is monotonically decreasing in $(0,\pi]$ , we apply (A.1) to obtain that

\sin(\theta^{0}_{N_{0}}-\theta^{0}_{1})\geq\frac{\sin\gamma}{\gamma}(\theta^{0}_{N_{0}}-\theta^{0}_{1}).

Moreover, due to the formula $Q^{0}(t)\leq\theta^{0}_{N_{0}}(t)-\theta^{0}_{1}(t)$ , we have

(A.14)		$\displaystyle\dot{Q}^{0}(t)$	$\displaystyle\leq D(\Omega)-\kappa\frac{1}{\sum_{j=1}^{N_{0}-1}(\eta^{j}A(2N_{0},j))+1}\frac{\sin\gamma}{\gamma}(\theta^{0}_{N_{0}}-\theta^{0}_{1})$
(A.14)			$\displaystyle\leq D(\Omega)-\kappa\frac{1}{\sum_{j=1}^{N_{0}-1}(\eta^{j}A(2N_{0},j))+1}\frac{\sin\gamma}{\gamma}Q^{0}(t),\quad t\in J_{l}.$

Note that the constructed quantity $Q^{0}(t)=\bar{\theta}_{0}(t)-\underline{\theta}_{0}(t)$ is Lipschitz continuous on $[0,T^{*})$ . Moreover, the above analysis does not depend on the time interval $J_{l},\ l=1,2,\ldots,r$ , thus the differential inequality (A.14) holds almost everywhere on $[0,T^{*})$ .

$\bigstar$ Step 5. For a given sufficiently small $D^{\infty}<\min\{\frac{\pi}{2},\alpha\}$ , based on the assumption of the coupling strength in (3.12), we have

(A.15)

\kappa>\left(1+\frac{\alpha}{\alpha-D(\theta(0))}\right)\frac{\tilde{c}}{\beta D^{\infty}}>\frac{1}{\beta D^{\infty}}\frac{D(\Omega)(\sum_{j=1}^{N_{0}-1}\eta^{j}A(2N_{0},j)+1)\gamma}{\sin\gamma}

where

\tilde{c}=\frac{D(\Omega)(\sum_{j=1}^{N_{0}-1}\eta^{j}A(2N_{0},j)+1)\gamma}{\sin\gamma}.

Next we study the upper bound of $Q^{0}(t)$ in the period $[0,T^{*})$ . Define

M_{0}=\max\left\{Q^{0}(0),\beta D^{\infty}\right\}.

We claim that

(A.16)

Q^{0}(t)\leq M_{0}\quad\mbox{for all}\ t\in[0,T^{*}).

Suppose not, then there exists some $\tilde{t}\in[0,T^{*})$ such that $Q^{0}(\tilde{t})>M_{0}$ . We construct a set

\mathcal{C}_{0}:=\{t<\tilde{t}\ |\ Q^{0}(t)\leq M_{0}\}.

Since $0\in\mathcal{C}_{0}$ , the set $\mathcal{C}_{0}$ is not empty. Then we denote $t^{*}=\sup\mathcal{C}_{0}$ , and immediately obtain that

(A.17)

t^{*}<\tilde{t},\quad Q^{0}(t^{*})=M_{0},\quad Q^{0}(t)>M_{0}\quad\mbox{for}\ t\in(t^{*},\tilde{t}].

According to the construction of $M_{0}$ , (A.15) and (A.17) , it is known the following estimates hold for $t\in(t^{*},\tilde{t}]$ ,

		$\displaystyle D(\Omega)-\kappa\frac{1}{\sum_{j=1}^{N_{0}-1}(\eta^{j}A(2N_{0},j))+1}\frac{\sin\gamma}{\gamma}Q^{0}(t)$
		$\displaystyle<D(\Omega)-\kappa\frac{1}{\sum_{j=1}^{N_{0}-1}(\eta^{j}A(2N_{0},j))+1}\frac{\sin\gamma}{\gamma}\beta D^{\infty}<0.$

Then, we apply the above inequality and integrate on the both sides of (A.14) from $t^{*}$ to $\tilde{t}$ to get

0<Q^{0}(\tilde{t})-M_{0}=Q^{0}(\tilde{t})-Q^{0}(t^{*})\leq\int_{t^{*}}^{\tilde{t}}(D(\Omega)-\kappa\frac{1}{\sum_{j=1}^{N_{0}-1}(\eta^{j}A(2N_{0},j))+1}\frac{\sin\gamma}{\gamma}Q^{0}(t))dt<0,

which is an obvious contradiction. Thus we complete the proof of (A.16).

$\bigstar$ Step 6. Now, we are ready to show the contradiction to (A.1), and thus it implies that $T^{*}=+\infty$ . In fact, due to the fact that $\beta<1,D^{\infty}<\alpha$ and $Q^{0}(0)\leq D_{0}(\theta(0))<\alpha$ , we have

Q^{0}(t)\leq M_{0}=\max\left\{Q^{0}(0),\beta D^{\infty}\right\}<\alpha,\quad t\in[0,T^{*}).

Then we apply the relation $\beta D_{0}(\theta(t))\leq Q^{0}(t)$ given in Lemma 3.2 and the assumption $\eta>\frac{2}{1-\frac{\alpha}{\gamma}}$ in (3.12) to obtain that

D_{0}(\theta(t))\leq\frac{Q^{0}(t)}{\beta}<\frac{\alpha}{\beta}<\gamma,\quad t\in[0,T^{*})\quad\mbox{where}\ \beta=1-\frac{2}{\eta}.

As $D_{0}(\theta(t))$ is continuous, we have

D_{0}(\theta(T^{*}))=\lim_{t\to(T^{*})^{-}}D_{0}(\theta(t))\leq\frac{\alpha}{\beta}<\gamma,

which contradicts to the situation that $D_{0}(\theta(T^{*}))=\gamma$ in (A.1). Therefore, we derive that $T^{*}=+\infty$ , which yields that

(A.18)

D_{0}(\theta(t))<\gamma,\quad\mbox{for all}\ t\in[0,+\infty).

Then for any finite time $T>0$ , we apply (A.18) and repeat the same argument in the second, third, forth steps to obtain the dynamics of $Q^{0}(t)$ in (A.14) holds on $[0,T)$ . This yields the following differential inequality of $Q^{0}$ on the whole time interval:

\dot{Q}^{0}(t)\leq D(\Omega)-\kappa\frac{1}{\sum_{j=1}^{N_{0}-1}(\eta^{j}A(2N_{0},j))+1}\frac{\sin\gamma}{\gamma}Q^{0}(t),\quad t\in[0,+\infty).

Thus, we complete the proof of this Lemma. ∎

Appendix B proof of step 1 in lemma 4.3

We will show the detailed proof of Step 1 in Lemma 4.3. Now we pick out any interval $J_{l}$ with $1\leq l\leq r$ , where the orders of both $\{\bar{\theta}_{i}\}_{i=0}^{k+1}$ and $\{\underline{\theta}_{i}\}_{i=0}^{k+1}$ are preseved and the order of oscillators in each subdigraph $\mathcal{G}_{i}$ with $0\leq i\leq k+1$ will not change in each time interval. Then, we consider four cases according to the possibility of relative position between $\bigcup_{i=0}^{k}\mathcal{G}$ and $\mathcal{G}_{k+1}$ .

B.1. Case 1

Consider the case that

\max_{0\leq i\leq k+1}\{\bar{\theta}_{i}\}=\max_{0\leq i\leq k}\{\bar{\theta}_{i}\},\quad\min_{0\leq i\leq k+1}\{\underline{\theta}_{i}\}=\min_{0\leq i\leq k}\{\underline{\theta}_{i}\}\quad\mbox{in}\ J_{l}.

Refer to caption — Figure 1. The comparison relation in Case 1

The comparison relation in this case is showed in Figure 1. In this case, $Q^{k+1}(t)=Q^{k}(t)$ , by the assumption of induction principle and from (4.18), we obviously have

	$\displaystyle\frac{d}{dt}Q^{k+1}(t)$	$\displaystyle=\frac{d}{dt}Q^{k}(t),\qquad\qquad t\in J_{l},$
		$\displaystyle\leq D(\Omega)-\frac{\kappa}{\sum_{j=1}^{N-1}(\eta^{j}A(2N,j))+1}\frac{\sin\gamma}{\gamma}Q^{k}(t)+\kappa(2N+1)D_{k-1}(\theta(t))$
		$\displaystyle\leq D(\Omega)-\frac{\kappa}{\sum_{j=1}^{N-1}(\eta^{j}A(2N,j))+1}\frac{\sin\gamma}{\gamma}Q^{k+1}(t)+\kappa(2N+1)D_{k}(\theta(t)),$

where we use $D_{k-1}(\theta(t))\leq D_{k}(\theta(t))$ . Thus we obtain the dynamics for $Q^{k+1}(t)$ in (4.18) on $J_{l}$ .

B.2. Case 2

Consider the case that

\max_{0\leq i\leq k+1}\{\bar{\theta}_{i}\}=\bar{\theta}_{k+1},\quad\min_{0\leq i\leq k+1}\{\underline{\theta}_{i}\}=\underline{\theta}_{k+1}\quad\mbox{in}\ J_{l}.

The comparison relation in this case is presented in Figure 2. For this case, we assume that

\theta^{k+1}_{1}\leq\theta^{k+1}_{2}\leq\dots\leq\theta^{k+1}_{N_{k+1}},\quad\mbox{on}\ J_{l}.

$\bigstar$ Step 1. Similar to formula (A.7), we claim that for $1\leq n\leq N_{k+1}$ , the following inequalities hold

(B.1)		$\displaystyle\frac{d}{dt}\bar{\theta}^{k+1}_{n}(t)\leq$	$\displaystyle\ \Omega_{M}+\kappa S_{k}D_{k}(\theta(t))$
(B.1)			$\displaystyle+\kappa\frac{1}{\bar{a}^{k+1}_{n}+1}\sum_{i=n}^{N_{k+1}}\left(\eta^{i-n}\underset{j\leq i}{\min_{j\in\mathcal{N}_{i}^{k+1}(k+1)}}\sin(\theta^{k+1}_{j}(t)-\theta^{k+1}_{i}(t))\right),$

where $S_{k}=\sum_{i=0}^{k}N_{i}$ . In the subsequence, we will prove the claim (B.1) by induction.

$\bigstar$ Step 1.1. As an initial step, we first verify that (B.1) holds for $n=N_{k+1}$ . In fact, the dynamics of $\bar{\theta}^{k+1}_{N_{k+1}}$ is given by

(B.2)		$\displaystyle\frac{d}{dt}\bar{\theta}^{k+1}_{N_{k+1}}=\frac{d}{dt}\theta^{k+1}_{N_{k+1}}=$	$\displaystyle\ \Omega^{k+1}_{N_{k+1}}+\underbrace{\kappa\sum_{j\in\mathcal{N}_{N_{k+1}}^{k+1}(k+1)}\sin(\theta^{k+1}_{j}-\theta^{k+1}_{N_{k+1}})}_{\mathcal{I}_{1}}$
(B.2)			$\displaystyle+\underbrace{\kappa\sum_{l=0}^{k}\sum_{j\in\mathcal{N}_{N_{k+1}}^{k+1}(l)}\sin(\theta^{l}_{j}-\theta^{k+1}_{N_{k+1}})}_{\mathcal{I}_{2}}.$

$\diamond$ Estimates on $\mathbf{\mathcal{I}_{1}}$ in (B.2). We know that $\theta^{k+1}_{N_{k+1}}$ is the largest phase among $\mathcal{G}_{k+1}$ , and all the oscillators in $\bigcup_{i=0}^{k+1}\mathcal{G}_{i}$ stay in half circle before $T^{*}$ . Therefore, it is clear that

\sin(\theta^{k+1}_{j}-\theta^{k+1}_{N_{k+1}})\leq 0,\quad\mbox{for}\ j\in\mathcal{N}_{N_{k+1}}^{k+1}(k+1).

Then we have

(B.3)

\sum_{j\in\mathcal{N}_{N_{k+1}}^{k+1}(k+1)}\sin(\theta^{k+1}_{j}-\theta^{k+1}_{N_{k+1}})\leq\min_{j\in\mathcal{N}^{k+1}_{N_{k+1}}(k+1)}\sin(\theta^{k+1}_{j}-\theta^{k+1}_{N_{k+1}}).

$\diamond$ Estimates on $\mathbf{\mathcal{I}_{2}}$ in (B.2). For $\theta^{l}_{j}$ which is the neighbor of $\theta^{k+1}_{N_{k+1}}$ in $\mathcal{G}_{l}$ with $0\leq l\leq k$ , i.e., $j\in\mathcal{N}_{N_{k+1}}^{k+1}(l)$ , there are two possible orderings between $\theta^{l}_{j}$ and $\theta^{k+1}_{N_{k+1}}$ :

If $\theta^{l}_{j}\leq\theta^{k+1}_{N_{k+1}}$ , we immediately have

\sin(\theta^{l}_{j}-\theta^{k+1}_{N_{k+1}})\leq 0.

If $\theta^{l}_{j}>\theta^{k+1}_{N_{k+1}}$ , according to the fact that

(B.4)

\theta^{i}_{N_{i}}\geq\bar{\theta}_{i}\geq\underline{\theta}_{i}\geq\theta^{i}_{1},\quad 0\leq i\leq d,

we immediately obtain

(B.5)

\theta^{k+1}_{N_{k+1}}\geq\bar{\theta}_{k+1}=\max_{0\leq i\leq k+1}\{\bar{\theta}_{i}\}\geq\max_{0\leq i\leq k}\{\bar{\theta}_{i}\}\geq\min_{0\leq i\leq k}\{\underline{\theta}_{i}\}\geq\min_{0\leq i\leq k}\min_{1\leq j\leq N_{i}}\{\theta^{i}_{j}\}.

Thus we use the property of $\sin x\leq x,\ x\geq 0$ and (B.5) to get

(B.6)

\sin(\theta^{l}_{j}-\theta^{k+1}_{N_{k+1}})\leq\theta^{l}_{j}-\theta^{k+1}_{N_{k+1}}\leq\theta^{l}_{j}-\min_{0\leq i\leq k}\min_{1\leq j\leq N_{i}}\{\theta^{i}_{j}\}\leq D_{k}(\theta(t)).

Therefore, combining the above discussion, (B.2) and (B.3), we obtain that

\frac{d}{dt}\bar{\theta}^{k+1}_{N_{k+1}}\leq\Omega_{M}+\kappa\min_{j\in\mathcal{N}^{k+1}_{N_{k+1}}(k+1)}\sin(\theta^{k+1}_{j}-\theta^{k+1}_{N_{k+1}})+\kappa S_{k}D_{k}(\theta(t)).

Thus we have that (B.1) holds for $n=N_{k+1}$ .

$\bigstar$ Step 1.2. Next, we will apply inductive criteria. We assume that (B.1) holds for $n$ with $2\leq n\leq N_{k+1}$ , and we will show that (B.1) holds for $n-1$ . According to the process $\mathcal{A}_{1}$ , we have

(B.7)	$\displaystyle\dot{\bar{\theta}}^{k+1}_{n-1}$	$\displaystyle=\frac{d}{dt}\left(\frac{\bar{a}^{k+1}_{n-1}\bar{\theta}^{k+1}_{n}+\theta^{k+1}_{n-1}}{\bar{a}^{k+1}_{n-1}+1}\right)=\frac{\bar{a}^{k+1}_{n-1}}{\bar{a}^{k+1}_{n-1}+1}\dot{\bar{\theta}}^{k+1}_{n}+\frac{1}{\bar{a}^{k+1}_{n-1}+1}\dot{\theta}^{k+1}_{n-1}$
		$\displaystyle\leq\frac{\bar{a}^{k+1}_{n-1}}{\bar{a}^{k+1}_{n-1}+1}\left[\Omega_{M}+\kappa\frac{1}{\bar{a}^{k+1}_{n}+1}\sum_{i=n}^{N_{k+1}}\left(\eta^{i-n}\underset{j\leq i}{\min_{j\in\mathcal{N}_{i}^{k+1}(k+1)}}\sin(\theta^{k+1}_{j}(t)-\theta^{k+1}_{i}(t))\right)\right]$
		$\displaystyle+\frac{\bar{a}^{k+1}_{n-1}}{\bar{a}^{k+1}_{n-1}+1}\kappa S_{k}D_{k}(\theta(t))$
		$\displaystyle+\frac{1}{\bar{a}^{k+1}_{n-1}+1}\left(\Omega^{k+1}_{n-1}+\kappa\sum_{j\in\mathcal{N}_{n-1}^{k+1}(k+1)}\sin(\theta^{k+1}_{j}-\theta^{k+1}_{n-1})+\kappa\sum_{l=0}^{k}\sum_{j\in\mathcal{N}_{n-1}^{k+1}(l)}\sin(\theta^{l}_{j}-\theta^{k+1}_{n-1})\right)$
		$\displaystyle\leq\Omega_{M}+\underbrace{\kappa\frac{\eta(2N-N_{k+1}-S_{k})}{\bar{a}^{k+1}_{n-1}+1}\sum_{i=n}^{N_{k+1}}\left(\eta^{i-n}\underset{j\leq i}{\min_{j\in\mathcal{N}_{i}^{k+1}(k+1)}}\sin(\theta^{k+1}_{j}(t)-\theta^{k+1}_{i}(t))\right)}_{\mathcal{I}_{11}}$
		$\displaystyle+\kappa\frac{\eta(N_{k+1}-n+2+S_{k})}{\bar{a}^{k+1}_{n-1}+1}\sum_{i=n}^{N_{k+1}}\left(\eta^{i-n}\underset{j\leq i}{\min_{j\in\mathcal{N}_{i}^{k+1}(k+1)}}\sin(\theta^{k+1}_{j}(t)-\theta^{k+1}_{i}(t))\right)$
		$\displaystyle+\kappa\frac{1}{\bar{a}^{k+1}_{n-1}+1}\left(\underbrace{\underset{j\leq n-1}{\sum_{j\in\mathcal{N}_{n-1}^{k+1}(k+1)}}\sin(\theta^{k+1}_{j}-\theta^{k+1}_{n-1})}_{\mathcal{I}_{12}}+\underbrace{\underset{j>n-1}{\sum_{j\in\mathcal{N}_{n-1}^{k+1}(k+1)}}\sin(\theta^{k+1}_{j}-\theta^{k+1}_{n-1})}_{\mathcal{I}_{13}}\right)$
		$\displaystyle+\kappa\frac{1}{\bar{a}^{k+1}_{n-1}+1}\underbrace{\sum_{l=0}^{k}\sum_{j\in\mathcal{N}_{n-1}^{k+1}(l)}\sin(\theta^{l}_{j}-\theta^{k+1}_{n-1})}_{\mathcal{I}_{14}}+\frac{\bar{a}^{k+1}_{n-1}}{\bar{a}^{k+1}_{n-1}+1}\kappa S_{k}D_{k}(\theta(t)),$

where we use the fact

\bar{a}^{k+1}_{n-1}=\eta(2N-n+2)(\bar{a}^{k+1}_{n}+1),\quad 2N-n+2=(N_{k+1}-n+2+S_{k})+2N-N_{k+1}-S_{k}.

$\diamond$ Estimates on $\mathbf{\mathcal{I}_{11}}$ in (B.7). We apply the strong connectivity of $\mathcal{G}_{k+1}$ and Lemma 3.1 to obtain that

(B.8)

\sum_{i=n}^{N_{k+1}}\left(\eta^{i-n}\underset{j\leq i}{\min_{j\in\mathcal{N}_{i}^{k+1}(k+1)}}\sin(\theta^{k+1}_{j}(t)-\theta^{k+1}_{i}(t))\right)\leq\sin(\theta^{k+1}_{\bar{k}_{n}}-\theta^{k+1}_{N_{k+1}}),

where $\bar{k}_{n}=\min_{j\in\bigcup_{i=n}^{N_{k+1}}\mathcal{N}^{k+1}_{i}(k+1)}j\leq n-1$ . And it is obvious that $\mathcal{I}_{11}\leq 0$ .

$\diamond$ Estimates on $\mathbf{\mathcal{I}_{12}}$ in (B.7). For the term $\mathcal{I}_{12}$ , we apply direct calculation to obtain that

(B.9)

\mathcal{I}_{12}=\underset{j\leq n-1}{\sum_{j\in\mathcal{N}_{n-1}^{k+1}(k+1)}}\sin(\theta^{k+1}_{j}-\theta^{k+1}_{n-1})\leq\underset{j\leq n-1}{\min_{j\in\mathcal{N}_{n-1}^{k+1}(k+1)}}\sin(\theta^{k+1}_{j}-\theta^{k+1}_{n-1}).

$\diamond$ Estimates on $\mathbf{\mathcal{I}_{13}}$ in (B.7). For the term $\mathcal{I}_{13}$ , the estimate is almost the same as (A.10). Without loss of generality, we only deal with $\mathcal{I}_{13}$ under the situation $\gamma>\frac{\pi}{2}$ . According to (B.8), we consider two cases depending on comparison between $\theta^{k+1}_{N_{k+1}}-\theta^{k+1}_{\bar{k}_{n}}$ and $\frac{\pi}{2}$ .

(i) For the first case that $0\leq\theta^{k+1}_{N_{k+1}}-\theta^{k+1}_{\bar{k}_{n}}\leq\frac{\pi}{2}$ , we immediately obtain that for $j\in\mathcal{N}^{k+1}_{n-1}(k+1),\ j>n-1$ ,

(B.10)

0\leq\theta^{k+1}_{j}(t)-\theta^{k+1}_{n-1}(t)\leq\theta^{k+1}_{N_{k+1}}(t)-\theta^{k+1}_{n-1}(t)\leq\theta^{k+1}_{N_{k+1}}(t)-\theta^{k+1}_{\bar{k}_{n}}(t)\leq\frac{\pi}{2}.

Then it is known from (B.8), (B.10) and $\eta>2$ that

		$\displaystyle\eta(N_{k+1}-n+1)\sum_{i=n}^{N_{k+1}}\left(\eta^{i-n}\underset{j\leq i}{\min_{j\in\mathcal{N}_{i}^{k+1}(k+1)}}\sin(\theta^{k+1}_{j}(t)-\theta^{k+1}_{i}(t))\right)+\mathcal{I}_{13}$
		$\displaystyle\leq\eta(N_{k+1}-n+1)\sin(\theta^{k+1}_{\bar{k}_{n}}-\theta^{k+1}_{N_{k+1}})+\underset{j>n-1}{\sum_{j\in\mathcal{N}_{n-1}^{k+1}(k+1)}}\sin(\theta^{k+1}_{j}-\theta^{k+1}_{n-1})$
		$\displaystyle\leq(N_{k+1}-n+1)\sin(\theta^{k+1}_{\bar{k}_{n}}-\theta^{k+1}_{N_{k+1}})+(N_{k+1}-n+1)\sin(\theta^{k+1}_{N_{k+1}}-\theta^{k+1}_{n-1})$
		$\displaystyle\leq 0.$

(ii) For the second case that $\frac{\pi}{2}<\theta^{k+1}_{N_{k+1}}-\theta^{k+1}_{\bar{k}_{n}}<\gamma$ , it is known that

(B.11)

\eta>\frac{1}{\sin\gamma}\quad\mbox{and}\quad\sin(\theta^{k+1}_{N_{k+1}}-\theta^{k+1}_{\bar{k}_{n}})>\sin\gamma,

which yields $\eta\sin(\theta^{k+1}_{\bar{k}_{n}}-\theta^{k+1}_{N_{k+1}})\leq-1$ . Thus we immediately derive that

		$\displaystyle\eta(N_{k+1}-n+1)\sum_{i=n}^{N_{k+1}}\left(\eta^{i-n}\underset{j\leq i}{\min_{j\in\mathcal{N}_{i}^{k+1}(k+1)}}\sin(\theta^{k+1}_{j}(t)-\theta^{k+1}_{i}(t))\right)+\mathcal{I}_{13}$
		$\displaystyle\leq\eta(N_{k+1}-n+1)\sin(\theta^{k+1}_{\bar{k}_{n}}-\theta^{k+1}_{N_{k+1}})+\underset{j>n-1}{\sum_{j\in\mathcal{N}_{n-1}^{k+1}(k+1)}}\sin(\theta^{k+1}_{j}-\theta^{k+1}_{n-1})$
		$\displaystyle\leq-(N_{k+1}-n+1)+(N_{k+1}-n+1)=0.$

Therefore, we combine the above arguments in (i) and (ii) to obtain

(B.12)

\eta(N_{k+1}-n+1)\sum_{i=n}^{N_{k+1}}\left(\eta^{i-n}\underset{j\leq i}{\min_{j\in\mathcal{N}_{i}^{k+1}(k+1)}}\sin(\theta^{k+1}_{j}-\theta^{k+1}_{i})\right)+\mathcal{I}_{13}\leq 0.

$\diamond$ Estimates on $\mathbf{\mathcal{I}_{14}}$ in (B.7). For the term $\mathcal{I}_{14}$ , there are three possible comparison between $\theta^{l}_{j}$ with $0\leq l\leq k$ and $\theta^{k+1}_{n-1}$ :

(i) If $\theta^{l}_{j}\leq\theta^{k+1}_{n-1}$ , we immediately have $\sin(\theta^{l}_{j}-\theta^{k+1}_{n-1})\leq 0$ .

(ii) If $\theta^{k+1}_{n-1}<\theta^{l}_{j}\leq\theta^{k+1}_{N_{k+1}}$ , we consider two cases separately:

(a) For the case that $0\leq\theta^{k+1}_{N_{k+1}}-\theta^{k+1}_{\bar{k}_{n}}\leq\frac{\pi}{2}$ , it is clear that

0\leq\theta^{l}_{j}-\theta^{k+1}_{n-1}\leq\theta^{k+1}_{N_{k+1}}-\theta^{k+1}_{n-1}\leq\theta^{k+1}_{N_{k+1}}-\theta^{k+1}_{\bar{k}_{n}}\leq\frac{\pi}{2}.

Thus from the above inequality and (B.8), we have

		$\displaystyle\eta\sum_{i=n}^{N_{k+1}}\left(\eta^{i-n}\underset{j\leq i}{\min_{j\in\mathcal{N}_{i}^{k+1}(k+1)}}\sin(\theta^{k+1}_{j}(t)-\theta^{k+1}_{i}(t))\right)+\sin(\theta^{l}_{j}-\theta^{k+1}_{n-1})$
		$\displaystyle\leq\eta\sin(\theta^{k+1}_{\bar{k}_{n}}-\theta^{k+1}_{N_{k+1}})+\sin(\theta^{l}_{j}-\theta^{k+1}_{n-1})$
		$\displaystyle\leq\sin(\theta^{k+1}_{\bar{k}_{n}}-\theta^{k+1}_{N_{k+1}})+\sin(\theta^{k+1}_{N_{k+1}}-\theta^{k+1}_{\bar{k}_{n}})=0.$

(b) For another case that $\frac{\pi}{2}<\theta^{k+1}_{N_{k+1}}-\theta^{k+1}_{\bar{k}_{n}}<\gamma$ , it is known from (B.11) that

		$\displaystyle\eta\sum_{i=n}^{N_{k+1}}\left(\eta^{i-n}\underset{j\leq i}{\min_{j\in\mathcal{N}_{i}^{k+1}(k+1)}}\sin(\theta^{k+1}_{j}(t)-\theta^{k+1}_{i}(t))\right)+\sin(\theta^{l}_{j}-\theta^{k+1}_{n-1})$
		$\displaystyle\leq\eta\sin(\theta^{k+1}_{\bar{k}_{n}}-\theta^{k+1}_{N_{k+1}})+\sin(\theta^{l}_{j}-\theta^{k+1}_{n-1})$
		$\displaystyle\leq-1+1=0$

Hence, combining the above arguments in (a) and (b), we obtain that

\eta\sum_{i=n}^{N_{k+1}}\left(\eta^{i-n}\underset{j\leq i}{\min_{j\in\mathcal{N}_{i}^{k+1}(k+1)}}\sin(\theta^{k+1}_{j}(t)-\theta^{k+1}_{i}(t))\right)+\sin(\theta^{l}_{j}-\theta^{k+1}_{n-1})\leq 0.

(iii) If $\theta^{l}_{j}>\theta^{k+1}_{N_{k+1}}$ , we exploit the concave property of sine function in $[0,\pi]$ to get

(B.13)

\sin(\theta^{l}_{j}-\theta^{k+1}_{n-1})\leq\sin(\theta^{l}_{j}-\theta^{k+1}_{N_{k+1}})+\sin(\theta^{k+1}_{N_{k+1}}-\theta^{k+1}_{n-1}).

For the second part on the right-hand side of above inequality (B.13), we apply the same analysis in (ii) to obtain

\eta\sum_{i=n}^{N_{k+1}}\left(\eta^{i-n}\underset{j\leq i}{\min_{j\in\mathcal{N}_{i}^{k+1}(k+1)}}\sin(\theta^{k+1}_{j}-\theta^{k+1}_{i})\right)+\sin(\theta^{k+1}_{N_{k+1}}-\theta^{k+1}_{n-1})\leq 0.

For the first part on the right-hand side of (B.13), the calculation is the same as the formula (B.6), thus we have

\sin(\theta^{l}_{j}-\theta^{k+1}_{N_{k+1}})\leq\theta^{l}_{j}-\theta^{k+1}_{N_{k+1}}\leq\theta^{l}_{j}-\min_{0\leq i\leq k}\min_{1\leq j\leq N_{i}}\{\theta^{i}_{j}\}\leq D_{k}(\theta(t)).

Therefore, we combine the above estimates to obtain

(B.14)			$\displaystyle\eta S_{k}\sum_{i=n}^{N_{k+1}}\left(\eta^{i-n}\underset{j\leq i}{\min_{j\in\mathcal{N}_{i}^{k+1}(k+1)}}\sin(\theta^{k+1}_{j}(t)-\theta^{k+1}_{i}(t))\right)+\mathcal{I}_{14}$
			$\displaystyle\leq\eta S_{k}\sin(\theta^{k+1}_{\bar{k}_{n}}-\theta^{k+1}_{N_{k+1}})+\sum_{l=0}^{k}\sum_{j\in\mathcal{N}_{n-1}^{k+1}(l)}\sin(\theta^{l}_{j}-\theta^{k+1}_{n-1})$
			$\displaystyle\leq S_{k}D_{k}(\theta(t)).$

Then combining (B.9), (B.12), (B.14) and coming back to (B.7), we obtain that

	$\displaystyle\frac{d}{dt}\bar{\theta}^{k+1}_{n-1}$	$\displaystyle\leq\Omega_{M}+\kappa\frac{\eta}{\bar{a}^{k+1}_{n-1}+1}\sum_{i=n}^{N_{k+1}}\left(\eta^{i-n}\underset{j\leq i}{\min_{j\in\mathcal{N}_{i}^{k+1}(k+1)}}\sin(\theta^{k+1}_{j}-\theta^{k+1}_{i})\right)$
		$\displaystyle+\kappa\frac{1}{\bar{a}^{k+1}_{n-1}+1}\underset{j\leq n-1}{\min_{j\in\mathcal{N}_{n-1}^{k+1}(k+1)}}\sin(\theta^{k+1}_{j}-\theta^{k+1}_{n-1})$
		$\displaystyle+\frac{\bar{a}^{k+1}_{n-1}}{\bar{a}^{k+1}_{n-1}+1}\kappa S_{k}D_{k}(\theta(t))+\frac{1}{\bar{a}^{k+1}_{n-1}+1}\kappa S_{k}D_{k}(\theta(t))$
		$\displaystyle=\Omega_{M}+\kappa\frac{1}{\bar{a}^{k+1}_{n-1}+1}\sum_{i=n-1}^{N_{k+1}}\left(\eta^{i-(n-1)}\underset{j\leq i}{\min_{j\in\mathcal{N}_{i}^{k+1}(k+1)}}\sin(\theta^{k+1}_{j}-\theta^{k+1}_{i})\right)+\kappa S_{k}D_{k}(\theta(t)).$

This means that the claim (B.1) does hold for $n-1$ . Therefore, we apply the inductive criteria to complete the proof of the claim (B.1).

$\bigstar$ Step 2. Now we are ready to prove (4.18) on $J_{l}$ for Case 2. In fact, we apply Lemma 3.1 and the strong connectivity of $\mathcal{G}_{k+1}$ to have

\sum_{i=1}^{N_{k+1}}\left(\eta^{i-1}\underset{j\leq i}{\min_{j\in\mathcal{N}_{i}^{k+1}(k+1)}}\sin(\theta^{k+1}_{j}-\theta^{k+1}_{i})\right)\leq\sin(\theta^{k+1}_{1}-\theta^{k+1}_{N_{k+1}})

From the notations in (4.5) and (4.6), it is known that

\bar{\theta}_{1}^{k+1}=\bar{\theta}_{k+1},\quad\underline{\theta}_{N_{k+1}}^{k+1}=\underline{\theta}_{k+1}.

Thus, we exploit the above inequality and set $n=1$ in (B.1) to obtain

(B.15)	$\displaystyle\frac{d}{dt}\bar{\theta}_{k+1}$	$\displaystyle=\frac{d}{dt}\bar{\theta}^{k+1}_{1}$
		$\displaystyle\leq\Omega_{M}+\kappa\frac{1}{\bar{a}^{k+1}_{1}+1}\sum_{i=1}^{N_{k+1}}\left(\eta^{i-1}\underset{j\leq i}{\min_{j\in\mathcal{N}_{i}^{k+1}(k+1)}}\sin(\theta^{k+1}_{j}-\theta^{k+1}_{i})\right)+\kappa S_{k}D_{k}(\theta(t))$
		$\displaystyle\leq\Omega_{M}+\kappa S_{k}D_{k}(\theta(t))+\kappa\frac{1}{\bar{a}^{k+1}_{1}+1}\sin(\theta^{k+1}_{1}-\theta^{k+1}_{N_{k+1}})$

We further apply the similar arguments in obtaining the dynamics of $\bar{\theta}_{k+1}$ in (B.15) to derive the differential inequality of $\underline{\theta}_{k+1}$ as below

(B.16)

\frac{d}{dt}\underline{\theta}_{k+1}\geq\Omega_{m}+\kappa\frac{1}{\bar{a}^{k+1}_{1}+1}\sin(\theta^{k+1}_{N_{k+1}}-\theta^{k+1}_{1})-\kappa S_{k}D_{k}(\theta(t)).

Due to the monotone decreasing property of $\frac{\sin x}{x}$ in $(0,\pi]$ and from (4.21), it is obvious that

\sin(\theta^{k+1}_{N_{k+1}}-\theta^{k+1}_{1})\geq\frac{\sin\gamma}{\gamma}(\theta^{k+1}_{N_{k+1}}-\theta^{k+1}_{1}).

Then we combine the above inequality, (B.15), (B.16) and (4.4) to get

	$\displaystyle\dot{Q}^{k+1}(t)$	$\displaystyle=\frac{d}{dt}(\bar{\theta}_{k+1}-\underline{\theta}_{k+1})\leq D(\Omega)-\kappa\frac{2}{\bar{a}^{k+1}_{1}+1}\sin(\theta^{k+1}_{N_{k+1}}-\theta^{k+1}_{1})+2\kappa S_{k}D_{k}(\theta(t))$
		$\displaystyle\leq D(\Omega)-\kappa\frac{1}{\bar{a}^{k+1}_{1}+1}\frac{\sin\gamma}{\gamma}(\theta^{k+1}_{N_{k+1}}-\theta^{k+1}_{1})+2\kappa S_{k}D_{k}(\theta(t))$
		$\displaystyle\leq D(\Omega)-\kappa\frac{1}{\bar{a}^{k+1}_{1}+1}\frac{\sin\gamma}{\gamma}Q^{k+1}(t)+2\kappa S_{k}D_{k}(\theta(t))$
		$\displaystyle\leq D(\Omega)-\kappa\frac{1}{\sum_{j=1}^{N-1}(\eta^{j}A(2N,j))+1}\frac{\sin\gamma}{\gamma}Q^{k+1}(t)+\kappa(2N+1)D_{k}(\theta(t)),\quad t\in J_{l},$

where we use the fact that $Q^{k+1}(t)\leq\theta^{k+1}_{N_{k+1}}(t)-\theta^{k+1}_{1}(t)$ . Thus we obtain the dynamics for $Q^{k+1}(t)$ in (4.18) on $J_{l}$ .

B.3. Case 3

Consider the case that

\max_{0\leq i\leq k+1}\{\bar{\theta}_{i}\}=\bar{\theta}_{k+1},\quad\min_{0\leq i\leq k+1}\{\underline{\theta}_{i}\}=\min_{0\leq i\leq k}\{\underline{\theta}_{i}\}\quad\mbox{on}\ J_{l}.

The comparison relation in this case is presented in Figure 3. For this case, without loss of generality, we set

\underline{\theta}_{q}=\min_{0\leq i\leq k}\{\underline{\theta}_{i}\}\quad\mbox{where}\ 0\leq q\leq k.

We further assume

\theta^{k+1}_{1}\leq\theta^{k+1}_{2}\leq\ldots\leq\theta^{k+1}_{N_{k+1}},\quad\theta^{q}_{1}\leq\theta^{q}_{2}\leq\ldots\leq\theta^{q}_{N_{q}}\quad\mbox{in}\ J_{l}.

It is obvious that $\underline{\theta}_{q}=\min_{0\leq i\leq q}\{\underline{\theta}_{i}\}$ . Thus we apply the same arguments in Case 2 to obtain

(B.17)

\frac{d}{dt}\underline{\theta}_{q}\geq\Omega_{m}+\kappa\frac{1}{\bar{a}^{q}_{1}+1}\sin(\theta^{q}_{N_{q}}-\theta^{q}_{1})-\kappa S_{q-1}D_{q-1}(\theta(t)).

In the subsequence, we prove (4.18) on $J_{l}$ in two sub-cases depending on the comparison between $\theta^{k+1}_{1}$ and $\max\limits_{0\leq i\leq k}\max\limits_{1\leq j\leq N_{i}}\{\theta^{i}_{j}\}$ .

$\bullet$ Case 3.1. If $\theta^{k+1}_{1}\leq\max\limits_{0\leq i\leq k}\max\limits_{1\leq j\leq N_{i}}\{\theta^{i}_{j}\}$ , then we combine (4.21), (B.15) and (B.17) to get

	$\displaystyle\dot{Q}^{k+1}(t)$	$\displaystyle=\frac{d}{dt}(\bar{\theta}_{k+1}-\underline{\theta}_{q})$
		$\displaystyle\leq D(\Omega)+\kappa S_{k}D_{k}(\theta(t))-\kappa\frac{1}{\bar{a}^{k+1}_{1}+1}\sin(\theta^{k+1}_{N_{k+1}}-\theta^{k+1}_{1})$
		$\displaystyle-\kappa\frac{1}{\bar{a}^{q}_{1}+1}\sin(\theta^{q}_{N_{q}}-\theta^{q}_{1})+\kappa S_{q-1}D_{q-1}(\theta(t))$
		$\displaystyle\leq D(\Omega)-\kappa\min\left\{\frac{1}{\bar{a}^{k+1}_{1}+1},\frac{1}{\bar{a}^{q}_{1}+1}\right\}\left(\sin(\theta^{k+1}_{N_{k+1}}-\theta^{k+1}_{1})+\sin(\theta^{q}_{N_{q}}-\theta^{q}_{1})\right)$
		$\displaystyle+\kappa(S_{k}+S_{q-1})D_{k}(\theta(t))$
		$\displaystyle\leq D(\Omega)-\kappa\min\left\{\frac{1}{\bar{a}^{k+1}_{1}+1},\frac{1}{\bar{a}^{q}_{1}+1}\right\}\frac{\sin\gamma}{\gamma}\left(\theta^{k+1}_{N_{k+1}}-\theta^{k+1}_{1}+\theta^{q}_{N_{q}}-\theta^{q}_{1}\right)$
		$\displaystyle+\kappa(S_{k}+S_{q-1})D_{k}(\theta(t))-\kappa\min\left\{\frac{1}{\bar{a}^{k+1}_{1}+1},\frac{1}{\bar{a}^{q}_{1}+1}\right\}\frac{\sin\gamma}{\gamma}\left(\max\limits_{0\leq i\leq k}\max\limits_{1\leq j\leq N_{i}}\{\theta^{i}_{j}\}-\theta^{q}_{N_{q}}\right)$
		$\displaystyle+\kappa\min\left\{\frac{1}{\bar{a}^{k+1}_{1}+1},\frac{1}{\bar{a}^{q}_{1}+1}\right\}\frac{\sin\gamma}{\gamma}\left(\max\limits_{0\leq i\leq k}\max\limits_{1\leq j\leq N_{i}}\{\theta^{i}_{j}\}-\theta^{q}_{N_{q}}\right)$
		$\displaystyle\leq D(\Omega)-\kappa\min\left\{\frac{1}{\bar{a}^{k+1}_{1}+1},\frac{1}{\bar{a}^{q}_{1}+1}\right\}\frac{\sin\gamma}{\gamma}\left(\theta^{k+1}_{N_{k+1}}-\theta^{q}_{1}\right)+\kappa(S_{k}+S_{q-1})D_{k}(\theta(t))$
		$\displaystyle+\kappa\min\left\{\frac{1}{\bar{a}^{k+1}_{1}+1},\frac{1}{\bar{a}^{q}_{1}+1}\right\}\frac{\sin\gamma}{\gamma}D_{k}(\theta(t))$
		$\displaystyle\leq D(\Omega)-\kappa\frac{1}{\sum_{j=1}^{N-1}(\eta^{j}A(2N,j))+1}\frac{\sin\gamma}{\gamma}Q^{k+1}(t)+\kappa(2N+1)D_{k}(\theta(t)),\qquad\mbox{in}\ J_{l}.$

In above estimates, we apply (4.4), (B.4) and the fact that

Q^{k+1}(t)=\bar{\theta}_{k+1}-\underline{\theta}_{q}\leq\theta^{k+1}_{N_{k+1}}-\theta^{q}_{1}\quad\mbox{and}\quad\min\left\{\frac{1}{\bar{a}^{k+1}_{1}+1},\frac{1}{\bar{a}^{q}_{1}+1}\right\}\frac{\sin\gamma}{\gamma}\leq 1.

$\bullet$ Case 3.2. If $\theta^{k+1}_{1}>\max\limits_{0\leq i\leq k}\max\limits_{1\leq j\leq N_{i}}\{\theta^{i}_{j}\}$ , similar to Case 2, we can apply the induction principle to prove that for $1\leq n\leq N_{k+1}$ ,

(B.18)	$\displaystyle\frac{d}{dt}\bar{\theta}^{k+1}_{n}$	$\displaystyle\leq\Omega_{M}+\kappa\frac{1}{\bar{a}^{k+1}_{n}+1}\sum_{i=n}^{N_{k+1}}\left(\eta^{i-n}\underset{j\leq i}{\min_{j\in\mathcal{N}_{i}^{k+1}(k+1)}}\sin(\theta^{k+1}_{j}-\theta^{k+1}_{i})\right)$
		$\displaystyle+\kappa\frac{1}{\bar{a}^{k+1}_{n}+1}\sum_{l=0}^{k}\sum_{j\in\mathcal{N}_{n}^{k+1}(l)}\sin(\theta^{l}_{j}-\theta^{k+1}_{n})$
		$\displaystyle+\kappa\sum_{i=n+1}^{N_{k+1}}\left(\frac{\prod_{r=n}^{i-1}\bar{a}^{k+1}_{r}}{\prod_{r=n}^{i}(\bar{a}^{k+1}_{r}+1)}\sum_{l=0}^{k}\sum_{j\in\mathcal{N}_{i}^{k+1}(l)}\sin(\theta^{l}_{j}-\theta^{k+1}_{i})\right).$

Since the proof of (B.18) is similar to that of (B.1), we omit its details. In particular, we set $n=1$ in the above inequality (B.18) and apply Lemma 3.1 to get

(B.19)		$\displaystyle\frac{d}{dt}\bar{\theta}_{k+1}=\frac{d}{dt}\bar{\theta}^{k+1}_{1}$	$\displaystyle\leq\Omega_{M}+\kappa\frac{1}{\bar{a}^{k+1}_{1}+1}\sin(\theta^{k+1}_{1}-\theta^{k+1}_{N_{k+1}})+\kappa\frac{1}{\bar{a}^{k+1}_{1}+1}\sum_{l=0}^{k}\sum_{j\in\mathcal{N}_{1}^{k+1}(l)}\sin(\theta^{l}_{j}-\theta^{k+1}_{1})$
(B.19)			$\displaystyle+\kappa\sum_{i=2}^{N_{k+1}}\left(\frac{\prod_{r=1}^{i-1}\bar{a}^{k+1}_{r}}{\prod_{r=1}^{i}(\bar{a}^{k+1}_{r}+1)}\sum_{l=0}^{k}\sum_{j\in\mathcal{N}_{i}^{k+1}(l)}\sin(\theta^{l}_{j}-\theta^{k+1}_{i})\right)$

Due to the situation that $\theta^{k+1}_{1}>\max\limits_{0\leq i\leq k}\max\limits_{1\leq j\leq N_{i}}\{\theta^{i}_{j}\}$ , it is known that for $0\leq l\leq k$ , the term $\sin(\theta^{l}_{j}-\theta^{k+1}_{i})$ in (B.19) is non-positive. And according to the spanning tree structure, the neighbors set of $\mathcal{G}_{k+1}$ in $\bigcup_{l=0}^{k}\mathcal{G}_{l}$ is non-empty,

\bigcup_{i=1}^{N_{k+1}}\bigcup_{l=0}^{k}\mathcal{N}_{i}^{k+1}(l)\neq\emptyset,

this means that there must exist some $\theta^{l}_{n}$ belonging to $\bigcup_{l=0}^{k}\mathcal{G}_{l}$ and $\theta^{k+1}_{m}$ such that $\theta^{l}_{n}\in\mathcal{N}^{k+1}_{m}(l)$ . Moreover, from (4.2), it is clear that for the coefficients in the last term in (B.19) satisfy

\frac{\prod_{r=1}^{i-1}\bar{a}^{k+1}_{r}}{\prod_{r=2}^{i}(\bar{a}^{k+1}_{r}+1)}=\frac{\prod_{r=1}^{i-1}\bar{a}^{k+1}_{r}}{\prod_{r=1}^{i-1}(\bar{a}^{k+1}_{r+1}+1)}=\prod_{r=1}^{i-1}\eta(2N-r+1)>1\quad\mbox{with}\ 2\leq i\leq N_{k+1}.

Then we combine the above estimates to have

(B.20)	$\displaystyle\frac{d}{dt}\bar{\theta}_{k+1}$	$\displaystyle\leq\Omega_{M}+\kappa\frac{1}{\bar{a}^{k+1}_{1}+1}\sin(\theta^{k+1}_{1}-\theta^{k+1}_{N_{k+1}})+\kappa\frac{1}{\bar{a}^{k+1}_{1}+1}\sum_{l=0}^{k}\sum_{j\in\mathcal{N}_{1}^{k+1}(l)}\sin(\theta^{l}_{j}-\theta^{k+1}_{1})$
		$\displaystyle+\kappa\frac{1}{\bar{a}^{k+1}_{1}+1}\sum_{i=2}^{N_{k+1}}\left(\frac{\prod_{l=1}^{i-1}\bar{a}^{k+1}_{l}}{\prod_{l=2}^{i}(\bar{a}^{k+1}_{l}+1)}\sum_{l=0}^{k}\sum_{j\in\mathcal{N}_{i}^{k+1}(l)}\sin(\theta^{l}_{j}-\theta^{k+1}_{i})\right)$
		$\displaystyle\leq\Omega_{M}+\kappa\frac{1}{\bar{a}^{k+1}_{1}+1}\sin(\theta^{k+1}_{1}-\theta^{k+1}_{N_{k+1}})+\kappa\frac{1}{\bar{a}^{k+1}_{1}+1}\sin(\theta^{l}_{n}-\theta^{k+1}_{m})$
		$\displaystyle\leq\Omega_{M}-\kappa\frac{1}{\bar{a}^{k+1}_{1}+1}\frac{\sin\gamma}{\gamma}\left(\theta^{k+1}_{N_{k+1}}-\theta^{k+1}_{1}\right)-\kappa\frac{1}{\bar{a}^{k+1}_{1}+1}\frac{\sin\gamma}{\gamma}\left(\theta^{k+1}_{m}-\theta^{l}_{n}\right)$
		$\displaystyle\leq\Omega_{M}-\kappa\frac{1}{\bar{a}^{k+1}_{1}+1}\frac{\sin\gamma}{\gamma}\left(\theta^{k+1}_{N_{k+1}}-\theta^{k+1}_{1}+\theta^{k+1}_{1}-\max\limits_{0\leq i\leq k}\max\limits_{1\leq j\leq N_{i}}\{\theta^{i}_{j}\}\right)$
		$\displaystyle=\Omega_{M}-\kappa\frac{1}{\bar{a}^{k+1}_{1}+1}\frac{\sin\gamma}{\gamma}\left(\theta^{k+1}_{N_{k+1}}-\max\limits_{0\leq i\leq k}\max\limits_{1\leq j\leq N_{i}}\{\theta^{i}_{j}\}\right),$

where we exploit the property

\theta^{k+1}_{m}-\theta^{l}_{n}\geq\theta^{k+1}_{1}-\max\limits_{0\leq i\leq k}\max\limits_{1\leq j\leq N_{i}}\{\theta^{i}_{j}\}.

Then we combine (B.17) and (B.20) to obtain that

	$\displaystyle\dot{Q}^{k+1}(t)$	$\displaystyle\leq D(\Omega)-\kappa\frac{1}{\bar{a}^{k+1}_{1}+1}\frac{\sin\gamma}{\gamma}\left(\theta^{k+1}_{N_{k+1}}-\max\limits_{0\leq i\leq k}\max\limits_{1\leq j\leq N_{i}}\{\theta^{i}_{j}\}\right)$
		$\displaystyle-\kappa\frac{1}{\bar{a}^{q}_{1}+1}\sin(\theta^{q}_{N_{q}}-\theta^{q}_{1})+\kappa S_{q-1}D_{q-1}(\theta(t))$
		$\displaystyle\leq D(\Omega)-\kappa\min\left\{\frac{1}{\bar{a}^{k+1}_{1}+1},\frac{1}{\bar{a}^{q}_{1}+1}\right\}\frac{\sin\gamma}{\gamma}\left(\theta^{k+1}_{N_{k+1}}-\max\limits_{0\leq i\leq k}\max\limits_{1\leq j\leq N_{i}}\{\theta^{i}_{j}\}+\theta^{q}_{N_{q}}-\theta^{q}_{1}\right)$
		$\displaystyle-\kappa\min\left\{\frac{1}{\bar{a}^{k+1}_{1}+1},\frac{1}{\bar{a}^{q}_{1}+1}\right\}\frac{\sin\gamma}{\gamma}\left(\max\limits_{0\leq i\leq k}\max\limits_{1\leq j\leq N_{i}}\{\theta^{i}_{j}\}-\theta^{q}_{N_{q}}\right)$
		$\displaystyle+\kappa\min\left\{\frac{1}{\bar{a}^{k+1}_{1}+1},\frac{1}{\bar{a}^{q}_{1}+1}\right\}\frac{\sin\gamma}{\gamma}\left(\max\limits_{0\leq i\leq k}\max\limits_{1\leq j\leq N_{i}}\{\theta^{i}_{j}\}-\theta^{q}_{N_{q}}\right)+\kappa S_{q-1}D_{q-1}(\theta(t))$
		$\displaystyle\leq D(\Omega)-\kappa\min\left\{\frac{1}{\bar{a}^{k+1}_{1}+1},\frac{1}{\bar{a}^{q}_{1}+1}\right\}\frac{\sin\gamma}{\gamma}\left(\theta^{k+1}_{N_{k+1}}-\theta^{q}_{1}\right)+\kappa(2N+1)D_{k}(\theta(t))$
		$\displaystyle\leq D(\Omega)-\kappa\frac{1}{\sum_{j=1}^{N-1}(\eta^{j}A(2N,j))+1}\frac{\sin\gamma}{\gamma}Q^{k+1}(t)+\kappa(2N+1)D_{k}(\theta(t)),\qquad\mbox{in}\ J_{l}.$

B.4. Case 4

Consider the case that

\max_{0\leq i\leq k+1}\{\bar{\theta}_{i}\}=\max_{0\leq i\leq k}\{\bar{\theta}_{i}\},\quad\min_{0\leq i\leq k+1}\{\underline{\theta}_{i}\}=\underline{\theta}_{k+1}\quad\mbox{in}\ J_{l}.

The comparison relation in this case is showed in Figure 4. For this case, the analysis is similar to that in Case 3. Therefore, we omit the details of discussion.

B.5. Conclusion

Since all analysis above do not depend on interval $J_{l}$ with $1\leq l\leq r$ , thus we combine all analysis in Case 1, Case 2, Case 3, and Case 4 to derive that

\dot{Q}^{k+1}(t)\leq D(\Omega)-\kappa\frac{1}{\sum_{j=1}^{N-1}(\eta^{j}A(2N,j))+1}\frac{\sin\gamma}{\gamma}Q^{k+1}(t)+\kappa(2N+1)D_{k}(\theta(t)),\qquad\mbox{in}\ [0,T^{*}).

∎

References

[1] Acebron, J. A., Bonilla, L. L., Vicente, C. J. P., Ritort, F. and Spigler, R.: The Kuramoto model: A simple paradigm for synchronization phenomena. Rev. Mod. Phys. 77, 137–185 (2005).
[2] Balmforth, N. J. and Sassi, R.: A shocking display of synchrony. Phys. D 143, 21–55 (2000).
[3] Choi, Y. P., Ha, S. Y., Jung, S. and Kim, Y.: Asymptotic formation and orbital stability of phase-locked states for the Kuramoto model. Phys. D 241, 735–754 (2012).
[4] Choi, Y.-P. and Li, Z.: Synchronization of nonuniform Kuramoto oscillators for power grids with general connectivity and dampings. Nonlinearity 32, 559–583 (2019).
[5] Chopra, N. and Spong, M. W.: On exponential synchronization of Kuramoto oscillators. IEEE Trans. Automat. Control 54, 353–357 (2009).
[6] Cucker, F. and Smale, S.: Emergent behavior in flocks. IEEE Trans. Automat. Control 52, 852–862 (2007).
[7] Degond, P. and Motsch, S..: Macroscopic limit of self-driven particles with orientation interaction. C. R. Math. 345, 555–560 (2007).
[8] Degond, P. and Motsch, S.: Large-scale dynamics of the persistent turning walker model of fish behavior. J. Stat. Phys., 131, 989–1022 (2008).
[9] Degond, P. and Motsch, S.: Continuum limit of self-driven particles with orientation interaction. Math. Models Methods Appl. Sci. 18, 1193–1215 (2008).
[10] Dong, J.-G., Ha, S.-Y. and Kim, D.: Interplay of time-delay and velocity alignment in the Cucker-Smale model on a general digraph. Discrete Contin. Dyn. Syst.-Ser. B 24, 5569–5596 (2019).
[11] Dong, J.-G., Ha, S.-Y. and Kim, D.:Emergent Behavior of the Kuramoto model with a time-delay on a general digraph. SIAM J. Appl. Dyn. Syst. 19, 304–328 (2020).
[12] Dong, J.-G. and Xue, X.: Synchronization analysis of Kuramoto oscillators, Commun. Math. Sci. 11, 465–480 (2013).
[13] Dörfler, F. and Bullo, F.: On the critical coupling for Kuramoto oscillators. SIAM J. Appl. Dyn. Syst. 10, 1070–1099 (2011).
[14] Ha, S. -Y., Ha, T. and Kim, J. -H.: On the complete synchronization of the Kuramoto phase model. Phys. D 239, 1692–1700 (2010).
[15] Ha, S.-Y. and Kim, D.: Robustness and asymptotic stability for the Winfree model on a general network under the effect of time-delay. J. Math. Phys. 59, 112702 (2018).
[16] Ha, S.-Y., Kim, D., Kim, J. and Zhang, X.:Asymptotic behavior of discrete Kuramoto model and uniform-in-time transition from discrete to continuous dynamics. J. Math. Phys. 60, no. 5, 051508 (2019).
[17] Ha, S.-Y., Kim, D., Lee, J. and Noh, S.E.: Synchronization conditions of a mixed Kuramoto ensemble in attractive and repulsive couplings. J. Nonlinear Sci. 31, 39 (2021).
[18] Ha, S.-Y., Kim, H. K. and Park, J.: Remarks on the complete synchronization of Kuramoto oscillators. Nonlinearity 28, 1441–1462 (2015).
[19] Ha, S.-Y., Kim, H. K. and Ryoo, S. W.: Emergence of phase-locked states for the Kuramoto model in a large coupling regime. Commun. Math. Sci. 14, 1073–1091 (2016).
[20] Ha, S.-Y., Ko, D., Park, J. and Ryoo, S. W.:Emergent dynamics of Winfree oscillators on locally coupled networks. J. Differ. Equ. 260, 4203–4236 (2016).
[21] Ha, S.-Y., Li, Z. and Xue, X.: Formation of phase-locked states in a population of locally interacting Kuramoto oscillators. J. Differential Equations 255, 3053–3070 (2013).
[22] Ha, S.-Y., Li, Z. and Zhang, X.: On the critical exponent of the one-dimensional Cucker Smale model on a general graph. Mathematical Models and Methods in Applied Sciences 1 30, 1653–1703 (2020).
[23] Ha, S.-Y. and Ryoo, S. W.: Asymptotic phase-Locking dynamics and critical coupling strength for the Kuramoto model. Commun. Math. Phys. 377, 811–857 (2002).
[24] Kuramoto, Y.: Self-entrainment of a population of coupled non-linear oscillators. International Symposium on Mathematical Problems in Theoretical Physics, 420–422 (1975).
[25] Leonard, N. E., Paley, D. A., Lekien, F., Sepulchre, R., Fratantoni D. M. and Davis, R. E.: Collective motion, sensor networks, and ocean sampling. Proc. IEEE 95, 48–74 (2007).
[26] Mirollo, R. E. and Strogatz, S. H.: The spectrum of the partially locked state for the Kuramoto model of coupled oscillator. J. Non- linear Sci. 17 309–347 (2007).
[27] Paley, D. A., Leonard, N. E., Sepulchre, R. and Grunbaum, D.: Oscillator models and collective motion: spatial patterns in the dynamics of engineered and biological networks. IEEE Control Sys. 27, 89–105 (2007).
[28] Perea, L., Gómez, G. and Elosegui, P.: Extension of the Cucker-Smale control law to space flight formations. J. Guid. Control Dynam. 32, 527–537 (2009).
[29] Pikovsky, A., Rosenblum, M. and Kurths, J.: Synchronization: A Universal Concept in Nonlinear Sciences. Cambridge University Press, 2001.
[30] Strogatz, S. H.: From Kuramoto to Crawford: exploring the onset of synchronization in populations of coupled oscillators. Phys. D 143, 1–20 (2000).
[31] Toner, J. and Tu, Y.: Flocks, herds, and schools: A quantitative theory of flocking. Phys. Rev. E 58, 4828–4858 (1998) .
[32] Topaz, C. M. and Bertozzi, A. L.: Swarming patterns in a two-dimensional kinematic model for biological groups. SIAM J. Appl. Math. 65, 152–174 (2004).
[33] Vicsek, T., Czirók, A., Ben-Jacob, E., Cohen, I. and Schochet, O.: Novel type of phase transition in a system of self-driven particles. Phys. Rev. Lett. 75, 1226–1229 (1995).
[34] Winfree, A. T.: Biological rhythms and behavior of populations of coupled oscillators. J. Theor. Biol. 16, 15–42 (1967).