0
$\begingroup$

problem

Suppose we color the edges of $K_n$ with colors Black, White and Red so that at most $n^2/k$ of the edges are colored Red.

  • Show that the graph contains either a Black $K_p$ or a White $K_p$ with $p = \frac{1}{100}\log{k}$
  • Show that there is a coloring of $K_n$ with colors Black, White and Red so that at most $n^2/k$ of the edges are colored Red, and yet the resulting graph does not contain either a Black $K_p$ or a White $K_p$ with $p = 100\log{k}$

I am not sure how to incorporate Ramsey theory to solve the above problem.

$\endgroup$
  • $\begingroup$ There is no problem. $\endgroup$ – qmd Jun 2 '16 at 12:40
  • $\begingroup$ Edited, sorry :) $\endgroup$ – Bob Kardeshian Jun 2 '16 at 12:44
  • 2
    $\begingroup$ Please do not use pictures for critical portions of your post. Pictures cannot be searched and are inaccessible to those using screen readers. $\endgroup$ – gebruiker Jun 2 '16 at 14:21
  • $\begingroup$ Edited again :) $\endgroup$ – Bob Kardeshian Jun 2 '16 at 14:32
  • $\begingroup$ Is there a reason this appeared almost simultaneously with this question? $\endgroup$ – joriki Jun 2 '16 at 21:35

Your Answer

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

Browse other questions tagged or ask your own question.