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.

Upper degree-tail count estimate — Lemma 6.8

PDF p. 36: Lemma 6.8 and proof

Statement

Let $n \geq 1$ be an integer and $p \in [0, 1]$ . In the random simple graph $G (n, p)$ on $n$ vertices, each possible edge occurs independently with probability $p$ . Let $X_{k}$ and $X_{\geq k}$ count the vertices of degree exactly $k$ and at least $k$ , respectively. For every $c > 0$ and integer $k \geq (1 + c) p n$ ,

$E X_{\geq k} \leq (1 + c^{- 1}) E X_{k} .$

Writing $f_{i} = P (Bin (n - 1, p) = i)$ , the interior calculation used in the proof is $f_{i} / f_{i - 1} = (n - i) p / (i (1 - p)) \leq 1 / (1 + c)$ whenever $0 < p < 1$ and $1 \leq i \leq n - 1$ with $i \geq (1 + c) p n$ .

Statement references

Counts of vertices of each degree

Facts & Assumptions

Given: The graph, $n$ , $p$ , $c$ and $k$ in the Statement.

Goal: Establish the displayed ratio in its stated range and the expected-count inequality.

[F1]

Each vertex degree is the number of incident edges and has the $Bin (n - 1, p)$ law; degrees are identically distributed. The counts $X_{k}$ and $X_{\geq k}$ are sums of the corresponding degree-event indicators. (Single-vertex degree laws and the shared-edge dependence, Counts of vertices of each degree)

[F2]

For $0 < p < 1$ , the binomial masses satisfy $f_{i} / f_{i - 1} = (n - i) p / (i (1 - p))$ for $1 \leq i \leq n - 1$ . If consecutive upper-tail masses from $k$ onward are bounded by a fixed ratio $q \in [0, 1)$ and $0 \leq k \leq n - 1$ , then $P (Bin (n - 1, p) \geq k) \leq f_{k} / (1 - q)$ . (prop-expander-prereq-binomial-tail-ratio-tool)

[F3]

For identically distributed integer-valued vertex degrees, $E X_{k} = n P (d (1) = k)$ . (Indicator expectations and exceptional-vertex probabilities)

[F4]

The expectation of an event indicator is its probability, and expectation is linear over finite sums. (Indicators turn event probabilities, intersections, and finite counts into expectations and products, Expectation is linear for every finite family of random variables, without any independence hypothesis)

Proof

technique · direct

1.1givenF2algebra

Suppose $0 < p < 1$ and $1 \leq i \leq n - 1$ with $i \geq (1 + c) p n$ . By [F2], the ratio is $(n - i) p / (i (1 - p))$ . Since $i \geq (1 + c) p n > 0$ , we have $n p / i \leq 1 / (1 + c)$ , and therefore $(n - i) p / (i (1 - p)) = (n p / i - p) / (1 - p) \leq (1 / (1 + c) - p) / (1 - p) \leq 1 / (1 + c)$ . This proves the stated ratio bound.

2.1givenF1F2F3F4step 1.1algebra

Put $q = 1 / (1 + c)$ , so $0 < q < 1$ . If $0 < p < 1$ and $k \leq n - 1$ , then $k \geq (1 + c) p n > 0$ , and step 1.1 applies to every consecutive mass ratio from $f_{k}$ upward. The upper-tail bound in [F2] gives $P (d (1) \geq k) \leq f_{k} / (1 - q) = (1 + c^{- 1}) f_{k}$ . By [F1] and [F4], $E X_{\geq k} = n P (d (1) \geq k)$ ; by [F3], $E X_{k} = n f_{k}$ . The desired inequality follows.

3.1givenF1step 2.1algebra∎

If $k > n - 1$ , every vertex degree is at most $n - 1$ , so both counts vanish. It remains to consider $p = 0$ with $k \leq n - 1$ : then the graph has no edges almost surely and $k \geq 0$ . If $k = 0$ , both counts equal $n$ almost surely; if $k > 0$ , both vanish. For $p = 1$ , the threshold gives $k \geq (1 + c) n > n - 1$ , already covered. These cases together with step 2.1 establish the inequality for all stated parameters.

Source notes

Lemma 6.8 of the cited article supplies the attribution for the degree-tail estimate. The argument above uses the stated mathematical suppliers.

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. 36, Lemma 6.8 and proof