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.

Independent degrees into a fixed half of a random graph

Statement

Let $n$ be positive and even, $m = n / 2$ , and $G \sim G (n, p)$ for $0 < p < 1$ . Partition its vertices into sets $U, V$ of size $m$ , and let $D_{u}$ be the number of neighbors of $u \in U$ in $V$ . Then $(D_{u})_{u \in U}$ are independent, and for integers $0 \leq k \leq m$ , $P (D_{u} = k) = (\binom{m}{k}) p^{k} (1 - p)^{m - k} .$ Here $k! = 1 \cdot 2 \dots k$ with $0! = 1$ .

Facts & Assumptions

[F1]

The graph has mutually independent Bernoulli $(p)$ edge indicators indexed by unordered pairs of distinct vertices. Each indicator has value 1 with probability $p$ and value 0 with probability $1 - p$ (The Erdős-Rényi finite random graph G(n,p), Bernoulli random variables and binomial random variables as sums of independent Bernoulli trials, Pairwise and mutual independence of finite-valued random variables).

[F2]

The weight of a coordinate assignment in a finite product is the product of its coordinate weights (The finite product of finite probability spaces).

[F3]

The number $(\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]ᵏ|).

[F4]

The factorial $k!$ is the product of the integers from 1 to $k$ (The factorial n! and the falling factorial n^k̲, defined by recursion in ℕ).

[F5]

Distinct vertices $u, v$ are neighbors exactly when ${u, v}$ is an edge; hence counting neighbors in $V$ counts the corresponding incident edges (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, and its distribution at a value is the probability of the corresponding fibre (Real random variables on finite probability spaces and their finite distributions).

[F7]

A finite family of finite-valued random variables is mutually independent when, for every nonempty subfamily and selection of values in their ranges, the joint probability is the product of the individual probabilities (Pairwise and mutual independence of finite-valued random variables).

[F8]

An event in a finite probability space is a subset of the outcome set, and its probability is the sum of its outcome weights; the sum over the whole outcome set is one (Finite probability spaces, outcome weights, events, and event probabilities).

Proof

Given: The hypotheses and objects in the Statement.

Goal: Establish the asserted conclusions.

1.1F1F2F5F6F7F8given

For $u \in U$ , $D_{u}$ depends on the $m$ edges ${u, v}$ with $v \in V$ . The coordinate sets for distinct $u$ are disjoint: equality of two such unordered edges forces equality of their endpoint in $U$ . To compute joint degree probabilities, sum the product weights over each prescribed block of coordinates. The sums factor over the disjoint blocks, while unused coordinates have total weight one. Thus the joint degree probabilities factor, establishing independence.

2.1F1F2F3F4F6F8step 1.1∎

Exactly $k$ of these $m$ coordinates equal one precisely when their set of one-coordinates is one of the $(\binom{m}{k})$ possible subsets. Each such assignment has weight $p^{k} (1 - p)^{m - k}$ . Sum their weights to obtain the displayed probability. The factorial notation is [F4].

Depends on

Used by · 4

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.