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 lower estimate for a binomial point probability

Statement

Let $M, k$ be integers with $1 \leq k \leq M$ , and let $0 < p \leq 1 / 2$ . Let $G \sim G (2 M, p)$ , fix a partition of its vertex set into sets $U, V$ of size $M$ , and fix $u \in U$ . Let $D$ be the number of neighbors of $u$ in $V$ . Then $P (D = k) \geq (M p / k)^{k} \exp (- 2 M p) .$

Facts & Assumptions

[F1]

For $G \sim G (2 M, p)$ , a fixed partition into equal parts of size $M$ , and a fixed vertex in one part, the cross-degree law is $P (D = k) = (\binom{M}{k}) p^{k} (1 - p)^{M - k}$ (Independent degrees into a fixed half of a random graph).

[F2]

The logarithm satisfies $\log x = \int_{1}^{x} d t / t$ (The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t).

[F3]

The natural logarithm is inverse to the exponential (The natural logarithm as the inverse of the exponential function).

[F4]

The exponential satisfies $\exp (a + b) = \exp (a) \exp (b)$ (The exponential addition formula exp(x+y)=exp(x)exp(y)).

[F5]

The real exponential is strictly increasing (The exponential function is strictly increasing).

[F6]

The model $G (2 M, p)$ is the simple graph on $2 M$ labelled vertices whose possible edges are present independently with probability $p$ (The Erdős-Rényi finite random graph G(n,p)).

[F7]

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

[F8]

Distinct vertices $u, v$ are neighbors exactly when ${u, v}$ is an edge; thus the number of neighbors of $u$ in $V$ counts the edges ${u, v}$ with $v \in V$ (Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree).

Proof

Given: The objects and hypotheses in the Statement.

Goal: Prove the asserted lower bound.

1.1F7givenalgebra

By [F7], $(\binom{M}{k})$ counts the $k$ -element subsets of $V$ . There are $\prod_{j = 0}^{k - 1} (M - j)$ ordered lists of $k$ distinct elements of $V$ , and each such subset has $\prod_{j = 0}^{k - 1} (k - j)$ orders. Dividing gives $(\binom{M}{k}) = \prod_{j = 0}^{k - 1} (M - j) / (k - j)$ . Each denominator is positive, and each factor is at least $M / k$ , since $k (M - j) \geq M (k - j)$ is equivalent to $(M - k) j \geq 0$ . Consequently $(\binom{M}{k}) p^{k} \geq (M p / k)^{k}$ .

2.1F1F2F3F4F5F6F8step 1.1algebra∎

By [F8], $D$ counts the edges from $u$ to $V$ . The model in [F6] and the fixed partition satisfy [F1] with $n = 2 M$ and $m = M$ ; in particular, $M \geq 1$ and $0 < p \leq 1 / 2 < 1$ . By [F2], $- \log (1 - p) = \int_{1 - p}^{1} d t / t \leq p / (1 - p) \leq 2 p$ . Apply [F3], [F4], and [F5] to obtain $(1 - p)^{M} = \exp (M \log (1 - p)) \geq \exp (- 2 M p)$ . Because $0 < 1 - p < 1$ , replacing $M$ by $M - k$ only increases this power. Multiply by step 1.1 and use the exact probability in [F1] to obtain the claimed lower bound.

Depends on

Used by · 1

Independent cross-degrees produce a large degree at logarithmic 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.