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.

A second-moment bound for the absence of low-degree vertices

Statement

In $G (n, p)$ with $n \geq 2$ and $0 < p < 1$ , let $k$ be an integer, let $X$ count vertices of degree at most $k$ , and set $a = P (Bin (n - 2, p) \leq k)$ and $r = P (d (u) \leq k)$ . If $a > 0$ , then $r \geq (1 - p) a > 0$ and $P (X = 0) \leq \frac{1}{n r} + \frac{2 p}{(1 - p)^{2}} .$ This does not assume that the full vertex degrees are independent.

Facts & Assumptions

[F1]

Distinct unordered edge indicators are independent (The Erdős-Rényi finite random graph G(n,p)).

[F2]

Joint probabilities factor over disjoint coordinate blocks in a finite product (The finite product of finite probability spaces).

[F3]

Event probabilities are finite sums of outcome weights (Finite probability spaces, outcome weights, events, and event probabilities), and expectations are finite weighted sums (Expectation of a real random variable on a finite probability space).

[F4]

Vertex degree is the number of incident edges (Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree).

[F5]

A binomial variable is a sum of independent Bernoulli trials; for zero trials it is the constant zero variable (Bernoulli random variables and binomial random variables as sums of independent Bernoulli trials).

[F6]

Variance is $Var X = E [(X - E X)^{2}]$ (Variance, standard deviation, and covariance on a finite probability space).

[F7]

For an event $A$ , its indicator $1_{A}$ is $1$ on $A$ and $0$ outside $A$ (The indicator random variable of an event).

Proof

Given: The objects and hypotheses in the Statement.

Goal: Prove its conclusions.

1.1F1F2F3F4F5givenalgebra

For two distinct vertices $u, v$ , condition on their shared edge. All their other incident edge-coordinate blocks are disjoint. Put $b = P (Bin (n - 2, p) \leq k - 1)$ , so $0 \leq b \leq a$ . Factoring and summing the two shared-edge outcomes gives $r = (1 - p) a + p b$ and $P (d (u) \leq k, d (v) \leq k) = (1 - p) a^{2} + p b^{2} \leq a^{2}$ . In particular $r \geq (1 - p) a$ .

2.1F3F4F6F7step 1.1algebra∎

Let $I_{u}$ be the indicator of degree at most $k$ , so $X = \sum_{u} I_{u}$ . Expand the finite sums for $E X$ and $E X^{2}$ to obtain $E X = n r$ and $Var X \leq n r + n (n - 1) (a^{2} - r^{2}) \leq n r + 2 p n^{2} a^{2}$ , since $a^{2} - r^{2} \leq [1 - (1 - p)^{2}] a^{2} \leq 2 p a^{2}$ . On $X = 0$ , $(X - E X)^{2} = (n r)^{2}$ , so the nonnegative expectation sum gives $P (X = 0) \leq Var X / (n r)^{2}$ . Insert the variance estimate and $r \geq (1 - p) a$ to get the displayed bound.

Depends on

Used by · 1

The gamma-two graph has a vertex of degree at most log n with high probability

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.