Ramanujan graph

A Ramanujan graph is a regular graph whose spectral gap achieves the theoretical optimum predicted by the Alon-Boppana bound. Named after the Indian mathematician Srinivasa Ramanujan, these graphs are the best possible expanders: no family of d-regular graphs can have a smaller second eigenvalue in the limit of large size. Their construction, first achieved by Lubotzky–Phillips–Sarnak and Margulis independently, required deep results from number theory and the proof of the Ramanujan conjecture. Ramanujan graphs demonstrate that the boundary between combinatorics and number theory is where optimal network structure lives.

Ramanujan graphs are not merely optimal expanders. They are a refutation of the intuition that optimal structures must be random. The explicit, deterministic constructions of Ramanujan graphs outperform random graphs in their spectral properties, proving that algebraic structure can beat entropy at its own game.