1
$\begingroup$

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.

  • 0
    Are you coloring vertices or edges? If vertices then a better bound seems trivial?2012-04-09

1 Answers 1

1

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'.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}}$