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 centered adjacency column retains a high-degree lower bound

Statement

For a simple undirected graph without self-loops on $n \geq 1$ vertices with adjacency matrix $A$ , a vertex $u$ of degree $D$ , and $0 \leq p \leq 1$ , let $J$ be the all-ones matrix and $Δ = A - p J$ . With Euclidean operator norms, $∥ Δ ∥ \geq (1 - p) \sqrt{D} .$ Unlike a bound obtained by subtracting $∥ p J ∥$ , this lower bound remains useful when $n p$ grows.

Facts & Assumptions

[F1]

The operator norm satisfies $∥ B ∥ \geq ∥ B e_{u} ∥_{2}$ for a coordinate unit vector $e_{u}$ (The operator norm is zero on the zero domain and otherwise is max_‖ v‖=1‖ Tv‖).

[F2]

For the undirected loop-free simple graph, adjacency entries are symmetric edge indicators and the degree of $u$ is $D = \sum_{x} A_{u x} = \sum_{x} A_{x u}$ (Adjacency, degrees, graph Laplacian, and spectral notation). The centered adjacency matrix with reference parameter $d^{*} = p n$ is $A - (d^{*} / n) J = A - p J$ (Centered graph matrices and reference degree).

Proof

Given: The objects and hypotheses in the Statement.

Goal: Prove the asserted conclusions.

1.1F2givenalgebra

The column $A e_{u}$ has exactly $D$ entries equal to one; the other $n - D$ entries equal zero. The corresponding entries of $Δ e_{u}$ are $1 - p$ and $- p$ . Therefore $∥ Δ e_{u} ∥_{2}^{2} = D (1 - p)^{2} + (n - D) p^{2} \geq D (1 - p)^{2}$ .

2.1F1step 1.1algebra∎

Apply [F1] and take nonnegative square roots in step 1.1. Since $1 - p \geq 0$ , this gives precisely the claimed inequality.

Depends on

Used by · 1

The proposed small-gamma centered-adjacency tail has the opposite limit

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.