Alon–Boppana bound

In spectral graph theory, the Alon–Boppana bound provides a lower bound on the second-largest eigenvalue of the adjacency matrix of a

-regularity, with the all-ones vector being the associated eigenvector.

Its discoverers are Noga Alon and Ravi Boppana.

Then The above statement is the original one proved by Noga Alon.

Some slightly weaker variants exist to improve the ease of proof or improve intuition.

More precisely, a Ramanujan graph is a

A theorem by Friedman[3] shows that, for every

-regular graph is typically "almost Ramanujan."

We will prove a slightly weaker statement, namely dropping the specificity on the second term and simply asserting

term refers to the asymptotic behavior as

Let the vertex set be

By the min-max theorem, it suffices to construct a nonzero vector

Each component will be indexed by a vertex

satisfies To prove this, let

denote the set of all vertices that have a distance of exactly

First, note that Second, note that where the last term on the right comes from a possible overcounting of terms in the initial expression.

The above then implies which, when combined with the fact that

yields The combination of the above results proves the desired inequality.

to be the set of vertices with a distance of at most

The number of vertices within distance

grow without bound while ensuring that

grow sublogarithmically as a function of

) makes the error term

This proof will demonstrate a slightly modified result, but it provides better intuition for the source of the number

Notice that the number of closed walks of length

is However, it is also true that the number of closed walks of length

starting at a fixed vertex

-regular graph is at least the number of such walks in an infinite

grow without bound and letting

grow without bound but sublogarithmically in