On April 9, 2024, Eero Räty from Umeå University gave a talk at the Discrete Math Seminar on lower bounds for the positive discrepancy of graphs of average degree d. The title of his talk was “Positive discrepancy, MaxCut and eigenvalues of graphs.” He is currently visiting the IBS Extremal Combinatorics and Probability Group for 2 months.

## 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.