Positive discrepancy, MaxCut, and eigenvalues of graphs

Abstract

The positive discrepancy of a graph $G$ of edge density $p=e(G)/\left(\genfrac{}{}{0ex}{}{v(G)}{2}\right)$ 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)=Ω(d^{1/2}n)$. We greatly extend this by showing that if $G$ has average degree $d$, then $\mbox{disc}^{+}(G)=Ω(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}-\epsilon )n\right]$. These bounds are best possible if $d\ll n^{3/4}$, and the complete bipartite graph shows that $\mbox{disc}^{+}(G)=Ω(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}+\epsilon \le \frac{d}{n}\le 1-\epsilon$ 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{λ_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.

29 pages