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

Chernoff bounds with the exact degree mean

Statement

Let $n \geq 2$ be an integer and $p \in [0, 1]$ . In $G (n, p)$ , the simple graph on $[n] = {1, \dots, n}$ whose possible edges occur independently with probability $p$ , let $d (v)$ be the number of edges incident to $v$ and put $μ = (n - 1) p$ . For $0 \leq δ \leq 1$ , $P (\exists v : ∣ d (v) - μ ∣ \geq δ μ) \leq 2 n \exp (- μ δ^{2} / 3) .$ No independence between different vertex degrees is required. If $1 / n \leq ε \leq 1$ , then the estimate centered at $p n$ is $P (\exists v : ∣ d (v) - p n ∣ \geq ε p n) \leq 2 n \exp (- \frac{p (n ε - 1)^{2}}{3 (n - 1)}) .$ In particular, for fixed $0 < ε \leq 1$ and $p = γ \log n / n \in [0, 1]$ , if $γ \geq γ_{0} > 3 / ε^{2}$ , the latter probability tends to zero uniformly over such $γ$ as $n \to \infty$ . The same conclusion holds when $γ \to \infty$ , subject to $p \leq 1$ .

Statement references

Single-vertex degree laws and the shared-edge dependence

Chernoff bound for independent bernoulli trials

The finite union bound

Facts & Assumptions

Given: The graph and parameters in the Statement.

Goal: Prove the exact-mean and translated simultaneous degree bounds and the stated logarithmic-density consequence.

[F1]

Each $d (v)$ is the sum of the $n - 1$ mutually independent Bernoulli $(p)$ indicators of the possible edges incident to $v$ . (Single-vertex degree laws and the shared-edge dependence)

[F2]

For a finite sum of independent Bernoulli variables with mean $μ$ , the two-sided deviation probability at $δ μ$ is at most $2 \exp (- μ δ^{2} / 3)$ when $0 \leq δ \leq 1$ , including $μ = 0$ . (Chernoff bound for independent bernoulli trials)

[F3]

The probability of a finite union of events is at most the sum of their probabilities; independence of the events is unnecessary. (The finite union bound)

Proof

technique · Apply the single-vertex tail bound and then the finite union bound; translate the center before selecting the deviation parameter

1.1F1F2F3

For each vertex, [F1] gives a sum to which [F2] applies with mean $(n - 1) p = μ$ . Thus its probability of deviation at least $δ μ$ is at most $2 \exp (- μ δ^{2} / 3)$ . Applying [F3] to the $n$ vertex events proves the first displayed inequality, regardless of dependence among degrees.

2.1step 1.1algebra

Since $p n - μ = p$ , the triangle inequality gives $∣ d (v) - μ ∣ \geq ∣ d (v) - p n ∣ - p$ . If $1 / n \leq ε \leq 1$ , put $δ = (n ε - 1) / (n - 1)$ ; then $0 \leq δ \leq 1$ and $δ μ = ε p n - p$ . Hence every event $∣ d (v) - p n ∣ \geq ε p n$ is contained in $∣ d (v) - μ ∣ \geq δ μ$ . The first bound therefore gives the second, including $p = 0$ .

3.1step 2.1algebra∎

For fixed $0 < ε \leq 1$ , the restriction $1 / n \leq ε$ holds for all sufficiently large $n$ . Substituting $p = γ \log n / n$ in the second bound yields $2 n^{1 - γ a_{n}}$ , where $a_{n} = (n ε - 1)^{2} / (3 n (n - 1)) \to ε^{2} / 3$ . If $γ \geq γ_{0} > 3 / ε^{2}$ , choose $c > 1$ with $γ_{0} a_{n} \geq c$ for all sufficiently large $n$ ; the probability is then at most $2 n^{1 - c}$ uniformly in $γ$ . A sequence with $γ \to \infty$ eventually exceeds such a fixed $γ_{0}$ , so the same conclusion follows whenever the specified $p$ is a probability.

Depends on

Used by · 3

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.