Explicit Bounds from the Alon Boppana Theorem
ABSTRACT The purpose of this article is to give explicit methods for bounding the number of vertices of finite k regular graphs with given second eigenvalue. Let X be a finite k regular graph and m1(X) the second largest eigenvalue of its adjacency matrix. It follows from the well known Alon Boppana theorem that for any e 0 there are only finitely many such X with and we effectively implement Serre's quantitative version of this result. For any k and e, this gives an explicit upper bound on the number of vertices in a k regular graph with
Exp. Math.