LemmaStatement: AI-generatedProof: 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.

Uniform spectral control transfers past connectivity

Statement

Assume countable choice. Use the independent-label process, its exponential-clock form $H_{t}$ , and $p_{0} = 3 \log n / (4 n)$ , $t_{0} = - \log (1 - p_{0})$ , $d (t) = (n - 1) (1 - e^{- t})$ . Let $Q$ be any predicate on connected graphs with the deterministic property that $κ (G) < 2$ implies $Q (G)$ . Suppose a constant $C > 0$ , independent of $n$ , and events $E_{n}$ of probability tending to one satisfy: for every $t \geq t_{0}$ for which $H_{t}$ is connected, $η (H_{t}) < C / \sqrt{d (t)}$ . Then with probability tending to one, $Q (G (n, m))$ holds simultaneously for every $τ \leq m \leq (\binom{n}{2})$ .

Facts & Assumptions

[F1]

Normalized Laplacians and the quantities $η$ and $κ$ are defined in Normalized graph Laplacian and its nontrivial spectrum; a spectral window of width less than $1 / 3$ implies $κ < 2$ by A spectral window giving condition number below two.

[F2]

The exponential-clock process has the uniform edge ordering, and a pathwise assertion after its connectivity time transfers to every later edge index (Exponential clocks and the uniform edge-order process).

[F3]

With probability tending to one the graph at $p_{0}$ has an isolated vertex, so the connectivity time is later than $t_{0}$ (An isolated vertex before three quarters of the connectivity scale).

[F4]

A probability measure is a nonnegative countably additive measure of total mass one, and high probability means convergence of event probabilities to one (Probability measures and probability spaces, Asymptotic quantifiers and uniform parameter ranges).

[A1]

Countable choice is assumed in the sense of The Axiom of Countable Choice (AC_ω); it supplies the hypothesis required to invoke the process-transfer and isolated-vertex results in [F2] and [F3].

Proof

Given: The objects and hypotheses in the statement.

Goal: Establish all stated claims.

1.1A1F2F3F4algebra

Under [A1], intersect $E_{n}$ with the event in [F3] and the probability-one coupling event in [F2]. The complement of this intersection has probability at most the sum of the first two failure probabilities: decompose the union into the first event and the portion of the second outside it, use additivity on these disjoint sets, and then monotonicity. Thus the intersection still has probability tending to one.

2.1givenF2F3F4step 1.1algebra

On this intersection, the connectivity time $s_{τ}$ exceeds $t_{0}$ . For every $t \geq s_{τ}$ , connectedness persists and the assumed bound applies. Since $p (t)$ is increasing, $d (t) \geq d (t_{0}) = 3 (n - 1) \log n / (4 n) \to \infty$ . Therefore, for all sufficiently large $n$ , the common upper bound $C / \sqrt{d (t_{0})}$ is less than $1 / 3$ , simultaneously for all such $t$ .

3.1givenF1F2step 1.1step 2.1∎

By [F1], every graph on this whole time interval has $κ < 2$ , so the assumed deterministic implication gives $Q (H_{t})$ . Applying [F2] at every edge arrival proves the single simultaneous assertion for all indices from $τ$ to $(\binom{n}{2})$ . The intersection already has probability tending to one, which proves the claim.

Depends on

Used by · 1

Simultaneous global synchronization from connectivity

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.