Bounds on the critical connectivity threshold

A graph is finite and undirected, has at most one edge between each pair of vertices, and may have loops, each counted once in its vertex degree. Write $d_{\min }$ for its minimum degree. Global synchronization means convergence to an all-equal phase state for almost every initial phase under normalized phase volume. Countable choice is assumed for this convention (Adjacency, degrees, graph Laplacian, and spectral notation, Globally synchronizing graph — Definition 1.1, Normalized phase volume and almost-everywhere assertions, The Axiom of Countable Choice (AC_ω)).

The threshold ${\mu }_c$ is the smallest real number $a$ such that, for each $\mu >a$, there is a cutoff $N(\mu )$ for which every graph on $n\ge N(\mu )$ vertices with $d_{\min }\ge \mu (n-1)$ globally synchronizes (Critical minimum-degree connectivity parameter).

Every simple loop-free graph on $n\ge 2$ vertices with minimum degree at least $3(n-1)\mathrm{/}4$ globally synchronizes. Deleting self-loops leaves the Kuramoto phase dynamics unchanged (Independent inputs for the critical-density bounds).

For each integer $k\ge 3$, there is a simple nonsynchronizing graph on $8k$ vertices with common degree $5k+\lceil k\mathrm{/}2\rceil -2$. Its degree divided by $8k-1$ is less than $11\mathrm{/}16$ and tends to $11\mathrm{/}16$ as $k\to \mathrm{\infty }$ (A simple nonsynchronizing family approaching eleven sixteenths).

For the simple loop-free graphs in [F4], connectedness means that the vertex set is nonempty and every two vertices are joined by a path. A connected component is the induced subgraph on the vertices reachable from a given vertex (Connected graphs and connected components defined by the existence of vertex paths).