  We prove the following Alon-Boppana type theorem for general (not necessarily
regular) weighted graphs: if $G$ is an $n$-node weighted undirected graph of
average combinatorial degree $d$ (that is, $G$ has $dn/2$ edges) and girth $g>
2d^{1/8}+1$, and if $\lambda_1 \leq \lambda_2 \leq \cdots \lambda_n$ are the
eigenvalues of the (non-normalized) Laplacian of $G$, then \[ \frac
{\lambda_n}{\lambda_2} \geq 1 + \frac 4{\sqrt d} - O \left( \frac 1{d^{\frac
58} }\right) \] (The Alon-Boppana theorem implies that if $G$ is unweighted and
$d$-regular, then $\frac {\lambda_n}{\lambda_2} \geq 1 + \frac 4{\sqrt d} -
O\left( \frac 1 d \right)$ if the diameter is at least $d^{1.5}$.)
  Our result implies a lower bound for spectral sparsifiers. A graph $H$ is a
spectral $\epsilon$-sparsifier of a graph $G$ if \[ L(G) \preceq L(H) \preceq
(1+\epsilon) L(G) \] where $L(G)$ is the Laplacian matrix of $G$ and $L(H)$ is
the Laplacian matrix of $H$. Batson, Spielman and Srivastava proved that for
every $G$ there is an $\epsilon$-sparsifier $H$ of average degree $d$ where
$\epsilon \approx \frac {4\sqrt 2}{\sqrt d}$ and the edges of $H$ are a
(weighted) subset of the edges of $G$. Batson, Spielman and Srivastava also
show that the bound on $\epsilon$ cannot be reduced below $\approx \frac
2{\sqrt d}$ when $G$ is a clique; our Alon-Boppana-type result implies that
$\epsilon$ cannot be reduced below $\approx \frac 4{\sqrt d}$ when $G$ comes
from a family of expanders of super-constant degree and super-constant girth.
  The method of Batson, Spielman and Srivastava proves a more general result,
about sparsifying sums of rank-one matrices, and their method applies to an
"online" setting. We show that for the online matrix setting the $4\sqrt 2 /
\sqrt d$ bound is tight, up to lower order terms.
