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.

Typical regular graphs are almost Ramanujan

PDF p. 7: Section 1.3, paragraph citing Friedman [20]

Statement

Fix an integer $d \geq 3$ and $ε > 0$ . A uniformly chosen labelled simple $d$ -regular graph on $n$ vertices is, with high probability, an $(n, d, α)$ -expander with $α = (2 \sqrt{d - 1} + ε) / d$ . The limit is as $n \to \infty$ through orders for which such graphs exist, with $d$ and $ε$ fixed.

Here simple means without loops or repeated edges, and $d$ -regular means that every vertex has $d$ neighbors. Uniformly chosen means that every such graph on ${1, \dots, n}$ has equal probability; with high probability means that the probability tends to one. For adjacency matrix $A$ and all-ones matrix $J$ , the expander condition is $∥ A - (d / n) J ∥_{o p} \leq α d$ , where the operator norm is induced by the Euclidean norm. This is the almost-Ramanujan assertion attributed to Friedman in the article.

Statement references

Adjacency spectral expander — Definition 1.3

Adjacency, degrees, graph Laplacian, and spectral notation

Uniform random regular graph convention

Asymptotic quantifiers and uniform parameter ranges

Facts & Assumptions

[F1]

For fixed integer $d \geq 3$ and fixed $ε > 0$ , in the uniform labelled simple $d$ -regular model, the probability that $\max {λ_{2} (A), ∣ λ_{n} (A) ∣} \geq 2 \sqrt{d - 1} + ε$ tends to zero along feasible orders. The real adjacency eigenvalues are ordered with multiplicity as $d = λ_{1} \geq \dots \geq λ_{n}$ (Friedman spectral expansion in the uniform simple model).

[F2]

For a labelled simple $d$ -regular graph with $d > 0$ and $n \geq 2$ , $∥ A - (d / n) J ∥_{o p} = \max {λ_{2} (A), ∣ λ_{n} (A) ∣}$ (Ordered eigenvalues and the centered regular norm).

[F3]

In the stated model the expander event is the centered norm inequality above, and high probability is convergence of its probability to one along feasible orders (Adjacency spectral expander — Definition 1.3, Adjacency, degrees, graph Laplacian, and spectral notation, Uniform random regular graph convention, Asymptotic quantifiers and uniform parameter ranges).

Proof

Given: Fixed integer $d \geq 3$ and fixed $ε > 0$ , with the uniform simple regular graph law at each feasible order.

Goal: Show that the $(n, d, α)$ -expander event has probability tending to one for $α = (2 \sqrt{d - 1} + ε) / d$ .

1.1givenF1

By [F1], the event that $\max {λ_{2} (A), ∣ λ_{n} (A) ∣} < 2 \sqrt{d - 1} + ε$ has probability tending to one. The graph law and feasible-order limit here are exactly those in the statement.

2.1F2F3step 1.1algebra∎

By [F2], on this event $∥ A - (d / n) J ∥_{o p} < 2 \sqrt{d - 1} + ε = α d$ . It therefore satisfies the non-strict expander inequality in [F3]. Its probability is at least that of the event in step 1.1 and at most one, so it tends to one.

Depends on

Used by · 1

Ramanujan and typical regular graphs synchronize for degree at least 600

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, paragraph citing Friedman [20]