PropositionStatement: 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.

Expected centered-adjacency norm — Proposition 6.3

PDF p. 33: Proposition 6.3 and proof; PDF p. 34: Proposition 6.3 and proof

Statement

Assume the Axiom of Choice. Let $n \geq 1$ and $ℓ \geq 1$ be integers and $p \in [0, 1]$ . Let $A$ be the adjacency matrix of the loop-free random graph $G (n, p)$ , in which distinct unordered edges occur independently with probability $p$ . Put $Δ_{A} = A - p J$ , where $J$ is the all-ones matrix, and let $∥ \cdot ∥$ be the Euclidean operator norm. With $q = 2 p (1 - p)$ ,

$E ∥ Δ_{A} ∥ \leq p + q^{1 / (2 ℓ)} (2 \sqrt{n} + 2 \sqrt{2 ℓ}) e^{\log n / (2 ℓ)} .$

Proposition 6.3 of the article asserts that for every $C > 2 \sqrt{2}$ there is $n_{0} (C)$ such that, for all $n \geq n_{0} (C)$ and every $p \in (0, 1)$ , $E ∥ Δ_{A} ∥ \leq C \sqrt{n p (1 - p)}$ . This uniform assertion is false. It fails both for parameters approaching $p = 1$ and along an explicit sequence with $p = 1 / n$ .

Statement references

Adjacency, degrees, graph Laplacian, and spectral notation

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

Centered graph matrices and reference degree

Loewner order, Hermitian inner product, and operator norm

The Axiom of Choice

Real random variables on finite probability spaces and their finite distributions

Expectation of a real random variable on a finite probability space

Facts & Assumptions

[F1]

Under the stated hypotheses, the corrected moment estimate gives the displayed upper bound (Expected-norm estimate from the corrected moment comparison, The Axiom of Choice).

[F2]

The adjacency entry $A_{x y}$ is the indicator of ${x, y} \in E$ . The graph has zero diagonal, $Δ_{A} = A - p J$ , and the operator norm is the supremum of $∥ Δ_{A} v ∥_{2}$ over Euclidean unit vectors $v$ (Adjacency, degrees, graph Laplacian, and spectral notation, Erdős–Rényi random graph and high probability, Centered graph matrices and reference degree, Loewner order, Hermitian inner product, and operator norm).

[F3]

Independent edge indicators have product probabilities. The number of $k$ -element subsets of an $m$ -element set is $(\binom{m}{k})$ , and $k! = 1 \dots k$ counts their orders (The finite product of finite probability spaces, The set [A]ᵏ of k-element subsets and the binomial coefficient C(n, k) := | [n]ᵏ|, The factorial n! and the falling factorial n^k̲, defined by recursion in ℕ).

[F4]

The Euclidean norm satisfies the triangle and Cauchy–Schwarz inequalities (Cauchy-Schwarz |⟨ x,y⟩| ≤ ‖ x‖₂‖ y‖₂ with its equality case, the triangle inequality for ‖·‖₂, the parallelogram law and polarisation).

[F5]

A real random variable on a finite probability space $(Ω, w)$ is a function $X : Ω \to R$ . Its expectation is $E [X] = \sum_{ω \in Ω} X (ω) w (ω)$ , where the outcome weights are nonnegative and sum to one (Real random variables on finite probability spaces and their finite distributions, Expectation of a real random variable on a finite probability space, The finite product of finite probability spaces).

Proof

Given: The graph, parameters and Choice assumption in the Statement.

Goal: Establish the corrected estimate and refute the article's uniform assertion in both stated regimes.

1.1givenF1F2F3F4F5

Take $Ω$ to be the finite set of assignments of zero or one to the $(\binom{n}{2})$ unordered edge coordinates, with the Bernoulli product weights $w$ from [F3]. By [F2] and [F4], the function $X (ω) = ∥ A (ω) - p J ∥$ is nonnegative and real valued, hence is a finite real random variable by [F5]; its expectation is the finite weighted sum there. The graph law, centering and norm are those in [F1]. Applying that estimate proves the displayed inequality.

1.2givenF2F3algebrainduction

