Positive discrepancy of graphs far from Turán 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án 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äty, Sudakov and Tomon.