Destroying cycle spurious minima by bounded-degree edge additions

Let $B_1$ and $B_2$ be the failure events for synchronization and Hamiltonicity, respectively, in the same uniform random regular graph space. By [F1], [F2] and [F5], $\mathbb{P}(B_1\cup B_2)\le \mathbb{P}(B_1)+\mathbb{P}(B_2)\to 0$. Hence the simultaneous event has probability tending to one and, for all sufficiently large feasible $n$, has positive probability. Every $n\ge 601$ is feasible: on vertices modulo $n$, joining vertices whose cyclic distance is one of $1,\dots ,300$ gives a simple $600$-regular graph. Thus, for every sufficiently large integer $n$, the simultaneous event is nonempty, and at least one simple $600$-regular graph $G$ has both properties.

Choose a Hamiltonian cycle $H$ in $G$ and let $S=E(G)\setminus E(H)$. Each vertex has two incident edges in $H$ and $600$ in $G$, so it has exactly $598$ incident edges in $S$. A bijection $\sigma :V\to W$ preserving cyclic order maps $H$ to the prescribed $C_n$ on $W$. Apply it to every edge of $G$ to obtain $G^{\mathrm{\prime }}$; the image of $S$ consists of new edges disjoint from $C_n$, with exactly $598$ incident to each vertex. The adjacency matrices obey $A_{\sigma (x),\sigma (y)}^{\mathrm{\prime }}=A_{xy}$.

Define $P:T_V\to T_W$ by $(P\theta {)}_{\sigma (x)}={\theta }_x$. It is well defined modulo $2\pi$, with inverse induced by ${\sigma }^{-1}$. If $\theta (t)$ is a homogeneous Kuramoto trajectory for $G$, then $\psi (t)=P\theta (t)$ satisfies ${\dot{\psi }}_{\sigma (x)}=\omega -{\sum }_{y\in V}{A}_{\sigma (x),\sigma (y)}^{\mathrm{\prime }}\sin ({\psi }_{\sigma (x)}-{\psi }_{\sigma (y)})$. Reindexing this finite sum over $W$ gives exactly the equation for $G^{\mathrm{\prime }}$. Its initial state is $P\theta (0)$, so uniqueness in [F6] identifies it with that graph's trajectory. Since $P$ commutes with subtracting $\omega t$ from every coordinate, it also conjugates the rotating-frame trajectories.

Order $V$ arbitrarily and order $W$ by transporting that ordering through $\sigma$. In these coordinate identifications $P$ leaves the representative tuple in $(-\pi ,\pi {]}^n$ unchanged. By [F7], it therefore carries phase-measurable sets to phase-measurable sets with the same normalized volume. The same coordinate identification shows that $P$ is an isometry for the flat torus distance and carries fully synchronized states to fully synchronized states. Let $N$ be the phase-null exceptional set for $G$. For each initial state outside $P(N)$, its inverse image lies outside $N$, so its rotating-frame trajectory for $G$ converges to a fully synchronized point. By step 3.1 and the isometry, the corresponding trajectory for $G^{\mathrm{\prime }}$ converges to the image of that point. Since $P(N)$ is phase-null, $G^{\mathrm{\prime }}$ is globally synchronizing.

If the augmented graph had a spurious local minimum, [F3] would rule out its global synchrony, contradicting step 4.1. Thus it has no spurious local minima. For $n>5$, [F4] also shows that the original cycle was not globally synchronizing. This proves all assertions.