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.

The unnormalized Laplacian needs its own degree deviation

Statement

Use the matrices and graph law in the loop-coupling and degree-envelope lemmas. Define $X = W - p (J - I)$ and $Y = L (W) + p J - d I$ . If $∥ X ∥ \leq K \sqrt{d}$ and every degree has $∣ d_{i} - (n - 1) p ∣ \leq \sqrt{12 d \log n}$ , then $∥ Y ∥ \leq K \sqrt{d} + \sqrt{12 d \log n}$ . The same $Y$ is obtained after adding any loops.

Facts & Assumptions

Given: The data and hypotheses in the Statement.

Goal: Establish the conclusions in the Statement.

[F1]

The loop-coupling notation has $W$ real symmetric, $J = 11^{T}$ , $d = n p$ , $L (W) = diag (W 1) - W$ , and loop invariance $L (W + B) = L (W)$ for the added diagonal loops (Loop coupling preserves the dynamics and centered Laplacian). The simultaneous loop-free degree envelope is supplied by Simultaneous degree deviations on the squared logarithmic scale; the argument below is conditional on the stated degree and adjacency bounds.

[F2]

In the finite vertex space, $∥ f ∥_{2}^{2} = \sum_{i} ∣ f_{i} ∣^{2}$ and $⟨ f, T f ⟩ = f^{*} T f$ (Finite vertex Hilbert space in the article convention). For real symmetric $T$ and $a \geq 0$ , $∥ T ∥ \leq a$ is equivalent to $- a I ⪯ T ⪯ a I$ ; the order is defined by nonnegative quadratic forms, and order inequalities can be added (Self-adjoint order, norm bounds and diagonal tests).

Proof

1.1givenF1algebra

Put $h_{i} = d_{i} - (n - 1) p$ and $H = diag (h_{i})$ . Since $W 1 = (d_{i})_{i}$ and $d = n p$ , expansion gives $H - X = diag (d_{i}) - (n - 1) p I - W + p J - p I = L (W) + p J - d I = Y$ .

2.1givenF2step 1.1algebra

Put $m = \sqrt{12 d \log n}$ . The assumed degree bounds give $- m \leq h_{i} \leq m$ . Hence for every $f \in C^{n}$ , $⟨ f, (m I \pm H) f ⟩ = \sum_{i} (m \pm h_{i}) ∣ f_{i} ∣^{2} \geq 0$ . By the definition of the order, $- m I ⪯ H ⪯ m I$ .

3.1givenF1F2step 1.1step 2.1algebra

Put $b = K \sqrt{d}$ . The assumed bound $∥ X ∥ \leq b$ implies $b \geq 0$ . The matrix $X = W - p (J - I)$ is real symmetric, so the norm-order equivalence yields $- b I ⪯ X ⪯ b I$ . The same two inequalities give $- b I ⪯ - X ⪯ b I$ , because $b I - X$ and $b I + X$ are positive semidefinite. Adding these bounds to those for $H$ gives $- (m + b) I ⪯ H - X ⪯ (m + b) I$ . The matrix $H - X = Y$ is real symmetric and $m + b \geq 0$ , so the reverse norm-order implication gives $∥ Y ∥ \leq m + b = K \sqrt{d} + \sqrt{12 d \log n}$ .

4.1F1step 3.1∎

Adding diagonal loops leaves $L (W)$ unchanged by [F1], while $p$ , $J$ and $d$ remain fixed. Thus it leaves $Y = L (W) + p J - d I$ unchanged. The bound in step 3.1 retains the separate degree-deviation term; no $O (\sqrt{d})$ bound for the unnormalized centered Laplacian is inferred from an adjacency bound alone.

Depends on

Used by · 1

Earlier thresholds with explicit source quantifiers and a fixed-scale deduction

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.