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

Research paper by **Bojan Mohar**

Indexed on: **17 Apr '10**Published on: **17 Apr '10**Published in: **Mathematics - Combinatorics**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### Abstract

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.