Eero Räty, Positive discrepancy, MaxCut and eigenvalues of graphs

The positive discrepancy of a graph $G$ of edge density $p$ is defined as the maximum of $e(U) – p|U|(|U|-1)/2$, where the maximum is taken over subsets of vertices in G. In 1993 Alon proved that if G is a $d$-regular graph on $n$ vertices and $d = O(n^{1/9})$, then the positive discrepancy of $G$ is at least $c d^{1/2}n$ for some constant $c$.

We extend this result by proving lower bounds for the positive discrepancy with average degree d when $d < (1/2 – \epsilon)n$. We prove that the same lower bound remains true when $d < n^(2/3)$, while in the ranges $n^{2/3} < d < n^{4/5}$ and $n^{4/5} < d < (1/2 – \epsilon)n$ we prove that the positive discrepancy is at least $n^2/d$ and $d^{1/4}n/log(n)$ respectively.

Our proofs are based on semidefinite programming and linear algebraic techniques. Our results are tight when $d < n^{3/4}$, thus demonstrating a change in the behaviour around $d = n^{2/3}$ when a random graph no longer minimises the positive discrepancy. As a by-product, we also present lower bounds for the second largest eigenvalue of a $d$-regular graph when $d < (1/2 – \epsilon)n$, thus extending the celebrated Alon-Boppana theorem.

This is joint work with Benjamin Sudakov and István Tomon.