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 μ1(X) the second largest eigenvalue of its adjacency matrix. It follows from the well-known Alon–Boppana theorem that for any ε > 0 there are only finitely many such X with , and we effectively implement Serre's quantitative version of this result. For any k and ε, this gives an explicit upper bound on the number of vertices in a k-regular graph with
.
Acknowledgments
We thank Stephen Debacker for his help in getting this project going and Sebastian Cioabă for communication related to [CitationCioabă et al. 16].
Funding
This material is based upon work supported by the National Science Foundation under grant numbers DMS 1045119 and 1361000. Noah Shutty is partially supported by the University of Michigan Undergraduate Research Opportunities Program. The authors also acknowledge support from the National Science Foundation grants DMS 1107452, 1107263, 1107367 “RNMS: GEometric structures And Representation varieties” (the GEAR Network).
Notes
1 Actually, we take m to be one larger when the expression inside the ceiling function is an integer, so there is a genuine gap between and αm.
2 Python code allowing one to implement the computations in this article is available from the third author's website.
3 This conjecture is proved in [CitationCioabă et al. 16].
4 Since this article was completed, [CitationCioabă et al. 16] showed that in fact v(4, 2) = 35 and v(4, 3) = 728.