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.

An isolated vertex before three quarters of the connectivity scale

Statement

Assume countable choice. In the independent-label process on $n \geq 2$ vertices, use its exponential-clock form $H_{t} = G_{p (t)}$ , where $p (t) = 1 - e^{- t}$ for $t \geq 0$ , and define its connectivity clock time by $s_{τ} = \min {t \geq 0 : H_{t} is connected}$ . Put $p_{0} = 3 \log n / (4 n)$ for sufficiently large $n$ that $0 < p_{0} < 1$ . With probability tending to one, $G_{p_{0}}$ has an isolated vertex and is therefore disconnected. Consequently $s_{τ}$ is strictly later than $t_{0} = - \log (1 - p_{0})$ on the same event.

Facts & Assumptions

[F1]

At each fixed threshold $p$ , the possible edges are independent Bernoulli variables of parameter $p$ ; connectivity persists as the threshold grows (Uniform edge orderings, graph-process times and independent labels).

[F2]

A finite probability law consists of nonnegative outcome weights summing to one, and event probabilities are sums of those weights (Finite probability spaces, outcome weights, events, and event probabilities). For a real function $Y$ on that finite space, its expectation is $E Y = \sum_{ω} Y (ω) w (ω)$ (Expectation of a real random variable on a finite probability space).

[F3]

The conventions for tending to zero and high probability are those of Asymptotic quantifiers and uniform parameter ranges.

[F4]

The natural logarithm has the usual inverse and product laws, and $\log x = \int_{1}^{x} d u / u$ for $x > 0$ (Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm, The integral logarithm L is the published natural logarithm, The integral logarithm L(x):=∫₁ˣdt/t for x>0).

[F5]

The clocks $T_{e} = - \log (1 - U_{e})$ are finite and satisfy $H_{t} = G_{p (t)}$ with $p (t) = 1 - e^{- t}$ . Almost surely their strict ordering is the uniform edge ordering, and the first connected clock time is $s_{τ}$ , the arrival time of the edge with connectivity index $τ$ (Exponential clocks and the uniform edge-order process).

Proof

Given: The objects and hypotheses in the statement.

Goal: Establish all stated claims.

1.1givenF1F2algebra

Fix $p = p_{0}$ and let $E$ be the set of possible edges, with $N = ∣ E ∣ = (\binom{n}{2})$ . On the finite configuration space $Ω_{p} = {0, 1}^{E}$ , put $w_{p} (ω) = \prod_{e \in E} p^{ω_{e}} (1 - p)^{1 - ω_{e}}$ . These weights are nonnegative and sum to $\prod_{e \in E} (p + (1 - p)) = 1$ by finite distributivity. By independence, the label-process indicator vector $(1_{{U_{e} \leq p}})_{e \in E}$ equals each configuration $ω$ with probability $w_{p} (ω)$ ; summing these disjoint configuration probabilities shows that every graph event has the same probability in the two models. All expectations below are the finite weighted sums on $(Ω_{p}, w_{p})$ .

2.1F1F2step 1.1algebra

On this finite space, let $I_{v}$ indicate that vertex $v$ is isolated and put $X = \sum_{v} I_{v}$ . Then $q : = P (I_{v} = 1) = (1 - p)^{n - 1}$ , and for distinct $u, v$ one has $P (I_{u} = I_{v} = 1) = (1 - p)^{2 n - 3}$ , since there are $2 n - 3$ distinct edges incident to at least one of them. Expanding the finite sums defining expectation, and using $I_{v}^{2} = I_{v}$ , gives $E X = n q$ and $E X^{2} = n q + n (n - 1) (1 - p)^{2 n - 3}$ .

3.1step 2.1F2algebra

Define $Var X = E (X - E X)^{2}$ . Dividing the preceding expressions yields $Var X / (E X)^{2} = 1 / (n q) + (n - 1) / (n (1 - p)) - 1 \leq 1 / (n q) + p / (1 - p)$ . On ${X = 0}$ , the squared difference equals $(E X)^{2}$ , so summing nonnegative weights gives $P (X = 0) \leq Var X / (E X)^{2}$ .

4.1givenF3F4step 3.1algebra

The integral identity gives $- \log (1 - p) = \int_{1 - p}^{1} d u / u \leq p / (1 - p)$ . Also $\log n \leq 2 \sqrt{n}$ follows by integrating $1 / u \leq 1 / \sqrt{u}$ from $1$ to $n$ , so $p \to 0$ . Eventually $p \leq 1 / 7$ , and hence $\log (n q) = \log n + (n - 1) \log (1 - p) \geq \log n - (n - 1) p / (1 - p) \geq (1 / 8) \log n$ . Thus $n q \geq n^{1 / 8}$ and step 3.1 bounds $P (X = 0)$ by $n^{- 1 / 8} + p / (1 - p) \to 0$ .

5.1givenF1F3F4F5step 1.1step 4.1∎

By the agreement of graph-event probabilities in step 1.1, the label-process graph $G_{p_{0}}$ has an isolated vertex with probability tending to one. On this event it is disconnected, since $n \geq 2$ and an isolated vertex has no path to any other vertex. The finite clocks ensure that the complete graph is attained at a finite time, and the first connected time is a minimum, since the graph changes only at finitely many clock values. The inverse laws give $p (t_{0}) = p_{0}$ , so $H_{t_{0}} = G_{p_{0}}$ is disconnected. Connectivity persists under edge addition, so its first connected time $s_{τ}$ must exceed $t_{0}$ . This proves all claims on the same high-probability event.

Depends on

Used by · 1

Uniform spectral control transfers past 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.