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


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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.