Alon–Boppana bound

Summary

In spectral graph theory, the Alon–Boppana bound provides a lower bound on the second-largest eigenvalue of the adjacency matrix of a $d$-regular graph, meaning a graph in which every vertex has degree $d$. The reason for the interest in the second-largest eigenvalue is that the largest eigenvalue is guaranteed to be $d$ due to $d$-regularity, with the all-ones vector being the associated eigenvector. The graphs that come close to meeting this bound are Ramanujan graphs, which are examples of the best possible expander graphs.