Räty–Sudakov–Tomon conjecture on graph surplus and least eigenvalues

Räty, Sudakov, and Tomon conjectured that graphs far from cluster-like structures must have large positive discrepancy, surplus, and least-eigenvalue magnitude. The conjecture connects structural distance from Turán graphs or disjoint unions of cliques with quantitative spectral and extremal bounds.

Known results

• Jin, Milojević, Tomon, and Zhang proved a weaker bound $\operatorname{disc}^{+}(G)\geq \Omega_{\delta}(n^{1+c})$ for some absolute $c>0$.
• Janzer, Tomon, and Yip proved $\operatorname{disc}^{+}(G)\geq n^{5/4-o(1)}$.
• The same work established $\operatorname{sp}(G)\geq n^{5/4-o(1)}$ for graphs far from disjoint unions of cliques.

October 2026 claimed resolution

An October 1, 2026 report on Fredy Yip's preprint claims fixed-constant bounds $\operatorname{disc}^{+}(G),\operatorname{sp}(G)\geq \Omega_{\epsilon}(n^{5/4})$ and $|\lambda_n|\geq \Omega_{\epsilon}(n^{1/4})$, removing the earlier $o(1)$ losses. Under an $n^{-o(1)}$ distance assumption it also reports $n^{1/4-o(1)}$ and $n^{5/4-o(1)}$ bounds. These are claims from an unrefereed preprint.

Current status (as of October 2026): Earlier asymptotic bounds are established, while the full fixed-constant conjecture is only claimed in an unrefereed preprint and remains unverified.