2
$\begingroup$

For every integer $k \ge 2$,

$$R_k \le \left \lfloor k!e \right \rfloor + 1$$

where $R_k$ denotes $R(\underbrace{{3, 3, \ldots, 3}}_{k})$.

$\endgroup$
  • $\begingroup$ I am not sure whether this helps here, but here is another question about $R_k$. No answer was posted so far, but comments there suggest that it can proved similarly to this. $\endgroup$ – Martin Sleziak Mar 29 '16 at 10:29
  • $\begingroup$ @MartinSleziak Using $R_{k+1}\le(k+1)(R_k-1)+2$ I can even get a stronger bound $R_k\le2n!+2$? $\endgroup$ – Colescu Mar 29 '16 at 11:20
  • $\begingroup$ Do you have some reason to believe that there should be equality? Maybe it would be worth mentioning the source of the problem. (It is advised to provide context.) And if you thing you have proof of the result, you can post it as an answer. add it to your question or as a separate question. That way there is a chance that some other users will have a look at your proof and point out mistakes if there are some. $\endgroup$ – Martin Sleziak Mar 29 '16 at 11:28
  • $\begingroup$ In this paper the author derives the inequality $R_n \le n! \left(\frac{e+e^{-1}+3}2\right) +1$. I found a reference to this result here. $\endgroup$ – Martin Sleziak Mar 29 '16 at 11:44
  • 1
    $\begingroup$ @MartinSleziak Thank you! I was wrong about the bound $R_k \le 2n! + 2$, sorry. I have asked a new question pointing out the source of this question here. $\endgroup$ – Colescu Mar 29 '16 at 13:02
2
$\begingroup$

The following text is quoted from the paper R. E. Greenwood, A. M. Gleason: Combinatorial relations and chromatic graphs, Canad. J. Math. 7(1955), 1-7, DOI: 10.4153/CJM-1955-001-4.

5. Upper and Lower Bounds for $n(3^r)$. Let $t_r=n(3^r)=n(3,3,\dots,3)$. The upper bounds used in Theorems 1, 4 and 5 can all be obtained by the use of

THEOREM 6. $$t_{r+1} \le (r+1)(t_r-1)+2.$$

This theorem is easily proved by induction; and then it is trivial to establish, also by induction, that $$t_{r+1} \le 3(r+1)!.$$ A somewhat sharper inequality may be obtained, however, without any added difficulties. It has already been established that $$t_r \le \lfloor (r!)e \rfloor +1, \qquad r=2,3,4,$$ where $\lfloor M \rfloor$ means the greatest integer contained in $M$. Such a bound holds for all integers $r\ge 2$, for if it did not there would be a least integer, say $s+1$, for which the relation failed to hold. By Theorem 6, $$t_{s+1} \le (s+1) \lfloor (s!)e \rfloor+2, \qquad s\ge2$$ But $\lfloor (s+1)!e \rfloor = (s+1) \lfloor (s!)e \rfloor +1$, and hence $$t_{s+1} \le \lfloor (s+1)!e \rfloor +1$$ and the stated upper bound follows.

A proof of the inequality stated as Theorem 6 can also be found here: Ramsey Number Inequality: $R(\underbrace{3,3,...,3,3}_{k+1}) \le (k+1)(R(\underbrace{3,3,...3}_k)-1)+2$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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