   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
DOI: https://doi.org/10.1090/S0002-9939-2010-10543-9
Published electronically: June 22, 2010
MathSciNet review: 2679612
Full-text PDF Free Access

Abstract: The Alon-Boppana theorem confirms that for every $\varepsilon >0$ and every integer $d\ge 3$, 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.

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

References

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

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

Bojan Mohar
Affiliation: Department of Mathematics, Simon Fraser University, Burnaby, British Columbia, V5A 1S6, Canada
MR Author ID: 126065
ORCID: 0000-0002-7408-6148
Email: mohar@sfu.ca

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