Asymptotic optimality conjecture for the construction H_{r,s,t}(n)

Let $g_r(n,m)$ denote the maximum number of vertices that one is required to remove from an $n$-vertex, $(r+1)$-saturated graph with at least $t_r(n)-m$ edges so that the remaining graph is complete $r$-partite. Let $H_{r,s,t}(n)$ be the construction described in the paper, and write $f(n)\ll g(n)$ when $f(n)/g(n)\to 0$ as $n\to\infty$. Asymptotic optimality conjecture. Let $m=m(n)$ satisfy

$$n\ll m\ll n^{\frac{r+1}{r}}.$$

Then

$$g_r(n,m)=(1+o(1))g_r\bigl(H_{r,s,t}(n)\bigr)$$

as $n\to\infty$ for some choice of $s=s(n)$ and $t=t(n)$. This conjecture asserts that, in this range of the number of missing edges, the lower bound supplied by the construction $H_{r,s,t}(n)$ is asymptotically optimal; determining whether this holds remains open.