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.

Simultaneous degree deviations on the squared logarithmic scale

Statement

Fix $c > 0$ and let $G \sim G (n, p)$ with $n p = d \geq c (\log n)^{2}$ and $p \leq 1$ . Put $μ = (n - 1) p$ and $t = \sqrt{12 μ \log n}$ . Eventually, with probability at least $1 - 2 n^{- 3}$ , every loop-free degree $d_{i}$ satisfies $∣ d_{i} - μ ∣ < t \leq \sqrt{12 d \log n}$ . The statement applies along every sequence of allowed probabilities.

Facts & Assumptions

Given: The data and hypotheses in the Statement.

Goal: Establish the conclusions in the Statement.

[F1]

The exact-mean Chernoff union estimate is $P (\exists i : ∣ d_{i} - μ ∣ \geq δ μ) \leq 2 n e^{- μ δ^{2} / 3}$ for $0 \leq δ \leq 1$ (Chernoff bounds with the exact degree mean); the graph law and sequence quantifiers are those of Single-vertex degree laws and the shared-edge dependence and Asymptotic quantifiers and uniform parameter ranges.

Proof

1.1F1algebra

Because $μ = (1 - 1 / n) d \geq (c / 2) (\log n)^{2}$ eventually, $δ = \sqrt{12 \log n / μ}$ is eventually at most one and $δ μ = t$ .

2.1F1step 1.1algebra∎

Substitution in the union bound gives $2 n \exp (- 4 \log n) = 2 n^{- 3}$ . Finally $μ \leq d$ gives the stated envelope.

Depends on

Used by · 2

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.