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.

Elementary estimates used for degree expectations

PDF p. 37: Proof of Proposition 6.9, binomial and factorial estimates

Statement

For every real $x$ , $1 - x \leq e^{- x}$ . For integers $n \geq 0$ and $0 \leq k \leq n$ , $(\binom{n}{k}) \leq n^{k} / k!$ , with $n^{0} = 1$ even when $n = 0$ . For every positive integer $k$ , $k! \geq (k / e)^{k}$ .

Here $(\binom{n}{k})$ counts the $k$ -element subsets of an $n$ -element set, $k! = 1 \cdot 2 \dots k$ with $0! = 1$ , and $e = \exp (1)$ , where $e^{t} = \exp (t)$ .

Facts & Assumptions

[F1]

For every real $t$ , $1 + t \leq \exp (t)$ (1+x≤exp(x) for every real x, hence (1-p)ᵐ≤exp(-mp)).

[F2]

For integers $N \geq k \geq 1$ and any $0 < p < 1$ , the elementary binomial envelope includes $(\binom{N}{k}) \leq N^{k} / k!$ and $k! \geq (k / e)^{k}$ (Elementary binomial probability envelopes).

[F3]

The binomial coefficient counts subsets and $(\binom{n}{0}) = 1$ for every integer $n \geq 0$ (The set [A]ᵏ of k-element subsets and the binomial coefficient C(n, k) := | [n]ᵏ|). The factorial has $0! = 1$ and is the product of the positive integers through its index (The factorial n! and the falling factorial n^k̲, defined by recursion in ℕ). The real exponential notation and $e = \exp (1)$ are as in The real exponential function and the number e by a power series.

Proof

Given: A real $x$ , integers $n \geq 0$ and $0 \leq k \leq n$ , and a positive integer wherever the factorial lower bound is asserted.

Goal: Establish the three stated inequalities, including the case $k = 0$ in the binomial bound.

1.1F1F3algebra

Apply [F1] with $t = - x$ . This gives $1 - x \leq \exp (- x) = e^{- x}$ .

1.2F2F3algebra

If $k \geq 1$ , choose $p = 1 / 2$ and apply [F2] with $N = n$ to obtain $(\binom{n}{k}) \leq n^{k} / k!$ . If $k = 0$ , [F3] gives $(\binom{n}{0}) = 1$ and $0! = 1$ , while the stated zeroth-power convention gives $n^{0} = 1$ ; hence the same inequality is equality, including at $n = 0$ .

2.1F2step 1.1step 1.2∎

For any positive integer $k$ , apply [F2] with $N = k$ and $p = 1 / 2$ . Its factorial conclusion gives $k! \geq (k / e)^{k}$ . Together with steps 1.1 and 1.2 this proves all three estimates.

Source notes

The cited article uses these estimates in the proof of Proposition 6.9 to bound degree expectations; the argument above derives them from the stated mathematical suppliers. In that application the exponential inequality is used with the edge probability $p \in (0, 1)$ .

Depends on

Used by · 1

Expected degree-count bound and logarithmic factorial estimate

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 — Abdalla, Bandeira, Kassabov, Souza, Strogatz, Townsend (2026) · PDF p. 37, proof of Proposition 6.9, binomial and factorial estimates