Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 1 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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