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.

Loop-free Bernoulli adjacency and its two centerings

Statement

Let $A$ be the adjacency matrix of the simple graph $G (n, p)$ , with $n \geq 1$ and $0 \leq p \leq 1$ . Matrix expectation is taken entrywise: $(E A)_{i j} = E [A_{i j}]$ . Write $J$ for the all-ones matrix, $I$ for the identity, $X = A - E A$ , and $Δ = A - p J$ , the reference-degree centering at $d^{*} = n p$ . Then $E A = p (J - I)$ , $X_{i i} = 0$ , $Δ_{i i} = - p$ , and $Δ = X - p I$ . For $p > 0$ , the diagonal entries of $Δ$ are not centered Bernoulli variables, since their mean is $- p \neq 0$ . For $p = 0$ , they are the zero centered Bernoulli( $0$ ) variables. Here a centered Bernoulli( $p$ ) variable means $B - p$ for a Bernoulli( $p$ ) variable $B$ .

Statement references

Erdős–Rényi random graph and high probability

Centered graph matrices and reference degree

Adjacency, degrees, graph Laplacian, and spectral notation

Expectation of a real random variable on a finite probability space

Bernoulli random variables and binomial random variables as sums of independent Bernoulli trials

Facts & Assumptions

[F1]

The adjacency entry $A_{i j}$ is the indicator of the edge ${i, j}$ . The simple graph has zero diagonal and mutually independent Bernoulli( $p$ ) entries above the diagonal. Adjacency, degrees, graph Laplacian, and spectral notation Erdős–Rényi random graph and high probability Bernoulli random variables and binomial random variables as sums of independent Bernoulli trials

[F2]

The reference-degree centered adjacency matrix is $A - (d^{*} / n) J$ . Centered graph matrices and reference degree

[F3]

For a real random variable $Y$ on a finite probability space $(Ω, w)$ , $E [Y] = \sum_{ω \in Ω} Y (ω) w (ω)$ ; a real constant also denotes the corresponding constant random variable. Expectation of a real random variable on a finite probability space

[F4]

For $p \in [0, 1]$ , a Bernoulli( $p$ ) variable $B$ takes the value $1$ with probability $p$ and $0$ with probability $1 - p$ . Bernoulli random variables and binomial random variables as sums of independent Bernoulli trials

Proof

Given: The data and hypotheses in the Statement.

Goal: Establish the stated conclusions, including the case $p = 0$ .

1.1givenF1F3algebra

Work on the finite probability space of simple graphs on $[n]$ with the law in [F1]. For $i \neq j$ , [F1] and [F3] give $E [A_{i j}] = \sum_{ω : A_{i j} (ω) = 1} w (ω) = p$ , since that sum is the probability that the edge is present. For $i = j$ , $A_{i i} = 0$ gives $E [A_{i i}] = 0$ . Taking matrix expectation entrywise therefore gives $E A = p (J - I)$ and $X_{i i} = 0$ .

2.1givenF1F2step 1.1algebra

Substitute $d^{*} = n p$ in [F2]. Then $Δ = A - p J = A - p (J - I) - p I = X - p I$ . Since $A_{i i} = 0$ and $J_{i i} = 1$ , this also gives $Δ_{i i} = - p$ .

3.1givenF1F3F4step 2.1algebra∎

By [F3], the deterministic variable $Δ_{i i} = - p$ has mean $- p \sum_{ω \in Ω} w (ω) = - p$ . By [F4], for a Bernoulli( $p$ ) variable $B$ , the centered variable $B - p$ has mean $p (1 - p) + (1 - p) (- p) = 0$ by the same weighted-sum definition. Thus for $p > 0$ the diagonal entries cannot be centered Bernoulli variables. At $p = 0$ , $B = 0$ almost surely and both $B - p$ and $Δ_{i i}$ are zero. This proves the distinction with its degenerate exception throughout the stated parameter range.

Depends on

Used by · 1

A near-threshold counterexample to the reported constant-two spectral bound

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.