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.

Regular adjacency expansion supplies two-sided expansion

PDF p. 8: Paragraph following Definition 1.9

Statement

An $(n, d^{*}, α)$ -expander need not be regular. If an $(n, d^{*}, α)$ -expander is $d^{*}$ -regular, then $Δ_{L} = - Δ_{A}$ and it is an $(n, d^{*}, α, - α, α)$ -expander.

Here $G = (V, E)$ is a finite undirected graph with $n = ∣ V ∣ > 0$ , binary symmetric adjacency matrix $A$ , degree matrix $D$ formed from row sums, and Laplacian $L = D - A$ ; a loop contributes once to its vertex's degree. Regularity means $D = d^{*} I$ . With $J$ the all-ones matrix, $Δ_{A} = A - (d^{*} / n) J$ and $Δ_{L} = L - d^{*} I + (d^{*} / n) J$ . An $(n, d^{*}, α)$ -expander satisfies $∥ Δ_{A} ∥ \leq α d^{*}$ in the induced Euclidean operator norm. An $(n, d^{*}, α, c^{-}, c^{+})$ -expander additionally satisfies $c^{-} d^{*} I ⪯ Δ_{L} ⪯ c^{+} d^{*} I$ , where $B ⪯ C$ means $f^{*} (C - B) f \geq 0$ for every $f \in C^{V}$ .

Statement references

Adjacency, degrees, graph Laplacian, and spectral notation

Centered graph matrices and reference degree

Adjacency spectral expander — Definition 1.3

Two-sided spectral expander — Definition 1.9

Loewner order, Hermitian inner product, and operator norm

Facts & Assumptions

[F1]

The graph conventions give $L = D - A$ and identify regularity with constant degree row sums (Adjacency, degrees, graph Laplacian, and spectral notation). The centered matrices satisfy $Δ_{L} = (D - d^{*} I) - Δ_{A}$ (Centered graph matrices and reference degree).

[F2]

The adjacency-expander predicate is $∥ Δ_{A} ∥ \leq α d^{*}$ (Adjacency spectral expander — Definition 1.3). The two-sided predicate is this same condition together with $c^{-} d^{*} I ⪯ Δ_{L} ⪯ c^{+} d^{*} I$ (Two-sided spectral expander — Definition 1.9); the order and norm are those stated above (Loewner order, Hermitian inner product, and operator norm).

[F3]

For a real symmetric matrix $B$ and real $b \geq 0$ , $∥ B ∥ \leq b$ if and only if $- b I ⪯ B ⪯ b I$ (Self-adjoint order, norm bounds and diagonal tests).

Proof

Given: The graph and parameters in the statement; for the conditional assertion assume also that the graph is $d^{*}$ -regular and is an $(n, d^{*}, α)$ -expander.

Goal: Exhibit an irregular adjacency expander and prove the centered identity and two-sided bound in the regular case.

1.1F1F2constructalgebra

For the irregular example, take two vertices, one loop at the first vertex, and no other edges. Then $A = (\begin{array}{cc} 1 & 0 \\ 0 & 0 \end{array})$ and the degrees are $1$ and $0$ . With $d^{*} = 1$ and $α = 1$ , the centered matrix is $B = A - J / 2 = \frac{1}{2} (\begin{array}{cc} 1 & - 1 \\ - 1 & - 1 \end{array})$ . Direct multiplication gives $B^{*} B = I / 2$ , so $∥ B f ∥_{2}^{2} = ∥ f ∥_{2}^{2} / 2$ for every $f$ and $∥ B ∥ = 1 / \sqrt{2} \leq 1 = α d^{*}$ . By [F2] this is an $(2, 1, 1)$ -expander, although its degrees differ.

2.1givenF1F2F3algebra∎

In the regular case, $D = d^{*} I$ by the degree definition. Therefore [F1] gives $Δ_{L} = - Δ_{A}$ . The matrix $Δ_{A}$ is real symmetric. Its norm is nonnegative, so the assumed bound $∥ Δ_{A} ∥ \leq α d^{*}$ implies $b = α d^{*} \geq 0$ . Applying [F3] gives $- b I ⪯ Δ_{A} ⪯ b I$ ; negating the inequalities and using the identity gives $- α d^{*} I ⪯ Δ_{L} ⪯ α d^{*} I$ . Together with the assumed adjacency-expander condition, [F2] identifies this as the $(n, d^{*}, α, - α, α)$ -expander condition.

Source notes

The claim is attributed to the paragraph following Definition 1.9 of Expander graphs are globally synchronizing. The example and proof above are local deductions from the stated suppliers.

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 page 8, paragraph following Definition 1.9