The well known *Ramsey number* $R(k)$ is the least integer $n$ so that every 2-edge coloring of $K_n$ contains a monochromatic $K_k.$

Another interpretation of the above definition is that every graph on $R(k)$ vertices has a $K_k$ or $\overline{K_k}$ as a (induced) subgraph. There are many generalizations of Ramsey numbers and I am curious to see what happens if we push this in the direction of complete multipartite graphs.

Let $\widetilde{R}(k)$ be the least integer $n$ so that every graph on $n$ vertices must contain an **induced** complete multipartite graph on $k$ vertices.

Since $K_k$ and $\overline{K}_k$ are complete multipartite graphs we have $\widetilde{R}(k) \leq R(k)$. What I am wondering is whether allowing other complete multipartite graph reduces the order of $\widetilde{R}(k)$ significantly. More precisely

Is it true that $\widetilde{R}(k) = o(R(k))$?

I am still looking at the available literature so if anyone is aware of results in this direction that is also appreciated. In particular is anybody aware of non-obvious bounds for $\widetilde{R}(k)$?