Tight bounds for positive discrepancy via eigenvalues

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^{\mathrm{\prime }}\times n^{\mathrm{\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^{\mathrm{\prime }}+1)$. We use this lemma to improve a number of recent results on the MaxCut, bisection width, and discrepancy of graphs. Among others, 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\mathrm{/}2+n^{5\mathrm{/}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\mathrm{/}4-{\mathrm{\Omega }}_{\epsilon }(d^{1\mathrm{/}3}n)$ for $d\le (1-\epsilon )n\mathrm{/}2$, which is optimal for $d=\mathrm{\Omega }(n)$. This confirms a conjecture of Räty, Sudakov and Tomon.