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

The fixed-degree Alon–Boppana lower bound

Statement

For each fixed integer $d \geq 3$ , a sequence of finite $d$ -regular graphs with orders tending to infinity has largest absolute nonconstant adjacency eigenvalue at least $2 \sqrt{d - 1} - o (1)$ . The error is in the growing-order limit at fixed degree. This lower bound concerns achievable expansion and does not establish any synchronization threshold.

More precisely, graphs may be arbitrary symmetric nonnegative integer adjacency-slot matrices $A_{n}$ with every row sum $d$ , including loops and repeated edges. The quantity meant is $Λ_{n} = ∥ A_{n} - (d / n) J ∥_{o p}$ , where $J$ is the all-ones matrix and the norm is Euclidean. For $n \geq 2$ , this equals $\max_{2 \leq i \leq n} ∣ λ_{i} (A_{n}) ∣$ , retaining every eigenvalue except one constant-vector eigenvalue $d$ . For $n = 1$ , $Λ_{1} = 0$ and no maximum over nonconstant eigenvalues is used. For every $ε > 0$ , eventually $Λ_{n} \geq 2 \sqrt{d - 1} - ε$ . No connectedness or nonbipartiteness is assumed.

Statement references

Regular adjacency spectra and normalized expansion

Asymptotic quantifiers and uniform parameter ranges

Facts & Assumptions

Given: The objects and hypotheses in the statement.

Goal: Establish every assertion in the statement.

[F1]

For $n \geq 2$ , the centered norm is the largest absolute nonconstant eigenvalue, with multiplicities retained; for $n = 1$ , the centered norm is zero (Regular adjacency spectra and normalized expansion).

[F2]

For fixed $d, k$ and every $η > 0$ , eventually $Λ_{n} \geq C_{k}^{1 / (2 k)} \sqrt{d - 1} - η$ , for the full adjacency-slot convention (Extracting a nonconstant eigenvalue from closed-walk moments).

[F3]

The Dyck-word numbers satisfy $C_{k}^{1 / (2 k)} \to 2$ (Dyck words and elementary Catalan growth).

[F4]

The asymptotic error is at fixed degree and along increasing graph order (Asymptotic quantifiers and uniform parameter ranges).

Proof

1.1F2F3F4choosealgebra

Fix $d \geq 3$ and $ε > 0$ . By [F3], choose an integer $k \geq 1$ such that $C_{k}^{1 / (2 k)} \sqrt{d - 1} \geq 2 \sqrt{d - 1} - ε / 2$ . Keep this $k$ fixed when letting the order grow. Apply [F2] with $η = ε / 2$ . Beyond its order cutoff, $Λ_{n} \geq 2 \sqrt{d - 1} - ε$ .

2.1F1F4step 1.1algebra∎

Since $n \to \infty$ , eventually $n \geq 2$ , so [F1] identifies this with the claimed absolute nonconstant adjacency bound. If an order-one term occurs, its matrix is $[d]$ and its centered matrix is $[d] - d [1] = [0]$ , giving $Λ_{1} = 0$ as stated. This initial term has no effect on an eventual assertion. Equivalently put $r_{n} = \max {0, 2 \sqrt{d - 1} - Λ_{n}}$ . Step 1.1 says $r_{n} \to 0$ , and $Λ_{n} \geq 2 \sqrt{d - 1} - r_{n}$ , which is exactly the stated one-sided $o (1)$ formulation. Since every helper counted actual slot labels, the conclusion includes diagonal entries counted once and parallel slots without a convention transfer. No synchronization or construction assertion was used or proved.

Source notes

The independent source is Hoory–Linial–Wigderson, Expander Graphs and Their Applications, May 2006 draft: §2.1, p. 19 allows self-loops and multiple edges; §2.4, p. 21 defines the absolute nonconstant parameter; §2.5, Theorem 2.7, p. 22 states the fixed-degree bound; §5.2.1–5.2.2, pp. 49–50 supplies the closed-walk/Catalan method and explicitly distinguishes it from the stronger second-eigenvalue bound. Those passages were read in the retained PDF. This proof uses the same moment method, but replaces the source's distant-vertices Rayleigh quotient with a trace argument and proves the Dyck-word count and slot-label injection explicitly. The fixed-loop reversal construction addresses the library's allowance of arbitrary diagonal slot counts; it does not infer that an ordinary two-incidence loop is identical to a single diagonal slot. The source is independent background and method attribution, not an outstanding imported logical premise. No complete reading of Chapter 5 or reconstruction of its stronger diameter estimate, explicit Ramanujan constructions, or other cited literature is claimed.

Depends on

Used by · 1

Asymptotic optimality and existence background for Ramanujan graphs

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

Hoory, Linial and Wigderson, Expander Graphs and Their Applications, May 2006 draft · §2.1 p. 19; §2.4 p. 21; §2.5 Theorem 2.7 p. 22; §5.2.1–5.2.2 pp. 49–50 (method attribution only)