LemmaStatement: AI-adaptedProof: 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.

Symmetrization and moments of the adjacency difference

PDF p. 33: Proof of Proposition 6.3, first paragraphs

Statement

Let $n \geq 1$ and $p \in [0, 1]$ . Let $A$ be the adjacency matrix of the loop-free Erdős–Rényi graph $G (n, p)$ , and let $A^{'}$ be an independent copy. Thus the entries indexed by distinct unordered pairs of distinct vertices are independent Bernoulli $(p)$ variables, $A$ is symmetric, and its diagonal is zero. Let $I$ be the identity matrix, $J$ the all-ones matrix, $Δ_{A} = A - p J$ , and $W = A - A^{'}$ . The norm $∥ \cdot ∥$ is the operator norm induced by the Euclidean norm; $Tr$ denotes the sum of diagonal entries.

Then $E A = p (J - I)$ and $E ∥ Δ_{A} ∥ \leq E ∥ W ∥ + p$ . For each $x \neq y$ and each positive integer $k$ , $E W_{x, y}^{k} = 0$ when $k$ is odd and $E W_{x, y}^{k} = 2 p (1 - p)$ when $k$ is even. With the zeroth power interpreted as the constant one, $E W_{x, y}^{0} = 1$ . The diagonal entries of $W$ are zero. For every integer $ℓ \geq 1$ , $E ∥ W ∥ \leq (E Tr W^{2 ℓ})^{1 / (2 ℓ)}$ .

The stronger inequality $E ∥ Δ_{A} ∥ \leq E ∥ W ∥$ can fail even when $n \geq 2$ and $0 < p < 1$ . For instance it fails at $p = 1 - [4 n (n - 1)]^{- 1}$ .

Facts & Assumptions

[F1]

The centered-matrix and operator-norm conventions give $Δ_{A} = A - p J$ for reference degree $p n$ and define the induced operator norm (Centered graph matrices and reference degree, Loewner order, Hermitian inner product, and operator norm).

[F2]

The independent-copy construction gives a symmetric zero-diagonal $W$ whose off-diagonal entries are differences of independent Bernoulli $(p)$ variables (Independent-copy symmetrization matrix).

[F3]

Independent-copy norm symmetrization gives $E ∥ A - E A ∥ \leq E ∥ A - A^{'} ∥$ and, for this graph, $E A = p (J - I)$ (Norm symmetrization at the actual matrix mean).

[F4]

A difference of two independent Bernoulli $(p)$ variables has odd positive moments zero, positive even moments $2 p (1 - p)$ , and zeroth moment one (Finite Bernoulli difference laws and parity of moments).

[F5]

For a real symmetric matrix and $ℓ \geq 1$ , $∥ W ∥^{2 ℓ} \leq Tr W^{2 ℓ}$ pointwise (Trace powers, closed walks and independent edge moments).

[F6]

Finite Jensen gives $f (\sum_{i} q_{i} x_{i}) \leq \sum_{i} q_{i} f (x_{i})$ for a convex real function and nonnegative weights $q_{i}$ summing to one (Finite Jensen inequality for a convex function and nonnegative weights summing to one).

Proof

Given: The graph, independent copy, and integers in the statement.

Goal: Prove the corrected symmetrization and moment assertions, the trace bound, and the stated counterexample to the stronger inequality.

1.1F1F3givenalgebra

By [F3], $Δ_{A} = (A - E A) - p I$ . The operator norm of $I$ is one, since $n \geq 1$ and $I f = f$ for every vector. The triangle inequality, followed by [F3], yields $E ∥ Δ_{A} ∥ \leq E ∥ A - E A ∥ + p \leq E ∥ W ∥ + p$ .

1.2F2F4given

The off-diagonal description in [F2] permits direct application of [F4] to every $x \neq y$ . It gives the positive odd and even moments and the separately stated zeroth moment. The diagonal assertion follows from [F2].

1.3F5F6givenalgebra

The finite graph sample space makes $X = ∥ W ∥$ a nonnegative finite-valued random variable. Put $m = 2 ℓ \geq 2$ . For $s, t \geq 0$ , direct polynomial multiplication gives $t^{m} - s^{m} - m s^{m - 1} (t - s) = (t - s)^{2} \sum_{j = 0}^{m - 2} (j + 1) t^{m - 2 - j} s^{j} \geq 0$ , where zeroth powers are constant one. Given $x, y \geq 0$ and $q \in [0, 1]$ , apply this inequality at $s = q x + (1 - q) y$ with $t = x$ and $t = y$ , and multiply the two inequalities by $q$ and $1 - q$ . The linear terms cancel, yielding $s^{m} \leq q x^{m} + (1 - q) y^{m}$ . Thus $f (t) = t^{2 ℓ}$ is convex on $[0, \infty)$ . Apply [F6] to this function with weights equal to the outcome probabilities. Thus $(E X)^{2 ℓ} \leq E X^{2 ℓ} \leq E Tr W^{2 ℓ}$ by [F5]. Taking the nonnegative $2 ℓ$ -th root proves the trace bound.

2.1F1F2F4givenalgebra∎

For $n \geq 2$ , each diagonal entry of $Δ_{A}$ is $- p$ , so applying $Δ_{A}$ to a standard unit vector shows $∥ Δ_{A} ∥ \geq p$ . On the other hand, the operator norm is at most the sum of the absolute values of all matrix entries: each matrix unit has norm one, and the triangle inequality applies. By [F2] and [F4], $E ∣ W_{x y} ∣ = 2 p (1 - p)$ for $x \neq y$ and the diagonal is zero. Hence $E ∥ W ∥ \leq 2 n (n - 1) p (1 - p)$ . At $p = 1 - [4 n (n - 1)]^{- 1}$ this upper bound is $p / 2 < p \leq E ∥ Δ_{A} ∥$ . These steps establish all assertions.

Source notes

The article's proof of Proposition 6.3 displays the stronger symmetrization inequality and states the even-moment formula for all $ℓ \geq 0$ . The corrected bounds above retain the positive-moment and trace claims while accounting for the nonzero mean $E Δ_{A} = - p I$ and the zeroth moment. The article is cited for attribution, not as a proof of this lemma.

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.

Sources

Expander graphs are globally synchronizing · PDF p. 33, proof of Proposition 6.3, first paragraphs