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

Previous Erdős–Rényi synchronization bounds

PDF p. 4: Section 1, previous work and amplification discussion; PDF p. 5: Section 1, previous work and amplification discussion

Statement

Assume countable choice. Let $G (n, p)$ be the simple Erdős–Rényi graph, and consider identical unit-coupled Kuramoto oscillators on it. If $p = p (n) \in [0, 1]$ and $p = Ω ((\log n)^{2} / n)$ , then $G (n, p)$ is globally synchronizing with high probability. The same conclusion holds if $p = Ω (n^{- 1 / 3} \log n)$ .

Here $p = Ω (f (n))$ means that some constant $c > 0$ satisfies $p (n) \geq c f (n)$ for all sufficiently large $n$ . High probability means that the probability tends to one as $n \to \infty$ . Global synchronization means that, outside a phase-volume-null set of initial states, the rotating-frame trajectory converges to a state in which all phases agree.

The article attributes the $n^{- 1 / 3} \log n$ bound to Ling, Xu and Bandeira and the $(\log n)^{2} / n$ improvement to Kassabov, Strogatz and Townsend.

Statement references

Erdős–Rényi random graph and high probability

Globally synchronizing graph — Definition 1.1

Asymptotic quantifiers and uniform parameter ranges

Earlier thresholds with explicit source quantifiers and a fixed-scale deduction

The Axiom of Countable Choice (AC_ω)

Facts & Assumptions

[F1]

Under countable choice, for every fixed $c > 0$ and every sequence $p \in [0, 1]$ satisfying $n p \geq c (\log n)^{2}$ eventually, the probability that the simple $G (n, p)$ is globally synchronizing tends to one. This is the stated local consequence of the independent criterion and concentration inputs in Earlier thresholds with explicit source quantifiers and a fixed-scale deduction.

[F2]

For every $a > 0$ , $\log a \leq a - 1$ (Logarithmic tangent bound and a quadratic entropy envelope). The logarithm laws give $\log n = 3 \log (n^{1 / 3})$ for $n > 0$ (Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm).

Proof

Given: Countable choice and a sequence $p (n) \in [0, 1]$ satisfying either lower bound in the Statement.

Goal: Show that the probability of global synchronization tends to one.

1.1F1givenalgebra

If $p = Ω ((\log n)^{2} / n)$ , then for some fixed $c > 0$ and all sufficiently large $n$ we have $n p \geq c (\log n)^{2}$ . The conclusion follows from [F1].

2.1F1F2givenalgebra∎

Suppose instead that $p \geq c n^{- 1 / 3} \log n$ eventually, for some $c > 0$ . For $n \geq 1$ , [F2] gives $\log n \leq 3 (n^{1 / 3} - 1) \leq 3 n^{2 / 3}$ . For sufficiently large $n$ , $\log n > 0$ , so $n p \geq c n^{2 / 3} \log n \geq (c / 3) (\log n)^{2}$ . Applying [F1] with the fixed positive constant $c / 3$ proves the conclusion.

Source notes

The article's historical attributions are recorded from its Section 1. The argument above obtains both conclusions from the independently supplied squared-logarithmic result; it does not infer dynamical convergence from the separate local-minimum statement of Ling, Xu and Bandeira. The earlier-threshold supplier records the distinction between the published $p ≫ (\log n)^{2} / n$ statement and its locally derived fixed-constant consequence.

Depends on

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. 4, Section 1; PDF p. 5, opening paragraph