Critical minimum-degree connectivity parameter

PDF p. 9: Section 1.5, first paragraph

Assume countable choice. A graph here is finite and undirected, with a nonempty vertex set, at most one edge between each pair of vertices, and possible self-loops; a loop contributes once to its vertex degree. For $n$ vertices, $d_{\min }$ is the minimum vertex degree. Global synchronization means that, for the homogeneous Kuramoto system in its rotating frame, a uniformly chosen initial phase state converges to a state in which all phases are equal with probability one; the uniform law is normalized phase volume.

For a real number $a$, say that $a$ has the threshold property if, for every real $\mu >a$, there is an integer $N=N(\mu )$ such that, for every $n\ge N$, every graph on $n$ vertices satisfying $d_{\min }\ge \mu (n-1)$ is globally synchronizing. The critical connectivity threshold ${\mu }_c$ is the smallest real number with the threshold property. Thus the cutoff may depend on $\mu$, but not on the graph of that order.

The Axiom of Countable Choice (AC_ω)

Adjacency, degrees, graph Laplacian, and spectral notation

Globally synchronizing graph — Definition 1.1

Normalized phase volume and almost-everywhere assertions

Asymptotic quantifiers and uniform parameter ranges

Given: The graph, phase-volume and synchronization conventions and countable choice above.

Goal: Show that the smallest real number in the definition exists and is unique.

1.1 Let $B$ be the set of real $b$ such that, for every integer $N$, some nonsynchronizing graph on $n\ge \max \{N,2\}$ vertices satisfies $d_{\min }\ge b(n-1)$. The graphs in [F2] have nonnegative degree and arbitrarily large orders, so $0\in B$. By [F1], $d_{\min }\le n$, and for $n\ge 2$ this gives $d_{\min }\mathrm{/}(n-1)\le 2$. Hence $2$ is an upper bound for $B$. By [F3], $s=\sup B$ exists. [given, F1, F2, F3, algebra]

2.1 If $\mu >s$, then $\mu \mathrm{\notin }B$; negating the defining condition for $B$ gives a cutoff beyond which every graph meeting $d_{\min }\ge \mu (n-1)$ synchronizes. Thus $s$ has the threshold property. If $a<s$, the least-upper-bound property gives some $b\in B$ with $b>a$. Set $\mu =(a+b)\mathrm{/}2$. For every cutoff, the nonsynchronizing graph supplied by $b\in B$ also satisfies the weaker degree bound with parameter $\mu$, so $a$ does not have the threshold property. Consequently $s$ is its unique smallest real number, and the definition is well defined. [step 1.1, F3, algebra] ∎

The critical-threshold formulation is attributed to Expander graphs are globally synchronizing, Section 1.5, first paragraph. The justification uses the independently supplied family and real completeness, rather than the article's threshold claim.