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

Connectivity and the lower Laplacian parameter

PDF p. 19: Prose after Proposition 3.2; PDF p. 20: Remark 3.5

Statement

Let $G$ be an $(n, d^{*}, α, c^{-}, c^{+})$ -expander with $n \geq 2$ and $d^{*} > 0$ . Its adjacency matrix is $A$ , its degree matrix is $D$ , its Laplacian is $L = D - A$ , and $Δ_{L} = L - d^{*} I + (d^{*} / n) J$ , where $J$ is the all-ones matrix. Write $λ_{2} (L)$ for the second-smallest eigenvalue of $L$ , counting multiplicity. Then $λ_{2} (L) \geq (1 + c^{-}) d^{*}$ . In particular, $c^{-} > - 1$ implies that $G$ is connected.

Conversely, connectivity guarantees that some admissible lower parameter exceeds $- 1$ , with the other parameters chosen appropriately. It does not force an arbitrarily prescribed admissible $c^{-}$ to exceed $- 1$ .

Statement references

Two-sided spectral expander — Definition 1.9

Centered graph matrices and reference degree

Adjacency, degrees, graph Laplacian, and spectral notation

Loewner order, Hermitian inner product, and operator norm

Facts & Assumptions

[F1]

The expander definition includes $c^{-} d^{*} I ⪯ Δ_{L} ⪯ c^{+} d^{*} I$ , and the Loewner order means nonnegativity of the corresponding quadratic forms. Two-sided spectral expander — Definition 1.9 Loewner order, Hermitian inner product, and operator norm

[F2]

For nonempty $V$ , $P = J / n$ is the orthogonal projection onto the constant vectors, and $Q = I - P$ projects onto $1^{⊥} = {f : \sum_{x} f (x) = 0}$ . The constant projection and centering decomposition

[F3]

The Laplacian is positive semidefinite, its kernel consists of functions constant on each connected component, and for $n \geq 2$ zero is a simple Laplacian eigenvalue exactly when the graph is connected. Support connectivity and the unnormalized Laplacian kernel

[F4]

A normal endomorphism of a finite-dimensional complex inner-product space has an orthonormal eigenbasis. Complex spectral theorem: a normal endomorphism of a finite-dimensional complex inner product space has an orthonormal eigenbasis, and conversely

Proof

Given: The expander and parameter hypotheses in the statement.

Goal: Prove the spectral lower bound, its connectivity consequence, and the qualified converse.

1.1givenF1F2F3F4algebra

By the centered-matrix identity, $L = Δ_{L} + d^{*} (I - P)$ . For $f \in 1^{⊥}$ , [F1] and [F2] therefore give $f^{*} L f \geq (1 + c^{-}) d^{*} ∥ f ∥^{2}$ . Also $L 1 = 0$ by the degree definition, and $L$ is real symmetric. Thus [F4] gives an orthonormal eigenbasis including $1 / \sqrt{n}$ ; by [F3] all its eigenvalues are nonnegative. Each other basis vector lies in $1^{⊥}$ , so its eigenvalue is at least $(1 + c^{-}) d^{*}$ . Consequently $λ_{2} (L) \geq (1 + c^{-}) d^{*}$ .

2.1F1F2F3F4step 1.1choosealgebra

If $c^{-} > - 1$ , the lower bound in step 1.1 is positive because $d^{*} > 0$ . Hence zero is simple, and [F3] gives connectivity. Conversely, suppose $G$ is connected. By [F3] and [F4], its smallest eigenvalue is zero and $λ_{2} (L) > 0$ . For any chosen $d^{*} > 0$ , put $c^{-} = \min {0, λ_{2} (L) / d^{*} - 1}$ . On $1^{⊥}$ , the eigenbasis gives $Δ_{L} = L - d^{*} I ⪰ c^{-} d^{*} I$ ; on the constant subspace both sides have quadratic values $0$ and $c^{-} d^{*} ∥ f ∥^{2}$ , respectively. Thus the lower inequality holds and $c^{-} > - 1$ . Since the matrices are finite-dimensional and self-adjoint, choose $c^{+}$ large enough for the upper inequality and $α$ large enough for $∥ Δ_{A} ∥ \leq α d^{*}$ . These choices make the connected graph an expander with a lower parameter exceeding $- 1$ .

3.1F1F2F4algebra∎

The choice of lower parameter need not be optimal. For the connected graph $K_{2}$ with $d^{*} = 1$ , $A = (\begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array})$ and $L = (\begin{array}{cc} 1 & - 1 \\ - 1 & 1 \end{array})$ . On the constant and zero-sum vectors, respectively, $Δ_{A} = A - J / 2$ has eigenvalues $0, - 1$ , while $Δ_{L} = L - I + J / 2$ has eigenvalues $0, 1$ . Hence $K_{2}$ is a $(2, 1, 1, - 1, 1)$ -expander, although its prescribed $c^{-} = - 1$ . This proves the stated limitation.

Source notes

The article states the unqualified equivalence between $c^{-} > - 1$ and connectivity and gives the displayed lower-bound argument. The counterexample above shows why the converse requires the existential qualification. This paragraph attributes the claim to Expander graphs are globally synchronizing, PDF pp. 19–20; the proof uses the mathematical suppliers listed above.

Depends on

Used by · 1

Cheeger lower bound — Remark 3.5

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 p. 19, prose after Proposition 3.2; p. 20, Remark 3.5