Take the 2-minute tour ×
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.

I am not sure if "recurrence inequality" is the correct term or whether it is possible to actually find an answer to this problem but anyways.

Let $n$ be a fixed natural number. Let $R(x,y)$ be a symmetric function of two variables (the domain is the set of whole numbers), i.e. $R(x,y)=R(y,x)$ and further suppose that:

  • $R(x,y)\le R(x-1,y)+R(x,y-1)$

  • $R(0,i)=n$

Clearly $R(m,m)\le cn$ where $c$ is a natural number depending upon $m$. Is it possible to find the value of $c$ in terms of $m$?

I found that $R(1,1)\le 2n$ ; $R(2,2) \le 6n$ ; $R(3,3) \le 20n$ and $R(4,4) \le 70n$ by hand-computation. The pattern $2,6,20,70$ doesn't seem to be leading anywhere for me though. Does someone have an opinion concerning this?

share|improve this question
    
Is it really necessary to carry around the $n$? Why not divide everything by $n$ and pretend that $n=1$ all everywhere? –  Srivatsan Dec 19 '11 at 12:33
1  
$R(x,y)$ is the Ramsey number? –  Paul Dec 19 '11 at 12:39
    
Yes indeed it is. –  Shahab Dec 19 '11 at 12:49

1 Answer 1

up vote 2 down vote accepted

You can show easily by induction that $$R(x,y)\le \binom{x+y}y n.$$

If $x=0$ or $y=0$ this is clearly true.

Suppose this holds whenever $0\le x+y\le n$.

Let $x+y=n+1$ and $x,y>0$. Then you have $$R(x,y)\le R(x-1,y)+R(x,y-1) \le \binom{x+y-1}y n +\binom{x+y-1}{y-1} n=\binom{x+y}y n.$$

We have used Pascal's rule, see e.g. this question: Proving ${{n} \choose {r}}={{n-1} \choose {r-1}}+{{n-1} \choose r}$ when $1\leq r\leq n$


Note that I get $\binom21=2$, $\binom42=6$, $\binom63=20$, $\binom84=70$ in this way. I.e., I get 2,6,20,70 instead of 2,6,20,50. (I hope I did not make a mistake there.)


Now, when you mentioned in a comment that you are in fact interested in Ramsey numbers, this inequality $$R(r,s) \leq \binom{r+s-2}{r-1}$$ seems to be well-known, it is mention in wikipedia article on Ramsey numbers.

share|improve this answer
    
Thanks. I was aware of this inequality but am not sure is relevant here. –  Shahab Dec 19 '11 at 13:26

Your Answer

 
discard

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.