2013/06/30 by Joseph Richey, Noah Shutty, Matthew Stover
Mathematics · #Adjacency list #Adjacency matrix #Bounding overwatch #Eigenvalues and eigenvectors #Finite Group Theory Research #Graph #Graph theory and applications #Limits and Structures in Graph Theory #Upper and lower bounds #math.CO #math.GT #math.SP
paper · pdf · doi:10.1080/10586458.2017.1311813
To appear in Exp. Math
openalex publication_date 2017/04/17 · openalex created_date 2017/04/28 · arxiv created 2017/09/15 · arxiv updated 2018/10/23 · openalex updated_date 2026/08/05
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 μ1(X)<(2-ϵ)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 μ1(X)<(2-ϵ)k-1.