ExampleConstruction: AI-adaptedVerification: 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.

Trees synchronize whereas cycles longer than five do not

PDF p. 8: Remark 1.8; Section 1.5; PDF p. 9: Remark 1.8; Section 1.5

Statement

Assume countable choice. Every finite nonempty tree is globally synchronizing, while an unweighted cycle of length greater than five is not globally synchronizing. Consequently, adding an edge to a globally synchronizing graph need not preserve global synchrony.

A tree is a connected finite simple graph without cycles. A cycle of length $n \geq 3$ has vertices $0, \dots, n - 1$ and edges ${j, j + 1}$ with indices modulo $n$ . Global synchrony means that, for normalized uniform phase volume, almost every rotating-frame trajectory converges to an individual state in which all phases agree modulo $2 π$ (Globally synchronizing graph — Definition 1.1, Trees, forests, leaves and isolated vertices).

Facts & Assumptions

[F1]

Countable choice is assumed. The phase space is the finite flat torus $T_{V} = R^{V} / (2 π Z)^{V}$ ; the homogeneous system has a complete flow and its rotating-frame trajectories are downward gradient trajectories of $E_{G} = \sum_{{x, y} \in E} (1 - \cos (θ_{x} - θ_{y}))$ for a simple graph (The Axiom of Countable Choice (AC_ω), Finite phase tori, local lifts and the flat metric, Graph Kuramoto differential equations, Homogeneous Kuramoto energy, Rotating-frame gradient formulation).

[F2]

The graph energy is real analytic on the phase torus. Every downward gradient trajectory of a real analytic potential on this torus converges to one critical point. For a $C^{2}$ potential with complete downward gradient flow, initial states converging to any critical point whose Hessian has a negative eigenvalue form a phase-volume null set (Analytic potentials on a finite phase torus, Point convergence for compact analytic periodic gradient flows, A null basin for all strict saddles of a smooth compact gradient flow).

[F3]

For the cosine-difference energy, the gradient at $x$ is $\sum_{y : {x, y} \in E} \sin (θ_{x} - θ_{y})$ , and its Hessian quadratic form at $θ$ is $\sum_{{x, y} \in E} \cos (θ_{x} - θ_{y}) (h_{x} - h_{y})^{2}$ . Sine is odd; its real zeros are integer multiples of $π$ , and cosine is $1$ at even and $- 1$ at odd multiples of $π$ (Differentiation of symmetric periodic pair potentials, Phasors, trigonometric identities and periodic derivatives, The zero sets of sine and cosine and the least positive common period 2 pi, Quarter-turn values and shifts by pi/2 and pi).

[F4]

Deleting any edge of a finite tree separates it into two tree components. A real symmetric Hessian with a negative quadratic-form direction has a negative eigenvalue (Deleting any edge of a tree separates it into exactly two tree components, Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis).

[F5]

On a cycle of length $n \geq 5$ , the winding-one state $θ_{j}^{*} = 2 π j / n$ is an equilibrium and its Hessian is positive on the subspace of vectors with coordinate sum zero. For a smooth rotation-invariant potential, such an equilibrium whose rotation orbit contains no synchronized state attracts a nonempty open set of positive phase volume; those initial states do not converge to the synchronized set (Twisted cycle equilibria and transverse positivity, A positive transverse Hessian gives an open nonsynchronous basin).

Proof

Given: A finite nonempty tree, or an unweighted cycle of length greater than five, with the homogeneous Kuramoto dynamics and countable choice.

Goal: Prove the stated probability-one synchronization and nonsynchronization claims, and exhibit an edge addition that destroys global synchrony.

1.1F3F4algebra

Let $T$ be a tree and $θ$ a critical point of its energy. Fix an edge $e = {a, b}$ and delete it. By [F4], one component has vertex set $S$ with $a \in S$ and $b \notin S$ , and $e$ is the only edge crossing from $S$ to its complement. Sum the zero gradient components over $S$ . By [F3], contributions of edges internal to $S$ cancel in pairs, leaving $\sin (θ_{a} - θ_{b}) = 0$ . Thus every edge difference is an integer multiple of $π$ .

1.2F5algebra

Let $n > 5$ . The cycle energy is smooth and invariant under common phase rotation. By [F5], its winding-one state is an equilibrium with positive Hessian on the coordinate-sum-zero subspace. Its neighboring phases differ by $2 π / n$ , which is not zero modulo $2 π$ , so no common rotation of this state is synchronized. The positive-basin assertion in [F5] gives a positive-volume set of initial states that do not converge to the synchronized set. Thus the cycle is not globally synchronizing.

2.1F3F4step 1.1algebra

If some edge has odd-multiple difference, delete it and take $h$ to be $1$ on one component and $0$ on the other. All terms in the Hessian form in [F3] vanish except that edge, whose contribution is $- 1$ . By [F4], the critical point has a negative Hessian eigenvalue. Otherwise every edge joins equal phases modulo $2 π$ ; connectedness of the tree makes all phases equal. This also covers the one-vertex tree, for which there are no edges.

3.1F1F2step 2.1

By [F1] and [F2], every rotating-frame trajectory converges to one critical point. By step 2.1, a nonsynchronized critical point has a negative Hessian eigenvalue; [F2] makes the set converging to any such point null. Every other trajectory therefore converges to an individual synchronized state, establishing global synchrony as defined in the Statement.

4.1step 3.1step 1.2algebra∎

Delete one edge from this cycle. The remaining graph is a path on the same vertices, hence a tree: consecutive remaining edges connect all vertices and no cycle remains. By step 3.1 it is globally synchronizing, while restoring the deleted edge produces the nonsynchronizing cycle of step 1.2. This is the required edge-addition example.

Source notes

The tree, cycle and edge-addition assertions are attributed to Expander graphs are globally synchronizing, PDF pp. 8–9, Remark 1.8 and Section 1.5. The article is not used as proof of these assertions.

Depends on

Used by · 2

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 pp. 8–9, Remark 1.8 and Section 1.5