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.

Asymptotic optimality and existence background for Ramanujan graphs

PDF p. 7: Section 1.3, Ramanujan background

Statement

Fix an integer $d \geq 3$ . Let $G_{n}$ be finite $d$ -regular graphs whose orders $n$ tend to infinity, in the graph convention of Ramanujan graph convention used in the article. Thus the adjacency matrix $A_{n}$ is symmetric, each row has sum $d$ , and a loop contributes one to its row sum. Write $J_{n}$ for the all-ones matrix and $α_{n} = ∥ A_{n} - (d / n) J_{n} ∥_{o p} / d$ , using the Euclidean operator norm. Then, for every $ε > 0$ , eventually $α_{n} \geq 2 \sqrt{d - 1} / d - ε$ . Hence the article's Ramanujan threshold $2 \sqrt{d - 1} / d$ is asymptotically optimal as a lower bound for this normalized parameter at fixed $d$ . Any sequence of graphs satisfying that threshold attains the bound asymptotically; this conditional assertion does not itself establish such a sequence.

The article reports explicit Ramanujan constructions and partial existence results, citing [34, 37] and [36], respectively. A separate existence theorem supplies, for every $d \geq 3$ , arbitrarily large $d$ -regular bipartite graphs whose eigenvalues other than the designated trivial values $d$ and $- d$ have absolute value at most $2 \sqrt{d - 1}$ . In that theorem's convention both $d$ and $- d$ are excluded. These graphs have centered norm at least $d$ , so this existence statement does not by itself give Ramanujan graphs in the article's centered-norm convention.

Facts & Assumptions

Given: A fixed integer $d \geq 3$ and a sequence of graphs as in the statement.

Goal: Establish the normalized asymptotic lower bound, its conditional attainment, and the stated distinction between existence conventions.

[F1]

The fixed-degree Alon–Boppana input gives, for every $η > 0$ , the eventual bound $∥ A_{n} - (d / n) J_{n} ∥_{o p} \geq 2 \sqrt{d - 1} - η$ for the stated graph convention (The fixed-degree Alon–Boppana lower bound).

[F2]

For a regular adjacency matrix the centered norm is the norm on the mean-zero subspace, retaining any $- d$ eigenvalue and every additional $d$ eigenvalue (Regular adjacency spectra and normalized expansion).

[F3]

The article's Ramanujan condition is $∥ A_{n} - (d / n) J_{n} ∥_{o p} \leq 2 \sqrt{d - 1}$ (Ramanujan graph convention used in the article).

[F4]

The bipartite existence input gives the sequence and spectral convention described in the statement, and establishes that its centered norm is at least $d > 2 \sqrt{d - 1}$ (Bipartite Ramanujan existence and the centered spectrum).

Proof

1.1F1algebra

Given $ε > 0$ , apply [F1] with $η = d ε$ and divide by the fixed positive number $d$ . This gives $α_{n} \geq 2 \sqrt{d - 1} / d - ε$ for all sufficiently large $n$ . Thus no sequence at this fixed degree can have its normalized centered norms eventually below the threshold by a fixed positive amount.

2.1F3step 1.1algebra

If every graph in the sequence satisfies the article's Ramanujan condition, [F3] gives $α_{n} \leq 2 \sqrt{d - 1} / d$ . Together with step 1.1 this proves convergence of $α_{n}$ to that value. This argument assumes the sequence exists.

3.1F2F4algebra∎

The sequence in [F4] exists under the stated bipartite convention, but [F4] also gives its centered norm at least $d > 2 \sqrt{d - 1}$ . The distinction is consistent with [F2]: removing only the constant-vector eigenvalue retains the eigenvalue $- d$ . Consequently that existence theorem alone does not establish the article's centered-norm condition.

Source notes

The original article attributes the fixed-degree asymptotic optimality to Alon and Boppana and reports explicit constructions and partial existence results, citing [34, 37] and [36]. This is attribution of its discussion, not a premise for the proof above. The independently supplied bipartite existence result has the narrower, explicitly stated convention in [F4]; it is not presented as a verification of the article's cited construction papers.

Depends on

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. 7, Section 1.3, paragraphs following Remark 1.5