# Proceedings of the American Mathematical Society

Published by the American Mathematical Society, the Proceedings of the American Mathematical Society (PROC) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6826 (online) ISSN 0002-9939 (print)

The 2020 MCQ for Proceedings of the American Mathematical Society is 0.85.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

## A strengthening and a multipartite generalization of the Alon-Boppana-Serre theoremHTML articles powered by AMS MathViewer

by Bojan Mohar
Proc. Amer. Math. Soc. 138 (2010), 3899-3909 Request permission

## 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.
Similar Articles
• 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
• 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