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

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.