Positive discrepancy of graphs far from Tur\'an graphs

Abstract

We prove that, for every $\eps>0$, any $n$-vertex graph that needs at least $\eps n^2$ edge changes to become a Tur\'an graph has positive discrepancy at least $c_\eps n^{5/4}$. Consequently, every such regular graph has second eigenvalue at least $c'_\eps n^{1/4}$. These results prove two conjectures of R\"aty, Sudakov and Tomon.