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

Eero Räty, Positive discrepancy, MaxCut and eigenvalues of graphs
April 9 Tuesday @ 4:30 PM - 5:30 PM KST
Room B332, IBS (기초과학연구원)
Eero Räty
Umeå University
www.umu.se/en/staff/eero-raty/
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 \le (1/2 - \epsilon)n$. We prove that the same lower bound remains true when $d \leq n^(2/3)$, while in the ranges $n^{2/3} \le d \le n^{4/5}$ and $n^{4/5} \le d \le (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 \le 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 \le (1/2 - \epsilon)n$, thus extending the celebrated Alon-Boppana theorem.
This is joint work with Benjamin Sudakov and István Tomon.