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

Expected degree-count bound and logarithmic factorial estimate

PDF p. 37: Proof of Proposition 6.9, first estimates

Statement

Let $n \geq 2$ and $1 \leq k \leq n - 1$ be integers, let $γ > 0$ , and suppose $p = γ \log n / n$ satisfies $0 < p < 1$ . In the random simple graph $G (n, p)$ , each possible edge occurs independently with probability $p$ ; let $X_{k}$ count vertices incident to exactly $k$ edges. Then

$E X_{k} = n (\binom{n - 1}{k}) p^{k} (1 - p)^{n - k - 1} \leq n^{1 - γ} \frac{(γ \log n)^{k}}{k!} e^{2 p k} .$

Put $L_{k} = (\log n)^{k} / k!$ and $δ = k / \log n > 0$ . Then

$\log L_{k} \leq (δ - δ \log δ) \log n$

and

$E X_{k} \leq \exp ((1 - γ + δ - δ \log δ + δ \log γ) \log n + 2 p k) .$

For $c > - 1$ let $h (c) = (1 + c) \log (1 + c) - c$ . If $δ = γ (1 + c + s)$ with $1 + c + s > 0$ , the exponent is $(1 - γ h (c + s)) \log n + 2 p k$ . In particular, if $0 < ε < 1$ , $1 + ε < γ < 1 + ε^{- 2}$ , and $c^{\pm} = c^{\pm} (γ, ε)$ are the shifted roots defined by $γ h (c^{-} - ε) = γ h (c^{+} + ε) = 1 + ε$ , then the respective choices $δ = γ (1 + c^{-} - ε)$ and $δ = γ (1 + c^{+} + ε)$ give $E X_{k} \leq \exp (- ε \log n + 2 p k)$ whenever the chosen $δ \log n$ is an integer in $[1, n - 1]$ .

Statement references

Counts of vertices of each degree

Degree large-deviation rate function and roots

Shifted rate roots for quantitative expansion

Real powers for positive bases, with the zero-base positive-exponent convention

Facts & Assumptions

[F1]

The degree-count definition specifies $G (n, p)$ , its independent edge indicators, and $X_{k}$ as the number of vertices of degree $k$ (Counts of vertices of each degree).

[F2]

For identically distributed integer-valued variables, the expectation of the number equal to $k$ is $n$ times their common mass at $k$ (Indicator expectations and exceptional-vertex probabilities). A sum of $N$ independent Bernoulli $(p)$ variables has mass $(\binom{N}{k}) p^{k} (1 - p)^{N - k}$ at $k$ (The Binomial count has its usual probability mass function).

[F3]

For $1 \leq k \leq N$ and $0 < p < 1$ , the binomial envelope is $(N p)^{k} e^{- p (N - k)} / k!$ (Elementary binomial probability envelopes). For positive integer $k$ , $k! \geq (k / e)^{k}$ (Elementary estimates used for degree expectations).

[F4]

The natural logarithm turns positive products and powers into sums and scalar multiples; the exponential is increasing and turns sums into products (Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm, The exponential function is strictly increasing, The exponential addition formula exp(x+y)=exp(x)exp(y)). For $a > 0$ and real $x$ , $a^{x} = \exp (x \log a)$ (Real powers for positive bases, with the zero-base positive-exponent convention).

[F5]

The rate function is $h (t) = (1 + t) \log (1 + t) - t$ for $t > - 1$ (Degree large-deviation rate function and roots). Under the stated shifted-root parameter hypotheses, the two roots have positive logarithm arguments and satisfy the displayed equations (Shifted rate roots for quantitative expansion).

Proof

Given: The integers, parameters, graph and notation in the Statement.

Goal: Establish the expectation identity and bounds, including the conditional shifted-rate specialization.

1.1givenF1F2F3F4algebra

Each vertex has $n - 1$ possible incident edges. By their independence and common probability, its degree has the binomial law with parameters $n - 1, p$ ; the degree laws are identical. Applying [F2] gives the stated exact expectation. Applying [F3] with $N = n - 1$ gives $E X_{k} \leq n ((n - 1) p)^{k} e^{- p (n - 1 - k)} / k!$ . Since $(n - 1) p \leq n p = γ \log n$ , $p n = γ \log n$ , and $k + 1 \leq 2 k$ , the real-power identity $n \exp (- γ \log n) = n^{1 - γ}$ from [F4], exponential laws and monotonicity give the first displayed bound.

1.2givenF3F4algebra

The factorial estimate in [F3] and the logarithm laws give $\log L_{k} \leq k \log \log n - k \log k + k$ . Substituting $k = δ \log n$ and $\log k = \log δ + \log \log n$ yields $\log L_{k} \leq (δ - δ \log δ) \log n$ . All logarithm arguments are positive because $n \geq 2$ and $k \geq 1$ .

2.1step 1.1step 1.2F4F5algebra

Write the first bound as $n^{1 - γ} γ^{k} L_{k} e^{2 p k}$ . Using step 1.2, $k = δ \log n$ , and [F4] gives the stated exponential bound. If $δ = γ (1 + c + s)$ , logarithm laws reduce its coefficient of $\log n$ to $1 - γ + γ (1 + c + s) - γ (1 + c + s) \log (1 + c + s) = 1 - γ h (c + s)$ .

3.1givenF5step 2.1algebra∎

For the lower shifted root take $s = - ε$ , and for the upper root take $s = ε$ . The respective equations in [F5] make $1 - γ h (c + s) = - ε$ . Substitution in step 2.1 proves the last bound whenever its stated integer and range conditions hold.

Source notes

The cited article, PDF p. 37, attributes these estimates to the proof of Proposition 6.9. The proof above uses the stated mathematical suppliers; the article is attribution only. The final specialization here is for exact integer values of $δ \log n$ and does not assert the separate rounding estimate.

Depends on

Used by · 1

Rounded degree thresholds and expectation bounds

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.

Sources

Expander graphs are globally synchronizing · PDF p. 37, proof of Proposition 6.9, first estimates