Discrepancy of graphs
Part of the Oxford Discrete Maths and Probability Seminar, held via Zoom. Please see the seminar website for details.
Abstract
The positive discrepancy of a graph $G$ is the maximum surplus of edges in an induced subgraph of $G$ compared to its expected size. This quantity is closely related to other well studied parameters, such as the minimum bisection and the spectral gap. I will talk about the extremal behavior of the positive discrepancy among graphs with given number of vertices and average degree, uncovering a surprising pattern. This leads to an almost complete solution of a problem of Alon on the minimum bisection and let's us extend the Alon-Boppana bound on the second eigenvalue to dense graphs.
Joint work with Eero Räty and Benny Sudakov.