Thumbnail Image
Non-discoverable
Item

Explicit Bounds from the Alon–Boppana Theorem

Richey, J
; 
Shutty, N
; 
Stover, M
Citations
Altmetric:
Genre
Pre-print
Date
2018-10-02
Advisor
Committee member
Group
Department
Subject
Graph spectrum
 graph Laplacian
 Alon-Boppana theorem
 spectra of regular graphs
Permanent link to this record
http://hdl.handle.net/20.500.12613/4908
Collections
Faculty/Researcher Works
Show all metadata
Files
Thumbnail Image
1306.6548v2.pdf
Adobe PDF, 593 KB
Research Projects
Organizational Units
Journal Issue
DOI
10.1080/10586458.2017.1311813
Abstract
© 2018, © 2018 Taylor & Francis. 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).
Description
Citation
Citation to related work
Informa UK Limited
Has part
Experimental Mathematics
ADA compliance
For Americans with Disabilities Act (ADA) accommodation, including help with reading this content, please contact scholarshare@temple.edu
Embedded videos