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–ϵ)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–ϵ)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–ϵ)n$, thus extending the celebrated Alon-Boppana theorem.

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