{"id":"arxiv/2610.02681","url":"https://arxiv.org/abs/2610.02681","tags":["math.CO"],"score":0,"title":"Positive discrepancy of graphs far from Turán graphs","domain":"math.CO","source":"arxiv","authors":["Leyou Xu","Bo Zhou"],"reviews":0,"subject":"math.CO","summary":"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.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-02","reactions":{}}