Ramanujan Graphs

TL;DR

Ramanujan graphs are regular graphs whose nontrivial adjacency eigenvalues match the spectrum of the universal covering tree, making them spectrally optimal expanders. The paper explains their connection to Ramanujan’s conjecture on Hecke eigenvalues and describes arithmetic constructions of such graphs.

• Problem

  Constructing k-regular graphs with optimally bounded nontrivial eigenvalues is difficult: random regular graphs are known to be expanders, but it is not known whether they are Ramanujan.

• Method

  The constructions use quotients of Bruhat–Tits trees by arithmetic subgroups whose associated representation-theoretic temperedness conditions follow from the Ramanujan–Peterson conjecture and the Jacquet–Langlands correspondence.

• Results

  Ramanujan graphs have all nontrivial eigenvalues within the spectrum of the infinite k-regular tree and are therefore optimal expanders.

• Takeaways & Limitations

  Their eigenvalue bounds yield the fastest possible convergence of random walks to the uniform distribution and support applications in networks, algorithms, combinatorics, and pure mathematics.