Problem in restricted 3 edge coloring

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.

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