The positive discrepancy of a graph G of edge density (Formula presented.) is defined as (Formula presented.). In 1993, Alon proved (using the equivalent terminology of minimum bisections) that if G is d-regular on n vertices, and d = O(n1/9), then disc+(G) = Ω(d1/2n). We greatly extend this by showing that if G has average degree d, then (Formula presented.). These bounds are best possible if d << n3/4, and the complete bipartite graph shows that disc+(G) = Ω(n) cannot be improved if d ≈ 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 (Formula presented.) has a cut of size (Formula presented.). 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 λ2, as (Formula presented.). As a byproduct of our arguments, we present lower bounds on λ2 for regular graphs, extending the celebrated Alon-Boppana theorem in the dense regime.