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 μ₁(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 ${\mu }_1\left(X\right)<(2-ϵ)\sqrt{k-1}$, 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 ${\mu }_1\left(X\right)<(2-ϵ)\sqrt{k-1}$.

Keywords:

• Graph spectrum
• graph Laplacian
• Alon–Boppana theorem
• spectra of regular graphs

2000 AMS SUBJECT CLASSIFICATION:

• 05C30
• 05C30
• 05C85

Acknowledgments

We thank Stephen Debacker for his help in getting this project going and Sebastian Cioabă for communication related to [Cioabă 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 $z/\sqrt{k-1}$ 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 [Cioabă et al. 16].

4 Since this article was completed, [Cioabă et al. 16] showed that in fact v(4, 2) = 35 and v(4, 3) = 728.