1
$\begingroup$

I am attempting to solve some problems here. For exercise 1, the tightest result I could get is $4^k$. Is that the mininum possible bound?

I am trying to either find a tight example, or find a better estimate and I am failing at both tasks. If my proof might help with finding a tight example, I can post it (I still have not verified it very thoroughly though..).

1 Answers 1

3

The minimum number of vertices required to force either a $k$-clique or a $k$-anticlique in any graph is known as the Ramsey Number $R(k,k)$. For bounds, I refer you to the Wikipedia article.

  • 0
    @aelguindy They seem to be different problems at first glance, since Ramsey numbers are usually stated in terms of red-blue edge-colorings. If you associate "red edge" with "that edge belongs to the graph" and "blue edge" with "that edge does not belong to the graph", then you see how the questions are actually the same.2012-04-16