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.

Components between two vertices and half the graph disappear in the window

Statement

Suppose $p = (\log n + c_{n}) / n$ , where $(c_{n})$ is bounded and $p \in [0, 1]$ . In $G (n, p)$ , the probability of a component of order $k$ with $2 \leq k \leq n / 2$ tends to zero.

Facts & Assumptions

[F1]

For the component count $X_{k}$ , $E X_{k} \leq (\binom{n}{k}) k^{k - 1} p^{k - 1} (1 - p)^{k (n - k)}$ (A parent-map bound for isolated components).

[F2]

A bounded sequence is eventually bounded in absolute value, and $O$ and $o$ have their stated sequence meanings (Asymptotic quantifiers and uniform parameter ranges).

[F3]

For integers $N \geq k \geq 1$ and $0 < p < 1$ , the binomial exponential envelope includes $(\binom{N}{k}) \leq N^{k} / k!$ , $k! \geq (k / e)^{k}$ and $1 - p \leq e^{- p}$ . Here $e = \exp (1)$ , and throughout this proof $e^{s}$ denotes $\exp (s)$ (Elementary binomial probability envelopes).

[F4]

For every $a > 0$ , $\log n / n^{a} \to 0$ (The logarithm grows more slowly than every positive real power).

[F5]

The model is the simple independent-edge graph (The Erdős-Rényi finite random graph G(n,p)).

[F6]

Component order is the cardinality of its vertex set (Connected graphs and connected components defined by the existence of vertex paths).

[F7]

The expectation is the sum of values times outcome weights (Expectation of a real random variable on a finite probability space).

[F8]

The binomial coefficient $(\binom{n}{k})$ counts the $k$ -element subsets of an $n$ -element set (The set [A]ᵏ of k-element subsets and the binomial coefficient C(n, k) := | [n]ᵏ|).

[F9]

The factorial is the positive product $k! = \prod_{j = 1}^{k} j$ (The factorial n! and the falling factorial n^k̲, defined by recursion in ℕ).

[F10]

The indicator $1_{E}$ of an event $E$ equals one on $E$ and zero off $E$ (The indicator random variable of an event).

[F11]

The logarithm is continuous and strictly increasing on $(0, \infty)$ , is onto $R$ , and satisfies $\log 1 = 0$ . It is inverse to the exponential, so $\exp (\log x) = x$ for $x > 0$ and $\log (\exp s) = s$ for real $s$ (Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm, The natural logarithm as the inverse of the exponential function).

[F12]

The exponential is continuous and strictly increasing on $R$ , and $\exp (s + t) = \exp (s) \exp (t)$ for real $s, t$ (The exponential function is strictly increasing, The exponential addition formula exp(x+y)=exp(x)exp(y)). In the inverse pair in [F11] its values are positive; $\exp (0) = \exp (\log 1) = 1$ , so the addition law also gives $\exp (- s) = 1 / \exp (s)$ .

Proof

Given: The objects and hypotheses of the Statement.

Goal: Prove that the probability of any component of order between two and half the graph tends to zero.

1.1F2F3F4F8F9F11algebra

Choose $C > 0$ with $∣ c_{n} ∣ \leq C$ eventually and set $a = n p = \log n + c_{n}$ . By [F11], $\log n \to + \infty$ : for any real $M$ , choose $x_{M} > 0$ with $\log x_{M} = M$ and then use monotonicity for $n > x_{M}$ . Hence eventually $\frac{1}{2} \log n \leq a \leq 2 \log n$ , $a > 1$ and $0 < p < 1$ , since [F4] with exponent $1$ gives $\log n / n \to 0$ . For $1 \leq k \leq n$ , [F3] with $N = n$ and this admissible $p$ gives $1 - p \leq \exp (- p)$ and $(\binom{n}{k}) \leq (e n / k)^{k}$ . These inequalities apply to every component index used below.

2.1F1F2F3F4F11F12step 1.1algebra

Fix an integer $k$ between $2$ and $10$ . From [F1] and [F3], raising the nonnegative inequality $1 - p \leq \exp (- p)$ to the integer power $k (n - k)$ and using the exponential addition law gives $E X_{k} \leq (k^{k - 1} / k!) n^{k} p^{k - 1} \exp (- p k (n - k))$ for sufficiently large $n$ . By [F11] and [F12], $\exp (- p k (n - k)) = n^{- k} \exp (- k c_{n} + k^{2} a / n)$ . Here $a / n \to 0$ by step 1.1 and [F4], and $∣ c_{n} ∣ \leq C$ , so the final exponential factor is bounded, for example by $\exp (k C + 1)$ eventually. Thus $E X_{k} = O ((\log n / n)^{k - 1}) \to 0$ . There are only nine such fixed values of $k$ , so their sum tends to zero.

2.2F1F2F4F11F12step 1.1algebra

For $11 \leq k \leq n / 2$ , [F1] and step 1.1 give $E X_{k} \leq (k p)^{- 1} [e n p \exp (- n p / 2)]^{k} \leq p^{- 1} q_{n}^{k}$ , where $q_{n} = e a \exp (- a / 2)$ . The inverse relation and addition law imply $\exp (- \log n / 2) = 1 / \sqrt{n}$ : both sides are positive and their squares equal $1 / n$ . Consequently $q_{n} = e a \exp (- c_{n} / 2) / \sqrt{n} = O (\log n / \sqrt{n}) \to 0$ by [F4]. Eventually $0 < q_{n} < 1 / 2$ , and $p^{- 1} = n / a = O (n / \log n)$ . Multiplying a finite geometric sum by $1 - q_{n}$ and discarding its nonnegative last term yields $\sum_{k = 11}^{⌊ n / 2 ⌋} E X_{k} \leq p^{- 1} q_{n}^{11} / (1 - q_{n}) = O ((\log n)^{10} / n^{9 / 2}) \to 0$ . For the final limit use [F4] with exponent $9 / 20$ and take the tenth power. An empty index range has sum zero and obeys the same bound.

3.1F5F6F7F10step 2.1step 2.2algebra∎

The indicator that any such component exists is at most $\sum_{k = 2}^{⌊ n / 2 ⌋} X_{k}$ , pointwise on the finite graph space. By the finite weighted-sum expectation, its expectation is the event probability and is at most the sum of the component expectations. Steps 2.1 and 2.2 show that this sum tends to zero, proving the Statement.

Depends on

Used by · 1

Connectivity in the logarithmic random-graph window

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.