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.

Rounded degree thresholds and expectation bounds

PDF p. 37: Proof of Proposition 6.9, rounded thresholds

Statement

Fix $0 < ε < 1$ and $1 + ε < γ < 1 + ε^{- 2}$ . Let $h (x) = (1 + x) \log (1 + x) - x$ for $x > - 1$ , and let $c^{-} < 0 < c^{+}$ be the shifted roots satisfying $γ h (c^{-} - ε) = γ h (c^{+} + ε) = 1 + ε$ , with both logarithm arguments positive. For each sufficiently large integer $n$ , put $p = γ \log n / n$ and define $k^{-} = ⌊ (1 + c^{-} - ε) γ \log n ⌋$ and $k^{+} = ⌈ (1 + c^{+} + ε) γ \log n ⌉$ . The floor is the greatest integer at most its argument and the ceiling is the least integer at least its argument.

In the random simple graph $G (n, p)$ , each possible edge occurs independently with probability $p$ ; let $X_{k}$ count vertices of degree exactly $k$ . Then $1 \leq k^{\pm} \leq n - 1$ , $0 < p < 1$ , and

$E X_{k^{\pm}} \leq \exp (- ε \log n + 2 p k^{\pm} + 4 \log \log n) .$

The threshold for sufficiently large $n$ may depend on $γ$ and $ε$ .

Facts & Assumptions

[F1]

The shifted-root definition supplies the stated positive logarithm arguments and equations (Shifted rate roots for quantitative expansion, Degree large-deviation rate function and roots). The degree-count definition supplies $G (n, p)$ and $X_{k}$ (Counts of vertices of each degree).

[F2]

For $1 \leq k \leq n - 1$ , $0 < p < 1$ , and $δ = k / \log n$ , the degree expectation estimate gives $E X_{k} \leq \exp ((1 - γ + δ - δ \log δ + δ \log γ) \log n + 2 p k)$ (Expected degree-count bound and logarithmic factorial estimate).

[F3]

Floor and ceiling differ from their real argument by at most one (Integer part: for every real x there is exactly one integer m with m ≤ x < m + 1). The logarithm is differentiable with derivative $1 / x$ , and the product and chain rules apply (The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t, Sum, product, quotient, and chain rules from difference quotients). A differentiable real function with derivative bounded in absolute value by $M$ on an interval varies by at most $M$ times the interval length (The mean value inequality: if f : [a,b] → ℝᵐ is continuous and differentiable on (a,b) with ‖ f'‖₂ ≤ M, then ‖ f(b)-f(a)‖₂ ≤ M(b-a)).

[F4]

The logarithm is increasing and obeys the product and quotient laws; the exponential is increasing (Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm, The exponential function is strictly increasing). The logarithm is unbounded above and grows more slowly than the first power at infinity (The integral logarithm is unbounded above and below, The logarithm grows more slowly than every positive real power).

Proof

Given: The fixed parameters, roots, graph, and rounded thresholds in the Statement.

Goal: Prove the degree ranges and both expectation bounds for all sufficiently large $n$ .

1.1F1F3F4algebra

Set $a_{-} = γ (1 + c^{-} - ε)$ and $a_{+} = γ (1 + c^{+} + ε)$ . Both are fixed and positive by [F1]. By [F3], $∣ k^{\pm} - a_{\pm} \log n ∣ \leq 1$ . Since $\log n$ tends to infinity while $\log n / n$ tends to zero by [F4], eventually $0 < p < 1$ , $1 \leq k^{\pm} \leq n - 1$ , and $k^{\pm} / \log n \in [a_{\pm} / 2, 2 a_{\pm}]$ .

2.1F3F4step 1.1algebra

Define $f (x) = 1 - γ + x - x \log x + x \log γ$ for $x > 0$ . The derivative rules give $f^{'} (x) = \log (γ / x)$ . Thus $∣ f^{'} ∣$ is bounded on each fixed interval $[a_{\pm} / 2, 2 a_{\pm}]$ , for example by $M_{\pm} = ∣ \log (γ / a_{\pm}) ∣ + \log 2$ . The mean value inequality and step 1.1 give $∣ f (k^{\pm} / \log n) - f (a_{\pm}) ∣ \log n \leq M_{\pm}$ .

3.1F1F2F4step 1.1step 2.1algebra

By the logarithm laws and the root equations, $f (a_{\pm}) = 1 - γ h (c^{\pm} \pm ε) = - ε$ , where the upper sign is used with $c^{+}$ and the lower sign with $c^{-}$ . Apply [F2] at $k = k^{\pm}$ and use step 2.1 to obtain $E X_{k^{\pm}} \leq \exp (- ε \log n + M_{\pm} + 2 p k^{\pm})$ .

4.1F4step 3.1algebra∎

The constants $M_{\pm}$ are independent of $n$ . By monotonicity and unboundedness of the logarithm, $\log \log n$ tends to infinity, so eventually both $M_{\pm} \leq 4 \log \log n$ . The increasing exponential now gives the two stated bounds.

Source notes

The cited article attributes the rounding allowance to a change bounded by $\log γ + \log \log n + \log (k + 1) + 2 p$ and writes $∣ L_{k} - L_{k + η} ∣ \leq ∣ η ∣ \log \log n + \log (k + 1)$ , with $L_{k} = (\log n)^{k} / k!$ and $∣ η ∣ \leq 1$ . The local proof instead bounds the smooth exponent at the rounded integer; it does not require a factorial at a noninteger or use that displayed comparison.

Depends on

Used by · 1

Valid restricted spectral tails and a counterexample to the shifted degree-failure conclusion

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, rounded thresholds