CorollaryStatement: 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.

Ramanujan and typical regular graphs synchronize for degree at least 600

PDF p. 1: Abstract; PDF p. 7: Corollary 1.6 and its proof; PDF p. 28: Section 5 opening

Statement

Assume countable choice. Every $d$ -regular Ramanujan graph with $d \geq 600$ is globally synchronizing. For each fixed integer $d \geq 600$ , a uniformly random labelled simple $d$ -regular graph is globally synchronizing with high probability as its number of vertices tends to infinity through feasible orders. In this range $2 \sqrt{d - 1} / d < 0.0816$ .

Here a graph is finite and undirected, with at most one edge between a pair of vertices; loops are allowed in the deterministic assertion and count once in degrees. Its adjacency matrix is $A$ , its vertex count is $n > 0$ , and $J$ is the all-ones matrix. It is $d$ -regular when each adjacency row sum is $d$ , and it is Ramanujan in the article's convention when $∥ A - (d / n) J ∥_{o p} \leq 2 \sqrt{d - 1}$ . The operator norm is induced by the Euclidean norm. Global synchrony means that, for phase-volume almost every initial state, the homogeneous Kuramoto trajectory in the rotating frame converges to a state with all phases equal.

In the random assertion, simple means no loops or repeated edges, the law is uniform over all labelled simple $d$ -regular graphs on ${1, \dots, n}$ , and a feasible order is one for which this set is nonempty. With high probability means that the probability tends to one along feasible orders, with $d$ fixed.

Statement references

Ramanujan graph convention used in the article

Globally synchronizing graph — Definition 1.1

Uniform random regular graph convention

The Axiom of Countable Choice (AC_ω)

Facts & Assumptions

[F1]

An $(n, d, α)$ -expander has $∥ A - (d / n) J ∥_{o p} \leq α d$ . The stated Ramanujan convention gives this inequality with $α = 2 \sqrt{d - 1} / d$ (Adjacency spectral expander — Definition 1.3, Ramanujan graph convention used in the article).

[F2]

Under countable choice, every $d$ -regular $(n, d, α)$ -expander with $d > 0$ and $α \leq 0.0816$ is globally synchronizing, including graphs with loops counted once in degrees (Regular spectral expansion implies synchronization — Theorem 1.4, The Axiom of Countable Choice (AC_ω)).

[F3]

For every fixed integer $d \geq 3$ and fixed $ε > 0$ , a uniform labelled simple $d$ -regular graph is, with high probability along feasible orders, an $(n, d, α)$ -expander for $α = (2 \sqrt{d - 1} + ε) / d$ (Typical regular graphs are almost Ramanujan, Uniform random regular graph convention).

Proof

Given: Countable choice and an integer $d \geq 600$ ; for the random assertion, $d$ remains fixed while feasible orders tend to infinity.

Goal: Prove the deterministic and high-probability synchronization assertions and the numerical inequality.

1.1givenalgebra

Since $d \geq 600$ , $(d - 600) (599 d - 600) \geq 0$ . Expanding and dividing by $90000 d^{2} > 0$ gives $4 (d - 1) / d^{2} \leq 599 / 90000$ . Moreover $599 \cdot 390625 = 233984375 < 234090000 = 2601 \cdot 90000$ , so $599 / 90000 < (51 / 625)^{2} = (0.0816)^{2}$ . Both sides being nonnegative, $2 \sqrt{d - 1} / d < 0.0816$ .

2.1F1F2step 1.1

For a $d$ -regular Ramanujan graph, [F1] gives the expander condition with $α = 2 \sqrt{d - 1} / d$ . By step 1.1 this parameter is below $0.0816$ , and $d > 0$ . Applying [F2] proves global synchrony.

3.1F2F3step 1.1algebra∎

Set $ε = \frac{d}{2} (0.0816 - 2 \sqrt{d - 1} / d)$ . By step 1.1 this is a fixed positive number, and $(2 \sqrt{d - 1} + ε) / d < 0.0816$ . By [F3], the corresponding expander event has probability tending to one. On that event [F2] gives global synchrony; therefore the probability of global synchrony also tends to one. This proves the random assertion.

Source notes

The article's Corollary 1.6 and its proof state the two synchronization conclusions and use the threshold $0.0816$ . The source reference is attribution; the argument above uses the declared suppliers.

Depends on

Used by · 1

Destroying cycle spurious minima by bounded-degree edge additions

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. 1, Abstract; p. 7, Corollary 1.6 and proof; p. 28, Section 5 opening