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.

An explicit lower bound on a sparse binomial atom

Statement

Let $k \geq 1$ be an integer and let $n \geq 4 k$ be even. Fix a partition $[n] = U ⊔ V$ into two sets of size $n / 2$ and a vertex $u \in U$ . For $G \sim G (n, 1 / n)$ , let $D$ have the law of $∣ N_{G} (u) \cap V ∣$ , the number of neighbors of $u$ in $V$ . Then $q : = P (D = k) \geq q_{0} : = \frac{1}{2 4^{k} k!} .$ The bound is uniform in all these $n$ , partitions and vertices.

Facts & Assumptions

[F1]

In the stated cross-degree setting, $0 < 1 / n < 1$ and $0 \leq k \leq n / 2$ , so the degree has probability $(\binom{n / 2}{k}) n^{- k} (1 - 1 / n)^{n / 2 - k}$ of equaling $k$ (Independent degrees into a fixed half of a random graph).

[F2]

The factorial $k!$ is the product $1 \cdot 2 \dots k$ , with $0! = 1$ (The factorial n! and the falling factorial n^k̲, defined by recursion in ℕ).

[F3]

The number $(\binom{m}{k})$ counts the $k$ -element subsets of any $m$ -element set (The set [A]ᵏ of k-element subsets and the binomial coefficient C(n, k) := | [n]ᵏ|).

[F4]

The model $G (n, p)$ is the finite simple graph on the labelled vertex set $[n]$ with mutually independent Bernoulli $(p)$ edge indicators (The Erdős-Rényi finite random graph G(n,p)).

[F5]

The open neighborhood is $N_{G} (u) = {v : {u, v} \in E (G)}$ , so $∣ N_{G} (u) \cap V ∣$ counts the neighbors of $u$ in $V$ (Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree).

[F6]

A real random variable on a finite probability space is a real-valued function on its outcome set. Its law assigns to each value the probability of the corresponding fibre, so variables with the same law have the same atom probabilities (Real random variables on finite probability spaces and their finite distributions).

Proof

Given: The hypotheses and objects in the Statement.

Goal: Establish the asserted conclusions.

1.1F2givenalgebra

Put $m = n / 2$ . For a set of $s$ elements, let $N_{j}$ count its ordered $j$ -tuples of distinct elements. There is one empty tuple, so $N_{0} = 1$ . For $0 \leq j < s$ , partition the ordered $(j + 1)$ -tuples by their first $j$ entries: each of the $N_{j}$ parts has exactly $s - j$ elements, one for each unused element. Therefore $N_{j + 1} = (s - j) N_{j}$ . Induction gives $N_{k} = s (s - 1) \dots (s - k + 1)$ for $k \leq s$ . Taking $s = k$ and using [F2] proves that each $k$ -element set has exactly $k!$ orderings.

2.1F3step 1.1givenalgebra

Forgetting the order partitions the ordered $k$ -tuples from an $m$ -element set into $(\binom{m}{k})$ classes by [F3], each of size $k!$ by step 1.1. Thus $(\binom{m}{k}) k! = m (m - 1) \dots (m - k + 1)$ . Since $n \geq 4 k$ , we have $k \leq m$ , and for $0 \leq j < k$ each factor $m - j$ is at least $n / 4$ . Dividing by the positive number $k! n^{k}$ gives $(\binom{m}{k}) n^{- k} \geq 1 / (4^{k} k!)$ .

3.1F1step 2.1algebra∎

For integers $r \geq 0$ and $0 \leq a \leq 1$ , induction gives $(1 - a)^{r} \geq 1 - r a$ : the inductive multiplication adds the nonnegative term $r a^{2}$ . Apply this with $r = m - k$ and $a = 1 / n$ . The resulting lower bound $1 - (m - k) / n$ is at least $1 / 2$ . Multiplying it by step 2.1 and using [F1] proves $q \geq q_{0}$ .

Depends on

Used by · 1

A large degree with explicitly bounded probability at fixed sparse density

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.