Tight bounds for positive discrepancy via eigenvalues

Abstract

Given an $n\times n$ symmetric matrix $M$ with largest eigenvalue ${\lambda }_1\ge 0$, it is easy to show that the solution of the optimisation problem ${\max }_{v\in [-1,1{]}^n}{v}^{T}Mv$ is at most ${\lambda }_{1}n$. We prove the following converse: if every $n^{\prime }\times n^{\prime }$ principal submatrix of $M$ has maximal eigenvalue at least $\lambda$, then ${\max }_{v\in [-1,1{]}^n}{v}^{T}Mv\ge \lambda (n-n^{\prime }+1)$. This allows us to lift results about the second largest and the smallest eigenvalue of graphs to the (a priori more difficult) setting of positive discrepancy and MaxCut. Using this new connection, we prove that every $n$-vertex $m$-edge graph that is far from a disjoint union of cliques has a cut of size at least $m/2+n^{5/4-o(1)}$, which is sharp up to the $o(1)$-term. Moreover, we prove that every $d$-regular $n$-vertex graph has bisection width at most $dn/4-{\Omega }_{\epsilon }(d^{1/3}n)$ for $d\le (1-\epsilon )n/2$, which is optimal for $d=\Omega (n)$. This confirms a conjecture of Räty, Sudakov and Tomon.

15 pages