A strengthening and a multipartite generalization of the Alon-Boppana-Serre theorem
- Autores: Bojan Mohar
- Localización: Proceedings of the American Mathematical Society, ISSN 0002-9939, Vol. 138, Nº 11, 2010, págs. 3899-3909
- Idioma: inglés
- DOI: 10.1090/s0002-9939-2010-10543-9
- Enlaces
-
Resumen
The Alon-Boppana theorem confirms that for every and every integer , there are only finitely many -regular graphs whose second largest eigenvalue is at most . Serre gave a strengthening showing that a positive proportion of eigenvalues of any -regular graph must be bigger than . 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 and bounded maximum degree. The two-partite result shows that for every and any positive integers , every -vertex graph of maximum degree at most , whose vertex set is the union of (not necessarily disjoint) subsets , such that every vertex in has at least neighbors in for , has eigenvalues that are larger than . Finally, we strengthen the Alon-Boppana-Serre theorem by showing that the lower bound can be replaced by for some 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.
