RemarkRemark: AI-adaptedProof: AI-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Connectivity is necessary but not sufficient for synchrony

PDF p. 4: Section 1, random graph discussion; PDF p. 8: Remark 1.8, cycle example; PDF p. 9: Section 1.5; PDF p. 31: Section 6, paragraph after the connectivity threshold

Statement

Assume countable choice. A finite undirected graph with nonempty vertex set, allowing self-loops, can be globally synchronizing only if it is connected. Connectivity is not sufficient: an unweighted cycle of length greater than five is connected but is not globally synchronizing.

Here connected means that every two vertices are joined by a path. Globally synchronizing means that, outside a set of normalized phase volume zero, the homogeneous Kuramoto trajectory in the frame rotating at its common intrinsic frequency converges to a state whose phases are all equal modulo $2 π$ . For the independent-edge graph $G (n, p_{n})$ with $p_{n} = (\log n + c_{n}) / n \in [0, 1]$ eventually and $c_{n} \to - \infty$ , the probability of global synchrony tends to zero. The article describes its result above $\log n / n$ as asymptotically optimal in relation to this connectivity threshold.

Facts & Assumptions

Given: Countable choice and a finite undirected graph $G = (V, E)$ with nonempty $V$ , symmetric adjacency matrix $A$ , and the homogeneous Kuramoto dynamics.

Goal: Prove the connectivity necessity, give a connected counterexample to sufficiency, and establish the stated lower-threshold consequence.

[F1]

Connected components partition $V$ into nonempty sets, with no edges between distinct components; a graph is connected exactly when it has one component (Connected graphs and connected components defined by the existence of vertex paths, Adjacency, degrees, graph Laplacian, and spectral notation).

[F2]

In the rotating frame the equations are ${\dot{ϕ}}_{x} = - \sum_{y \in V} A_{x y} \sin (ϕ_{x} - ϕ_{y})$ , and the trajectories are defined for all time. The adjacency matrix is symmetric and loop terms vanish (Graph Kuramoto differential equations, Adjacency, degrees, graph Laplacian, and spectral notation).

[F3]

Normalized phase volume is the completed normalized Lebesgue measure on the representative box $(- π, π]^{V}$ . Under countable choice every affine hyperplane with nonzero normal in $R^{V}$ , and every subset of it, is Lebesgue null (Normalized phase volume and almost-everywhere assertions, Every affine hyperplane of ℝⁿ, and hence every proper linear subspace, is Lebesgue null, The Axiom of Countable Choice (AC_ω)).

[F4]

An unweighted cycle of length greater than five is not globally synchronizing (Trees synchronize whereas cycles longer than five do not).

[F5]

For the stated independent-edge graph law, if $c_{n} \to - \infty$ , the probability of connectedness tends to zero (Classical Erdős–Rényi connectivity threshold).

[F6]

Finite sums of differentiable functions of a real variable may be differentiated termwise. For real $u$ , the phasor $z (u) = \cos u + i \sin u$ satisfies $z (- u) = \overline{z (u)}$ (Phasors, trigonometric identities and periodic derivatives).

Proof

technique · direct

1.1F1F2F6

Suppose $G$ is disconnected and choose distinct components $C, D$ , of sizes $a, b > 0$ . For a rotating-frame trajectory, the circle-valued component sums $S_{C} = \sum_{x \in C} ϕ_{x}$ and $S_{D} = \sum_{x \in D} ϕ_{x}$ are constant modulo $2 π$ . Indeed, [F6] permits termwise differentiation in local lifts, and taking imaginary parts of $z (- u) = \overline{z (u)}$ gives $\sin (- u) = - \sin u$ . Thus the derivative of either sum is zero: terms for distinct vertices in the same component cancel in pairs by symmetry and oddness of sine, loop terms vanish, and there are no edges leaving the component. Hence $b S_{C} - a S_{D}$ is constant modulo $2 π$ .

1.2F4

A cycle of length greater than five is connected: successive edges along the cycle join any pair of its vertices. By [F4] it is nevertheless not globally synchronizing. This proves that connectivity is not sufficient.

2.1F1F3step 1.1

If the trajectory converges to a fully synchronized state with common phase $s$ , continuity of addition on the phase circle gives $S_{C} \to a s$ and $S_{D} \to b s$ . Thus the constant $b S_{C} - a S_{D}$ must be zero modulo $2 π$ . For initial representatives $u \in (- π, π]^{V}$ , this necessary condition is $b \sum_{x \in C} u_{x} - a \sum_{x \in D} u_{x} = 2 π k$ for some $k \in Z$ . Each equation defines an affine hyperplane with nonzero normal. Their countable union is Lebesgue null, so by [F3] the set of initial phases satisfying the condition is phase-null. Consequently almost no initial state can converge to a fully synchronized state, and the disconnected graph is not globally synchronizing.

3.1F5step 2.1∎

For each $n$ , step 2.1 makes the event that $G (n, p_{n})$ is globally synchronizing a subset of the event that it is connected. There are finitely many graphs on the labeled vertex set, so these events are measurable. Their probabilities therefore satisfy $0 \leq P (G (n, p_{n}) globally synchronizing) \leq P (G (n, p_{n}) connected)$ . The right side tends to zero by [F5], proving the lower-threshold assertion.

Source notes

The necessity, failure of sufficiency, and threshold comparison are attributed to Expander graphs are globally synchronizing, PDF page 8, Remark 1.8 (the cycle example), pages 4 and 31 (the connectivity threshold comparison), and page 9, Section 1.5 (related discussion). The article states its upper result for fixed positive distance above the leading threshold; the lower-threshold deduction above does not establish a matching result throughout the critical window. The article is cited for attribution, not as proof of the deductions.

Depends on

Dependency tree · 2 levels

Each result is drawn at its shortest distance from this item. Arrows run from prerequisites to the items that use them; this item has a heavier outline. External source nodes link directly to the cited text. The view shows up to two dependency steps; open a prerequisite to continue.

Sources

Expander graphs are globally synchronizing · PDF p. 4, random graph discussion; p. 8, Remark 1.8; p. 9, Section 1.5; p. 31, paragraph following the connectivity threshold