Mathematics – Combinatorics
Scientific paper
2010-02-04
Proc. Amer. Math. Soc. 138 (2010) 3899-3909
Mathematics
Combinatorics
Revised version; to appear in Proc. AMS
Scientific paper
10.1090/S0002-9939-2010-10543-9
The Alon-Boppana theorem confirms that for every $\epsilon>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}-\epsilon$. Serre gave a strengthening showing that a positive proportion of eigenvalues of any $d$-regular graph must be bigger than $2\sqrt{d-1}-\epsilon$. We provide a multipartite version of this result. Our proofs are elementary and work also 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 $\epsilon>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_\epsilon(n)$ eigenvalues that are larger than $\sqrt{d_1-1}+\sqrt{d_2-1}-\epsilon$. Finally, we strengthen the Alon-Boppana-Serre theorem by showing that the lower bound $2\sqrt{d-1}-\epsilon$ 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.
No associations
LandOfFree
A strengthening and a multipartite generalization of the Alon-Boppana-Serre Theorem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A strengthening and a multipartite generalization of the Alon-Boppana-Serre Theorem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A strengthening and a multipartite generalization of the Alon-Boppana-Serre Theorem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-534231