For a second counterexample fix an integer $k \geq 1$ , put $n = 4^{k + 2} k!$ and $p = 1 / n$ , and partition the vertices into sets $U, V$ each of size $m = n / 2$ . For $u \in U$ , let $D_{u}$ count its neighbors in $V$ . The sets of edge indicators defining distinct $D_{u}$ are disjoint. By [F3], the $D_{u}$ are independent and $P (D_{u} = k) = (\binom{m}{k}) n^{- k} (1 - 1 / n)^{m - k}$ . Since $n \geq 4 k$ , each factor of $m (m - 1) \dots (m - k + 1)$ is at least $n / 4$ . Counting ordered selections gives $(\binom{m}{k}) k! = m (m - 1) \dots (m - k + 1)$ . Also $(1 - 1 / n)^{m - k} \geq 1 - (m - k) / n \geq 1 / 2$ , by induction. Therefore $P (D_{u} = k) \geq q_{0} : = 1 / (2 4^{k} k!)$ .

2.1givenF2F5step 1.1algebra

Fix $C > 2 \sqrt{2}$ and any integer $n \geq 2$ , and choose $p = 1 - 1 / (16 C^{2} n)$ . Then $0 < p < 1$ and $p > 1 / 2$ . By [F2], every diagonal entry of $Δ_{A}$ equals $- p$ ; applying it to a coordinate unit vector gives $∥ Δ_{A} ∥ \geq p$ for every graph outcome. By [F5], $E ∥ Δ_{A} ∥ = \sum_{ω \in Ω} X (ω) w (ω) \geq p \sum_{ω \in Ω} w (ω) = p > 1 / 2$ , whereas $C \sqrt{n p (1 - p)} = \sqrt{p} / 4 < 1 / 4$ . This contradicts the asserted bound for arbitrarily large $n$ .

2.2F3step 1.2algebrainduction

By independence, the probability that no $u \in U$ has $D_{u} = k$ is at most $(1 - q_{0})^{m}$ . Here $m q_{0} = 4$ . For $0 \leq q < 1$ , $(1 - q)^{- 1} \geq 1 + q$ , and induction gives $(1 + q)^{m} \geq 1 + m q$ ; hence $(1 - q_{0})^{m} \leq 1 / (1 + m q_{0}) = 1 / 5$ . Thus, with probability at least $4 / 5$ , the graph has a vertex of total degree at least $k$ .

3.1F2F4F5step 1.1step 2.2algebra∎

If a vertex has degree $D$ , its adjacency column has Euclidean norm $\sqrt{D}$ , so [F2] gives $∥ A ∥ \geq \sqrt{D}$ . By Cauchy–Schwarz, $∥ J / n ∥ \leq 1$ ; the constant unit vector gives equality. The triangle inequality then gives $∥ A - J / n ∥ \geq ∥ A ∥ - 1$ . Let $H \subseteq Ω$ be the event that some vertex has degree at least $k$ . On $H$ we have $X \geq \sqrt{k} - 1 \geq 0$ , and outside $H$ we have $X \geq 0$ . Thus [F5] and step 2.2 give $E ∥ Δ_{A} ∥ \geq \sum_{ω \in H} X (ω) w (ω) \geq (\sqrt{k} - 1) \sum_{ω \in H} w (ω) = (\sqrt{k} - 1) P (H) \geq (4 / 5) (\sqrt{k} - 1)$ . On the other hand $C \sqrt{n p (1 - p)} = C \sqrt{1 - 1 / n} < C$ . Choose integers $k > (1 + 5 C / 4)^{2}$ , arbitrarily large. The resulting even integers $n = 4^{k + 2} k!$ are arbitrarily large, $p = 1 / n$ lies in $(0, 1)$ , and the lower bound exceeds $C$ . This contradicts the asserted bound for every proposed threshold $n_{0} (C)$ .

Source notes

The article citation attributes Proposition 6.3; it does not supply a premise for the corrected estimate or either counterexample. The sparse construction counts independent cross-degrees directly.

Depends on

Used by · 1

Numerical coefficients and thresholds — Remark 6.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.

Sources

Expander graphs are globally synchronizing · PDF pp. 33–34, Proposition 6.3 and its proof; PDF p. 6 for centering