# Prove the following inequality: $N(P,P,2)\leq 4^{P-1}$

I've made very little headway on this problem, so any help is appreciated.

Edit: Sorry, I should have explained that. In general, $N(p,q,2)$ is the smallest value of $n$ such that a red-blue coloring of $K_n$ must contain either a red $K_p$ or a blue $K_q$ graph ($K_n$ is a complete graph on $n$ vertices). So, $N(P,P,2)$ is the smallest value of $n$ such that a red-blue coloring of $K_n$ must contain either a red $K_P$ or a blue $K_P$ graph.

-
What is the definition of $N(\cdot,\cdot,\cdot)$? – Austin Mohr Apr 9 '12 at 2:44
Are you coloring vertices or edges? If vertices then a better bound seems trivial? – Jernej Apr 9 '12 at 9:17

I will prove a stronger result. We will prove that $$N(t,s)\leq N(t-1,s)+N(t,s-1)$$$\bf{Proof}$: Let $n=N(t-1,s)+N(t,s-1)$, then assume that we are giving a coloring of $K_n$. We want to find either a red copy of $K_t$ or a blue copy of $K_s$. Let $x\in K_n$ be given. As the graph is complete, we have that $deg(x)=n-1=N(t-1,s)+N(t,s-1)-1$. Either there are $N(t-1,s)$ red edges or $N(t,s-1)$ blue edges (let me know if you want me to elaborate in this part). Without loss of generality, let us say that the first case holds. We have at least $a=N(t-1,s)$ red edges. Then consider a subgraph $K_a$ that is formed by the $a$-number of vertices adjacent to $x$ through a red edge. If there is a blue copy of $K_s$ in $K_a$ we are done. If otherwise, by definition of $N(t-1,s)$, we have a red copy of $K_{t-1}$ in $K_a$, by adjoining $x$ to $K_a$, we have a red copy of $K_t$ in $K_n$.
Hence the bound is proven. Now we prove that $$N(t,s)\leq \binom{s+t-2}{t-1}$$by induction on $s+t$. Note that if $t=2$ or $s=2$, then we have that $N(t,2)=t$. And hence we would have that $$t=N(t,2)\leq\binom{2+t-2}{t-1}=t$$ holds. This was our base case. Then assume that it holds for any pair $(t',s')$ with $t'+s'<t+s$.Then by our recursive looking bound we have that $$N(t,s)\leq N(t-1,s)+N(t,s-1)\leq\binom{s+t-1-2}{t-1-1}+\binom{s-1+t-2}{t}=\binom{s+t-2}{t-1}$$Now we are almost done. Let $t=s$. Then, $N(t,t)\leq\binom{2t-2}{t-1}$. I leave it to you to check that indeed $$\binom{2t-2}{t-1}\leq 2^{2(t-1)}=4^{t-1}$$
$\bf{Remark:}$ You could do a little better since $$\binom{2t-2}{t-1}\leq \frac{2^{2t-2}}{\sqrt{t}}$$