Color the edges of a complete graph on $n$ vertices $K_n$ in three colors (red,blue,yellow) such that at most $\dfrac{n^2}{k}$ are colored red ($k$ is some natural number).

Prove that $K_n$ contains either blue $K_p$ or yellow $K_p$ (complete subgraph on p vertices where all of its edges are colored blue or all are colored yellow) with $p=\dfrac{1}{100}\log k$.

What are the bounds for $p$?

I know that a complete graph $K_n$ has ${n\choose 2}$ edges, thus if $\dfrac{n^2}{k}$ are colored red, we have $\dfrac{n^2}{2}-\dfrac{n}{2}-\dfrac{n^2}{k}$ edges that are colored blue or yellow. Now I thought to use Ramsey theorem, but I don't know how to find the relavant bounds for $p$.

Any help will be very appreciated.

  • $\begingroup$ Is there a reason this appeared almost simultaneously with this question? $\endgroup$ – joriki Jun 2 '16 at 21:34
  • 1
    $\begingroup$ @joriki, It is a question from some homework we got. Apparently both of us have not succeed and decided to ask here. $\endgroup$ – user344113 Jun 3 '16 at 3:14

We know that the number of edges in $K_{n}$ is: $|E(K_{n})|={n \choose 2}=\frac{n(n-1)}{2}=\frac{n^{2}}{2}-\frac{n}{2}$

We are given that at most $n^{2}/k$ edges are colored Red, and thus at least $n^{2}/2-n/2-n^{2}/k$ edges are not Red,

i.e. White or Black (Also, $k$ should be at least 3, for the question to make sense - so we will have

$n^{2}/k\leq n^{2}/2-n/2$ , for large enough $n$ ).

Denote by $G$ the graph we obtain from $K_{n}$ by removing the Red colored edges.

Let $t=\sqrt[50]{k}-1$ . By Turan's theorem, if $G$ has no copy of $K_{t+1}$ (regardless of color) then $|E(G)|\leq\frac{n^{2}}{2}(1-\frac{1}{t})$ .

However, $|E(G)|\geq\frac{n^{2}}{2}-\frac{n}{2}-\frac{n^{2}}{k}=\frac{n^{2}}{2}(1-\frac{1}{n}-\frac{2}{k})\underset{(*)\,k\leq n^{2}\Rightarrow\sqrt{k}\leq n}{\geq}\frac{n^{2}}{2}(1-\frac{1}{\sqrt{k}}-\frac{2}{\sqrt{k}})=\frac{n^{2}}{2}(1-\frac{3}{\sqrt{k}})$ .

And we have: $\frac{n^{2}}{2}(1-\frac{3}{\sqrt{k}})\geq\frac{n^{2}}{2}(1-\frac{1}{\sqrt[50]{k}-1})$ , where $t=\sqrt[50]{k}-1$ , as $\frac{3}{\sqrt{k}}<\frac{1}{\sqrt[50]{k}-1}$ for $k>1$ .

(easy to check as $\sqrt{k}$ , $\sqrt[50]{k}$ are mono. increasing and $\sqrt{k}>\sqrt[50]{k}$ ).

$\Longrightarrow|E(G)|>\frac{n^{2}}{2}(1-\frac{1}{t})$ , and so by Turan's theorem,$ G$ has a copy of $K_{t+1}$ .

Let $p=\frac{1}{100}\log_{2}k$ . We know from class the following upper bound on Ramsey's numbers:$R(m,m)\leq4^{m}=2^{2m}$

And so we have:


As $t=\sqrt[50]{k}-1$ and $G$ has a copy of $K_{t+1}=K_{\sqrt[50]{k}}$ , then every coloring of edges of $G$ in 2 colors (White and Black)

is also a 2-coloring of this $K_{t+1}$, and by Ramsey's theorem, will contain either White $K_{p}$ or Black $K_{p}$ , as required.


Your Answer

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

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