Alon–Krivelevich–Sudakov surplus order-of-magnitude conjecture

Let $G$ be a graph with $m$ edges, and let $\mathrm{sp}(G)=\mathrm{mc}(G)-m/2$ denote its surplus, where $\mathrm{mc}(G)$ is the number of edges in a largest bipartite subgraph of $G$. For a fixed graph $H$, let $\mathrm{sp}(m,H)$ be the smallest value of $\mathrm{sp}(G)$ over all $H$-free graphs $G$ with $m$ edges. Alon–Krivelevich–Sudakov conjecture. For any fixed graph $H$, there is a constant $c(H)>0$ such that

$$\mathrm{sp}(m,H)=\Theta(m^{c(H)}).$$

This conjecture seeks the precise order of the surplus for every fixed forbidden graph, strengthening the problem of obtaining a universal lower-bound exponent. The paper presents it as a more difficult conjecture and does not report a resolution.