---
abstract: 'Since 2002, the best known upper bound on the Ramsey numbers $R_n(3)=R(3,\dots,3)$ is $R_n(3) \le n!(e-1/6)+1$ for all $n \ge 4$. It is based on the current estimate $R_4(3) \le 62$. We show here how any closing-in on $R_4(3)$ yields an improved upper bound on $R_n(3)$ for all $n \ge 4$. For instance, with our present adaptive bound, the conjectured value $R_4(3)=51$ implies $R_n(3) \le n!(e-5/8)+1$ for all $n \ge 4$.'
author:
- 'S. Eliahou'
title: 'An adaptive upper bound on the Ramsey numbers $R(3,\dots,3)$ '
---

Introduction
============

For $n \ge 1$, the $n$-color Ramsey number $R_n(3)=R(3,\dots,3)$ denotes the smallest $N$ such that, for any $n$-coloring of the edges of the complete graph $K_N$, there is a monochromatic triangle. See e.g. [@GRS; @Ram; @Soi] for background on Ramsey theory. There is a well known recursive upper bound on $R_n(3)$ due to [@GG], namely $$\label{rec}
R_n(3) \le n(R_{n-1}(3)-1)+2$$ for all $n \ge 2$. Currently, the only exactly known values of $R_n(3)$ are $R_1(3)=3$, $R_2(3)=6$ and $R_3(3)=17$. As for $n=4$, the current state of knowledge is $$51 \le R_4(3) \le 62.$$ The lower bound is due to [@Ch] and the upper bound to [@FKR], down from the preceding bound $R_4(3) \le 64$ in [@S-F]. Moreover, it is conjectured in [@XuR] that $$R_4(3) = 51.$$ Here is a brief summary of successive upper bounds on $R_n(3)$. In [@GG], the authors proved that $$R_n(3) \le n!e+1$$ for all $n \ge 2$. Whitehead’s results [@Whi] led to $$R_n(3) \le n!(e-1/24)+1$$ for all $n \ge 2$, and Wan [@Wan] further improved it to $$R_n(3) \le n!(e-e^{-1}+3)/2+1.$$ The last improvement came in 2002, when it was proved in [@XuXC] that $$R_n(3) \le n!(e-1/6)+1$$ for all $n \ge 4$. That bound relies on the estimate $R_4(3) \le 62$ by [@FKR].

Because of the recurrence relation , any improved upper bound on $R_{k}(3)$ for some $k \ge 4$ will yield an improved upper bound on $R_{n}(3)$ for all $n \ge k$. Our purpose here is to make this automatic improvement explicit. For instance, combined with our adaptive upper bound, the above-mentioned conjecture $R_4(3) = 51$ implies $$R_n(3) \le n!(e-5/8)+1$$ for all $n \ge 4$. This would be a substantial improvement over the current upper bound $n!(e-1/6)+1$, since $e-1/6 \approx 2.55$ while $e-5/8 \approx 2.09$.

Main results
============

As reported in [@radzi], it is proved in [@XuXC] that $$R_n(3) \le n!(e-1/6)+1$$ for all $n \ge 4$. But the latter paper is in Chinese and not easily accessible to English readers. In this section, we prove a somewhat more general statement. We shall need the formulas below.

Useful formulas
---------------

In proving $R_n(3) \le n!e+1$, the authors of  [@GG] used without comment the formula $$\lfloor (n+1)!e \rfloor = (n+1)\lfloor n!e \rfloor+1$$ for all $n\ge 1$. For convenience, we provide a proof here, as a direct consequence of the auxiliary formula below.

\[n!e\] For all $n \ge 1$, we have $
\lfloor n!e \rfloor = \sum_{i=0}^n\, {n!}/{i!} \,.
$

We have $ e = 1/0!+1/1!+\sum_{i=2}^{\infty} 1/i! = 2+\sum_{i=2}^{\infty} 1/i!$. Since $e < 3$, it follows that $\sum_{i=2}^{\infty} 1/i! < 1$. Now $n!e= \sum_{i=0}^n\, {n!}/{i!} + \sum_{i=n+1}^\infty\, {n!}/{i!}$. The left-hand summand is an integer, while the right-hand one satisfies $$\sum_{i=n+1}^\infty\, {n!}/{i!} = \sum_{j=1}^\infty\, \frac{1}{\Pi_{k=1}^j (n+k)} \le \sum_{i=2}^\infty\, 1/{i!} < 1.$$ This concludes the proof.

