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.

Classical Erdős–Rényi connectivity threshold

PDF p. 30: Section 6 opening connectivity formula; PDF p. 31: Section 6 opening connectivity formula; PDF p. 4: Section 1 random graph paragraph

Statement

Let $c_{n}$ be a real sequence such that $p_{n} = (\log n + c_{n}) / n \in [0, 1]$ for all sufficiently large $n$ . In $G (n, p_{n})$ , a graph is connected when every two vertices are joined by a path. As $n \to \infty$ , $P (G (n, p_{n}) is connected)$ tends to $0$ if $c_{n} \to - \infty$ , to $e^{- e^{- c}}$ if $c_{n} \to c \in R$ , and to $1$ if $c_{n} \to + \infty$ .

Here $G (n, p_{n})$ is the simple graph on ${1, \dots, n}$ in which each possible edge is present independently with probability $p_{n}$ . Limits are along the positive integers; the probability spaces may vary with $n$ .

Facts & Assumptions

Given: The sequence and graph law in the Statement.

Goal: Establish the three asserted limits of connectivity probability.

[F1]

The stated graph law is the independent-edge Erdős–Rényi model (Erdős–Rényi random graph and high probability), and connectedness means that the nonempty graph has a path between every pair of vertices (Connected graphs and connected components defined by the existence of vertex paths).

[F2]

Sequence convergence is understood as $n \to \infty$ , with probability spaces allowed to vary with $n$ (Asymptotic quantifiers and uniform parameter ranges).

[F3]

For the independent-edge graph with $p = (\log n + c_{n}) / n \in [0, 1]$ , the connectivity probability has precisely the three limits stated above (Connectivity in the logarithmic random-graph window).

Proof

technique · direct

1.1F1F2F3

By [F1], the graph in the Statement has the independent-edge law and the connectedness convention used in [F3]. Since only sufficiently large $n$ affect the limits in [F2], the eventual condition $p_{n} \in [0, 1]$ supplies the probability-range hypothesis of [F3] on the relevant tail.

2.1F2F3step 1.1∎

Apply [F3] to that tail. Its cases $c_{n} \to - \infty$ , $c_{n} \to c \in R$ , and $c_{n} \to + \infty$ yield respectively $0$ , $e^{- e^{- c}}$ , and $1$ . Thus all three stated limits follow.

Source attribution

The article states this connectivity formula at the opening of Section 6 and identifies $\log n / n$ as the connectivity threshold in its introduction. The citation records attribution; the argument above uses the independent supplier [F3].

Depends on

Used by · 1

Connectivity is necessary but not sufficient for synchrony

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 pp. 30–31, Section 6 opening; PDF p. 4, Section 1 random graph paragraph