PreprintCC BY 4.0arXiv
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 n2 edge changes to become a Turán graph has positive discrepancy at least ceps n5/4. Consequently, every such regular graph has second eigenvalue at least c'eps n1/4. These results prove two conjectures of Räty, Sudakov and Tomon.
Related
- Turán-type extremal problems for unbalanced signed graphs
- A Vertex-Localized Positive Square-Energy Strengthening of Turán's Theorem
- Turán numbers for suspensions of bipartite 2-regular graphs
- Ramsey--Turán Factors of Non-directed Oriented Cycles in Oriented Graphs
- Characterizing $3$-graphs with Degenerate Codegree Turán Density
BibTeX
@misc{xu2026positive,
title = {{Positive discrepancy of graphs far from Turán graphs}},
author = {Leyou Xu and Bo Zhou},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02681},
eprint = {2610.02681},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02681},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Positive discrepancy of graphs far from Turán graphs
AU - Leyou Xu
AU - Bo Zhou
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.02681
UR - https://arxiv.org/abs/2610.02681
AB - 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.
ER -