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.

Degree control implies two-sided expansion — Proposition 3.2

PDF p. 18: Proposition 3.2; PDF p. 19: Proposition 3.2 and proof

Statement

Let $G = (V, E)$ be a finite undirected graph with $n = ∣ V ∣ > 0$ , allowing self-loops and counting a loop once in the degree. Let $A$ be its adjacency matrix, $D$ its diagonal degree matrix, $L = D - A$ , $I$ the identity, and $J$ the all-ones matrix. For real parameters $d^{*}, α, c^{-}, c^{+}$ put $Δ_{A} = A - (d^{*} / n) J$ and $Δ_{L} = L - d^{*} I + (d^{*} / n) J$ . Write $d_{\min} (G)$ and $d_{\max} (G)$ for the minimum and maximum vertex degrees, and use the induced operator norm and Loewner order on the complex vertex space.

If $∥ Δ_{A} ∥ \leq α d^{*}$ and $(1 + c^{-} + α) d^{*} \leq d_{\min} (G) \leq d_{\max} (G) \leq (1 + c^{+} - α) d^{*}$ , then $G$ is an $(n, d^{*}, α, c^{-}, c^{+})$ -expander: it satisfies the stated norm bound and $c^{-} d^{*} I ⪯ Δ_{L} ⪯ c^{+} d^{*} I$ .

Statement references

Adjacency, degrees, graph Laplacian, and spectral notation

Centered graph matrices and reference degree

Loewner order, Hermitian inner product, and operator norm

Two-sided spectral expander — Definition 1.9

Facts & Assumptions

[F1]

The degree matrix is diagonal with entries $D_{x x} = d (x)$ , and $d_{\min} (G) \leq d (x) \leq d_{\max} (G)$ for every vertex. The adjacency matrix is real symmetric (Adjacency, degrees, graph Laplacian, and spectral notation).

[F2]

The centered matrices are real symmetric and obey $Δ_{L} = (D - d^{*} I) - Δ_{A}$ (Centered graph matrices and reference degree).

[F3]

For real symmetric $B$ and $b \geq 0$ , $∥ B ∥ \leq b$ implies $- b I ⪯ B ⪯ b I$ ; Loewner inequalities can be added (Self-adjoint order, norm bounds and diagonal tests). The order is defined by nonnegative quadratic forms (Loewner order, Hermitian inner product, and operator norm).

[F4]

A graph is an $(n, d^{*}, α, c^{-}, c^{+})$ -expander exactly when $∥ Δ_{A} ∥ \leq α d^{*}$ and $c^{-} d^{*} I ⪯ Δ_{L} ⪯ c^{+} d^{*} I$ (Two-sided spectral expander — Definition 1.9).

Proof

Given: The graph, real parameters, norm bound and degree bounds in the statement.

Goal: Establish both defining inequalities of the two-sided expander.

1.1givenF1F3algebra

Put $b = α d^{*}$ . The operator norm is nonnegative, so the given bound implies $b \geq 0$ . By [F1] and the given degree bounds, every diagonal entry of $D - ((1 + c^{-}) d^{*} + b) I$ and of $((1 + c^{+}) d^{*} - b) I - D$ is nonnegative. Their quadratic forms are sums of these entries times $∣ f (x) ∣^{2}$ , so the definition of order in [F3] gives $((1 + c^{-}) d^{*} + b) I ⪯ D ⪯ ((1 + c^{+}) d^{*} - b) I$ .

2.1givenF2F3F4step 1.1algebra∎

By [F2], $Δ_{A}$ is real symmetric. The norm bound and [F3] therefore give $- b I ⪯ Δ_{A} ⪯ b I$ . Adding these inequalities to the two bounds in step 1.1 yields $(1 + c^{-}) d^{*} I ⪯ D - d^{*} I - Δ_{A} + d^{*} I ⪯ (1 + c^{+}) d^{*} I$ . Subtracting $d^{*} I$ throughout and using [F2] gives $c^{-} d^{*} I ⪯ Δ_{L} ⪯ c^{+} d^{*} I$ . Together with the given norm bound, [F4] proves the asserted expander property.

Source notes

Proposition 3.2 and its degree-to-order argument are attributed to Expander graphs are globally synchronizing, PDF pp. 18–19. The proof above derives the claim from the stated suppliers.

Depends on

Used by · 3

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. 18–19, Proposition 3.2 and proof