# Coloring a Complete Graph in Three Colors, Proving that there is a Complete Subgraph

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.

• Is there a reason this appeared almost simultaneously with this question? – joriki Jun 2 '16 at 21:34
• @joriki, It is a question from some homework we got. Apparently both of us have not succeed and decided to ask here. – 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{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{k}-1})$ , where $t=\sqrt{k}-1$ , as $\frac{3}{\sqrt{k}}<\frac{1}{\sqrt{k}-1}$ for $k>1$ .

(easy to check as $\sqrt{k}$ , $\sqrt{k}$ are mono. increasing and $\sqrt{k}>\sqrt{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:

$R(p,p)\leq2^{\frac{1}{50}\log_{2}k}=k^{\frac{1}{50}}=\sqrt{k}$

As $t=\sqrt{k}-1$ and $G$ has a copy of $K_{t+1}=K_{\sqrt{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.