How many nodes before k-clique or k-anti-clique?

$\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..).

$\endgroup$

1 Answer

$\begingroup$

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.

$\endgroup$ 2

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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