  The positive discrepancy of a graph $G$ of edge density
$p=e(G)/\binom{v(G)}{2}$ is defined as
  $$\mbox{disc}^{+}(G)=\max_{U\subset V(G)}e(G[U])-p\binom{|U|}{2}.$$
  In 1993, Alon proved (using the equivalent terminology of minimum bisections)
that if $G$ is $d$-regular on $n$ vertices, and $d=O(n^{1/9})$, then
$\mbox{disc}^{+}(G)=\Omega(d^{1/2}n)$. We greatly extend this by showing that
if $G$ has average degree $d$, then
$\mbox{disc}^{+}(G)=\Omega(d^{\frac{1}{2}}n)$ if $d\in [0,n^{\frac{2}{3}}]$,
$\Omega(n^2/d)$ if $d\in [n^{\frac{2}{3}},n^{\frac{4}{5}}]$, and
$\Omega(d^{\frac{1}{4}}n/\log n)$ if $d\in
\left[n^{\frac{4}{5}},(\frac{1}{2}-\varepsilon)n\right]$. These bounds are best
possible if $d\ll n^{3/4}$, and the complete bipartite graph shows that
$\mbox{disc}^{+}(G)=\Omega(n)$ cannot be improved if $d\approx n/2$. Our proofs
are based on semidefinite programming and linear algebraic techniques.
  An interesting corollary of our results is that every $d$-regular graph on
$n$ vertices with ${\frac{1}{2}+\varepsilon\leq \frac{d}{n}\leq 1-\varepsilon}$
has a cut of size $\frac{nd}{4}+\Omega(n^{5/4}/\log n)$. This is not
necessarily true without the assumption of regularity, or the bounds on $d$.
  The positive discrepancy of regular graphs is controlled by the second
eigenvalue $\lambda_2$, as $\mbox{disc}^{+}(G)\leq \frac{\lambda_2}{2} n+d$. As
a byproduct of our arguments, we present lower bounds on $\lambda_2$ for
regular graphs, extending the celebrated Alon-Boppana theorem in the dense
regime.