\[fact\] For all $n \ge 1$, we have $
\lfloor (n+1)!e \rfloor = (n+1)\lfloor n!e \rfloor+1.
$

Applying Proposition \[n!e\] for $n+1$ and then for $n$, we have $$\begin{aligned}
\lfloor (n+1)!e \rfloor & = & \sum_{i=0}^{n+1}\, {(n+1)!}/{i!} \\
& = & (n+1)\sum_{i=0}^{n}\, {n!}/{i!} + (n+1)!/(n+1)! \\
& = & (n+1)\lfloor n!e \rfloor+1. \qedhere\end{aligned}$$

An optimal model
----------------

We now exhibit an optimal model for the recursion .

\[lem rec\] Given $q \in {\mathbb Q}$, let $f \colon {\mathbb N}\to {\mathbb Z}$ be defined by $f(n)= \lfloor n!(e-q) \rfloor+1$ for $n \in {\mathbb N}$. Then, for all $n \in {\mathbb N}$ such that $n!q \in {\mathbb Z}$, we have $$\label{rec f}
f(n+1) = (n+1)(f(n)-1)+2.$$

We have $$\begin{aligned}
f(n+1) & = & \lfloor (n+1)!(e-q) \rfloor +1 \\
& = & \lfloor (n+1)!e \rfloor - (n+1)!q+1 \,\,\, \textrm{ [since $(n+1)!q \in {\mathbb Z}$]} \\
& = & (n+1)\lfloor n!e \rfloor +1 - (n+1)!q+1 \,\,\, \textrm{[by Corollary~\ref{fact}]} \\
& = & (n+1)\lfloor n!(e-q) \rfloor +2  \,\,\, \textrm{ [since $n!q \in {\mathbb Z}$]} \\
& = & (n+1)(f(n)-1)+2. \qedhere\end{aligned}$$

An adaptive bound
-----------------

Our adaptive upper bound on $R_n(3)$ is provided by the following statements.

\[main prop\] Let $k \in {\mathbb N}$ and $q \in {\mathbb Q}$ satisfy $k \ge 2$, $R_k(3) \le k!(e-q)+1$ and $k!q \in {\mathbb N}$. Then $R_n(3) \le n!(e-q)+1$ for all $n \ge k$.

As in Proposition \[lem rec\], denote $f(n)=\lfloor n!(e-q) \rfloor+1$ for $n \in {\mathbb N}$. By assumption, we have $$\label{bound}
R_k(3) \le f(k)$$ and $k!q \in {\mathbb Z}$. It suffices to prove the claim for $n=k+1$, since if $k!q \in {\mathbb N}$ then $(k+1)!q \in {\mathbb N}$. By successive application of , and , we have $$\begin{aligned}
R_{k+1}(3) & \le & (k+1)(R_k(3)-1)+2 \\
& \le & (k+1)(f(k)-1)+2 \\
& = & f(k+1).\end{aligned}$$ Note that using is allowed by Proposition \[lem rec\] and the assumption $k!q \in {\mathbb N}$.

\[main thm\] Let $k \ge 2$ be an integer. Let $a \in {\mathbb N}$ satisfy $a \le \lfloor k!e \rfloor - R_k(3)+1$, and let $q=a/k!$. Then $R_n(3) \le n!(e-q)+1$ for all $n \ge k$.

We have $a \le k!e-R_k(3)+1$, so $R_k(3) \le k!e-a+1=k!(e-q)+1$. Moreover $k!q=a \in {\mathbb N}$. The conclusion follows from Proposition \[main prop\].

Theorem \[main thm\] is the best possible application of Proposition \[main prop\]. Indeed, with the value $a'=\lfloor k!e \rfloor - R_k(3)+2$ and $q'=a'/k!$, it no longer holds that $R_k(3) \le k!(e-q')+1$.

The case $k=4$
--------------

We now apply the above result to the case $k=4$. We only know $51 \le R_4(3) \le 62$ so far. Note that by Proposition \[n!e\], we have $$\label{4!e}
\lfloor 4!e \rfloor = \sum_{i=0}^4 4!/i! = 24+24+12+4+1= 65.$$

