A variant of Ramsey numbers

Question

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)$?

Answer 1

There is a conjecture of Erdős, Fajtlowicz and Staton which is closely related to your question. Define $\hat{R}(k)$ to be the smallest positive integer $n$ such that any graph on $n$ vertices contains an induced regular subgraph on $k$ vertices. Note that this class includes complete graphs, independent sets and complete balanced multipartite graphs (this balancedness requirement makes it a little different to your question as stated, but you can easily get a large balanced multipartite graph from an unbalanced one). The conjecture then states that $\hat{R}(k) = 2^{o(k)}$. However, to date, the best known bounds are just $$k^{2 - o(1)} \leq \hat{R}(k) \leq R(k).$$ To my mind, this points to your problem being difficult.