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 large degree with explicitly bounded probability at fixed sparse density

Statement

For every integer $k \geq 1$ , put $n_{k} = 4^{k + 2} k!$ and $p_{k} = 1 / n_{k}$ . In $G (n_{k}, p_{k})$ , with probability at least $4 / 5$ , some vertex has at least $k$ neighbors. In fact some vertex in the first half has exactly $k$ neighbors in the second half with probability at least $4 / 5$ .

Facts & Assumptions

[F1]

The degrees from distinct vertices in one half into the other half are independent (Independent degrees into a fixed half of a random graph).

[F2]

For even $n \geq 4 k$ each such degree equals $k$ with probability at least $q_{0} = 1 / (2 4^{k} k!)$ (An explicit lower bound on a sparse binomial atom).

[F3]

The model $G (n, p)$ is a finite simple graph on the labelled vertices $[n]$ with mutually independent Bernoulli $(p)$ edge indicators (The Erdős-Rényi finite random graph G(n,p)). For even $n$ , the first half is ${1, \dots, n / 2}$ and the second half is ${n / 2 + 1, \dots, n}$ .

[F4]

Distinct vertices are neighbors precisely when their unordered pair is an edge, and a vertex's total degree is the number of all its neighbors (Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree).

[F5]

Mathematical induction holds for properties of nonnegative integers: a property true at $0$ and preserved from $r$ to $r + 1$ holds for every $r \geq 0$ (The principle of mathematical induction).

Proof

Given: The hypotheses and objects in the Statement.

Goal: Establish the asserted conclusions.

1.1F1F2F3givenalgebra

The integer $n = n_{k}$ is even and satisfies $n \geq 4 k$ (since $k! \geq k$ and $4^{k + 2} \geq 4$ ). Let $m = n / 2$ and let $q$ be the common probability of degree $k$ into the second half. By [F1] the probability none of the $m$ first-half vertices has this degree is $(1 - q)^{m}$ . By [F2], $m q \geq m q_{0} = 4$ .

2.1F4F5step 1.1algebra∎

Fix $0 \leq q < 1$ . Since $(1 - q) (1 + q) = 1 - q^{2} \leq 1$ and $1 - q > 0$ , we have $(1 - q)^{- 1} \geq 1 + q$ . For a nonnegative integer $r$ , the inequality $(1 + q)^{r} \geq 1 + r q$ holds at $r = 0$ . If it holds at $r$ , multiplication by $1 + q > 0$ gives $(1 + q)^{r + 1} \geq (1 + r q) (1 + q) = 1 + (r + 1) q + r q^{2} \geq 1 + (r + 1) q$ . Thus [F5] proves it for every nonnegative integer $r$ , in particular $r = m$ . Taking positive reciprocals gives $(1 - q)^{m} \leq (1 + q)^{- m} \leq 1 / (1 + m q) \leq 1 / 5$ . If $q = 1$ the probability of no such vertex is zero. The complementary event therefore has probability at least $4 / 5$ . A vertex's total degree is no smaller than its degree into the second half, proving both assertions.

Depends on

Used by · 2

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.