\[a\] Let $a \in {\mathbb N}$ satisfy $a \le 66-R_4(3)$. Then setting $q=a/24$, we have $R_n(3) \le n!(e-q)+1$ for all $n \ge 4$.

By , $a$ satisfies the hypotheses of Theorem \[main thm\]. The conclusion follows.

When the exact value of $R_4(3)$ will be known, Proposition \[a\] will provide an adapted upper bound on $R_n(3)$ for all $n \ge 4$. In the meantime, here are three possible outcomes.

\[62\] $R_n(3) \le n!(e-1/6)+1$ for all $n \ge 4$.

Since $R_4(3) \le 62$, we may take $a=4$ in Proposition \[a\]. The conclusion follows from that result with $q=a/4!=1/6$.

Note that the above bound dos not extend to $n=3$, since $R_3(3)=17$, whereas by Proposition \[n!e\], we have $\lfloor 3!(e-1/6)\rfloor +1= \lfloor 3!e\rfloor = 3!+3!+3+1=16$.

As mentioned earlier, it is conjectured in [@XuR] that $R_4(3)=51$. If true, Proposition \[a\] will yield the following improved upper bound.

\[51\] If $R_4(3)=51$, then $R_n(3) \le n!(e-5/8)+1$ for all $n \ge 4$.

By Proposition \[a\], with $a = 66-51=15$ and $q=15/4!=5/8$.

As noted in the Introduction, this would be a substantial improvement over the current upper bound $n!(e-1/6)+1$, since $e-1/6 \approx 2.55$ whereas $e-5/8 \approx 2.09$.

An intermediate step would be, for instance, to show $R_4(3) \le 54$ if at all true. This would yield the following weaker improvement.

\[54\] If $R_4(3) \le 54$, then $R_n(3) \le n!(e-1/2)+1$ for all $n \ge 4$.

By Proposition \[a\], with $a = 66-54=12$ and $q=a/4!=1/2$.

The above three corollaries are best possible applications of Proposition \[a\], as in each case we took the largest admissible value for $a \in {\mathbb N}$.

The case $k=5$
--------------

Let us also briefly consider the case $k=5$. At the time of writing, we only know $162 \le R_5(3) \le 307$. See [@radzi].

\[b\] Let $a \in {\mathbb N}$ satisfy $a \le 327-R_5(3)$. Then setting $q=a/120$, we have $R_n(3) \le n!(e-q)+1$ for all $n \ge 5$.

By Theorem \[main thm\] and the value $\lfloor 5!e \rfloor=326$ given by Proposition \[n!e\].

Here again are three possible outcomes. Knowing only $R_5(3) \le 307$ does not allow to improve the current estimate $R_n(3) \le n!(e-1/6)+1$. At the other extreme, if $R_5(3) = 162$ holds true, it would yield $R_n(3) \le n!(e-11/8)+1$ for all $n \ge 5$. As an intermediate estimate, if $R_5(3) \le 227$ holds true, it would imply $R_n(3) \le n!(e-5/6)+1$ for all $n \ge 5$.

Concluding remarks
==================

On $\lim_{n \to \infty} R_n(3)^{1/n}$
-------------------------------------

The adaptive upper bound on $R_n(3)$ given by Theorem \[main thm\] may still be quite far from reality, as the asymptotic behavior of $R_n(3)$ remains poorly understood. For instance, is there a constant $c$ such that $R_{n+1}(3) \le cR_n(3)$ for all $n$? Or, maybe, such that $R_n(3) \ge c n!$ for all $n$? The former would imply that $\lim_{n \to \infty} R_n(3)^{1/n}$, known by [@ChG] to exist, is finite, whereas the latter would imply $\lim_{n \to \infty} R_n(3)^{1/n}=\infty$. At the time of writing, it is not known whether that limit is finite or infinite. See e.g. [@LRX], where this question is discussed together with related problems.

Link with the Schur numbers
---------------------------

