This week's seminar in Discrete Mathematics is given by Eero Räty, Umeå university.
Title: Positive discrepancy, MaxCut and eigenvalues of graphs
Abstract: 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 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, up to a logarithmic factor, 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 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 - c)n, thus extending the celebrated Alon-Boppana theorem.
This is joint work with Benjamin Sudakov and István Tomon
