Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826(online) ISSN 0002-9939(print)

 

A strengthening and a multipartite generalization of the Alon-Boppana-Serre theorem


Author: Bojan Mohar
Journal: Proc. Amer. Math. Soc. 138 (2010), 3899-3909
MSC (2010): Primary 05C50
Published electronically: June 22, 2010
MathSciNet review: 2679612
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The Alon-Boppana theorem confirms that for every $ \varepsilon>0$ and every integer $ d\ge3$, there are only finitely many $ d$-regular graphs whose second largest eigenvalue is at most $ 2\sqrt{d-1}-\varepsilon$. Serre gave a strengthening showing that a positive proportion of eigenvalues of any $ d$-regular graph must be bigger than $ 2\sqrt{d-1}-\varepsilon$. We provide a multipartite version of this result. Our proofs are elementary and also work in the case when graphs are not regular. In the simplest, monopartite case, our result extends the Alon-Boppana-Serre result to non-regular graphs of minimum degree $ d$ and bounded maximum degree. The two-partite result shows that for every $ \varepsilon>0$ and any positive integers $ d_1,d_2,d$, every $ n$-vertex graph of maximum degree at most $ d$, whose vertex set is the union of (not necessarily disjoint) subsets $ V_1,V_2$, such that every vertex in $ V_i$ has at least $ d_i$ neighbors in $ V_{3-i}$ for $ i=1,2$, has $ \Omega_\varepsilon(n)$ eigenvalues that are larger than $ \sqrt{d_1-1}+\sqrt{d_2-1}-\varepsilon$. Finally, we strengthen the Alon-Boppana-Serre theorem by showing that the lower bound $ 2\sqrt{d-1}-\varepsilon$ can be replaced by $ 2\sqrt{d-1} + \delta$ for some $ \delta>0$ if graphs have bounded ``global girth''. On the other side of the spectrum, if the odd girth is large, then we get an Alon-Boppana-Serre type theorem for the negative eigenvalues as well.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 05C50

Retrieve articles in all journals with MSC (2010): 05C50


Additional Information

Bojan Mohar
Affiliation: Department of Mathematics, Simon Fraser University, Burnaby, British Columbia, V5A 1S6, Canada
Email: mohar@sfu.ca

DOI: http://dx.doi.org/10.1090/S0002-9939-2010-10543-9
PII: S 0002-9939(2010)10543-9
Keywords: Spectral radius, eigenvalue, Ramanujan graph, universal cover.
Received by editor(s): February 4, 2010
Published electronically: June 22, 2010
Additional Notes: The author was supported in part by the Research Grant P1–0297 of ARRS (Slovenia), by an NSERC Discovery Grant (Canada) and by the Canada Research Chair program.
The author is on leave from IMFM & FMF, Department of Mathematics, University of Ljubljana, Ljubljana, Slovenia.
Communicated by: Jim Haglund
Article copyright: © Copyright 2010 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.