The Schur number $S(n)$ is defined as the largest integer $N$ such that for any $n$-coloring of the integers $\{1,2,\dots,N\}$, there is a monochromatic triple of integers $1 \le x,y,z \le N$ such that $x+y=z$. The existence of $S(n)$ was established by Schur in [@Schur], an early manifestation of Ramsey theory. Still in [@Schur], Schur proved the upper bound $$\label{S(n)}
S(n) \le n!e-1$$ for all $n \ge 2$. The similarity with the upper bound $R_n(3) \le n!e+1$ proved 40 years later in [@GG] is striking. In fact, there is a well known relationship between these numbers, namely $$\label{S and R}
S(n) \le R_n(3)-2.$$ Thus, via , our adaptive upper bound on $R_n(3)$ given by Theorem \[main thm\] also yields an upper bound on $S(n)$.

**Acknowledgements.** The author wishes to thank L. Boza and S.P. Radziszowski for informal discussions during the preparation of this note and for their useful comments on a preliminary version of it.

[999]{} <span style="font-variant:small-caps;">F.R.K. Chung</span>, On The Ramsey Numbers $N (3, 3, \dots, 3; 2)$, Discrete Mathematics 5 (1973) 317–321. <span style="font-variant:small-caps;">F.R.K. Chung and C. Grinstead</span>, A Survey of Bounds for Classical Ramsey Numbers, J. Graph Theory 7 (1983) 25–37. <span style="font-variant:small-caps;">S.E. Fettes, R.L. Kramer and S.P. Radziszowski</span>, An upper bound of $62$ on the classical Ramsey number $R(3,3,3,3)$, Ars Combin. 72 (2004) 41–63. <span style="font-variant:small-caps;">R.L. Graham, B.L. Rothschild and J.H. Spencer</span>, Ramsey Theory, John Wiley & Sons, 1990. <span style="font-variant:small-caps;">R.E. Greenwood and A.M. Gleason</span>, Combinatorial relations and chromatic graphs, Canadian J. Math 7 (1955) 1–7. <span style="font-variant:small-caps;">M. Liang, S.P. Radziszowski and X. Xu</span>, On a diagonal conjecture for classical Ramsey numbers, Discrete Appl. Math. 267 (2019) 195–200. <span style="font-variant:small-caps;">S.P. Radziszowski</span>, Small Ramsey numbers, Electron. J. Combin. 1 (1994), Dynamic Survey DS1, Revision \#15 (2017), 104pp. (electronic). <span style="font-variant:small-caps;">F.P. Ramsey</span>, On a Problem of Formal Logic, Proceedings of the London Mathematical Society 30 (1930) 264–286. <span style="font-variant:small-caps;">A.T. Sánchez-Flores</span>, An improved upper bound for Ramsey number $N(3, 3, 3, 3; 2)$, Discrete Math. 140 (1995) 281–286. <span style="font-variant:small-caps;">I. Schur</span>, Uber die Kongruenz $x^m+y^m \equiv z^m \pmod{p}$, Jahresbericht der Deutschen Mathematiker Vereinigung 25 (1916) 114–117. <span style="font-variant:small-caps;">A. Soifer</span>, The mathematical coloring book. Mathematics of coloring and the colorful life of its creators. Springer, New York, 2009. ISBN: 978-0-387-74640-1. <span style="font-variant:small-caps;">H. Wan</span>, Upper bounds for Ramsey numbers $R(3,3,\dots,3)$ and Schur numbers, J. Graph Theory 26 (1997) 119–122. <span style="font-variant:small-caps;">E.G. Whitehead, Jr.</span>, Algebraic structure of chromatic graphs associated with the Ramsey number N(3,3,3;2), Discrete Math. 1 (1971/72) 113–114. <span style="font-variant:small-caps;">X. Xu and S.P. Radziszowski</span>, On some open questions for Ramsey and Folkman numbers. Graph theory – favorite conjectures and open problems. 1, 43–62, Probl. Books in Math., Springer, \[Cham\], 2016. <span style="font-variant:small-caps;">X. Xu, Z. Xie and Z. Chen</span>, Upper bounds for Ramsey numbers $R_n(3)$ and Schur numbers, Mathematics in Economics 19 (2002) 81–84.

**Author’s adress:**\
Shalom Eliahou, Univ. Littoral Côte d’Opale,\
EA 2597 - LMPA - Laboratoire de Mathématiques Pures et Appliquées Joseph Liouville, F-62228 Calais, France,\
CNRS, FR 2956, France.\
E-mail: [eliahou@univ-littoral.fr](eliahou@univ-littoral.fr)
