Ramanujan graphs (Lubotzky-Phillips-Sarnak 1988, Margulis 1988): d-regular graphs where every non-trivial eigenvalue satisfies |λ| ≤ 2√(d-1). This is the Alon-Boppana lower bound — Ramanujan graphs achieve the optimal possible spectral gap λ₁-λ₂ = d - 2√(d-1).
Large spectral gap ↔ good expander ↔ fast random walk mixing ↔ good error-correcting codes.
The Petersen graph (10 vertices, 3-regular) is a Ramanujan graph with λ₂ = √5 = 2√(3-1).