Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
    
I actually knew about Erdos's quote about R(5; 5).. Somehow, I couldn't relate the problem to R(r; s). Thanks! –  aelguindy Apr 16 '12 at 20:55
    
@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. –  Austin Mohr Apr 16 '12 at 20:59
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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