Positive discrepancy, MaxCut, and eigenvalues of graphs

Source abstract

The positive discrepancy of a graph G G of edge density p = e ( G ) / ( v ( G ) 2 ) p= e(G)/\binom {v(G)}{2} is defined as d i s c + ( G ) = max U ⊂ V ( G ) e ( G [ U ] ) − p ( | U | 2 ) . $$\begin{equation*} disc^{+}(G)=\max _{U\subset V(G)}e(G[U])-p\binom {|U|}{2}. \end{equation*}$$ In 1993, Alon proved (using the equivalent terminology of minimum bisections ) that if G G is d d -regular on n n vertices, and d = O ( n 1 / 9 ) d=O(n^{1/9}) , then d i s c + ( G ) = Ω ( d 1 / 2 n ) disc^{+}(G)=\Omega (d^{1/2}n) . We greatly extend this by showing that if G G has average degree d d , then d i s c + ( G ) = { Ω ( d 1 2 n ) a m p ; if d ∈ [ 0 , n 2 3 ] , Ω ( n 2 / d ) a m p ; if d ∈ [ n 2 3 , n 4 5 ] , Ω ( d 1 4 n / log ⁡ n ) a m p ; if d ∈ [ n 4 5 , ( 1 2 − ε ) n ] . $$\begin{equation*} disc^{+}(G)=\begin {cases} \Omega (d^{\frac {1}{2}}n) &\text {if }d\in [0,n^{\frac {2}{3}}],\\ \Omega (n^2/d) & \text {if } d\in [n^{\frac {2}{3}},n^{\frac {4}{5}}],\\ \Omega (d^{\frac {1}{4}}n/\log n) & \text {if } d\in \left [n^{\frac {4}{5}},(\frac {1}{2}-\varepsilon )n\right ]. \end{cases} \end{equation*}$$ These bounds are best possible if d ≪ n 3 / 4 d\ll n^{3/4} , and the complete bipartite graph shows that d i s c + ( G ) = Ω ( n ) disc^{+}(G)=\Omega (n) cannot be improved if d ≈ n / 2 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 d -regular graph on n n vertices with 1 2 + ε ≤ d n ≤ 1 − ε {\frac {1}{2}+\varepsilon \leq \frac {d}{n}\leq 1-\varepsilon } has a cut of size n d 4 + Ω ( n 5 / 4 / log ⁡ n ) \frac {nd}{4}+\Omega (n^{5/4}/\log n) . This is not necessarily true without the assumption of regularity, or the bounds on d d . The positive discrepancy of regular graphs is controlled by the second eigenvalue λ 2 \lambda _2 , as d i s c + ( G ) ≤ λ 2 2 n + d disc^{+}(G)\leq \frac {\lambda _2}{2} n+d . As a byproduct of our arguments, we present lower bounds on λ 2 \lambda _2 for regular graphs, extending the celebrated Alon-Boppana theorem in the dense regime.