Multi-color Ramsey number for triangles

For graphs \( G_i\), \( i=1,\dots,k\), let \( r(G_1,\dots,G_k)\) denote the smallest integer \( m\) satisfying the property that if the edges of the complete graph \( K_m\) are colored in \( k\) colors, then for some \( i\), \( 1\leq i\leq k\), there is a subgraph isomorphic to \( G_i\) with all edges in the \( i\)-th color. We denote \( r(n_1, \dots, n_k)= r(K_{n_1}, \dots, K_{n_k})\). The only known exact value for a multi-colored Ramsey number is \( r(3,3,3)=17\) (see [4]). For \( r(3,3,3,3) \), the upper bound of \( 64\) was established by Sanchez-Flores [7] in 1995 while the lower bound of \( 51\) dates back to the 1970s [1]. Concerning \( r(3,3,4)\), Piwakowski and Radziszowski [6] recently proved an upper bound of \( 29\) while the lower bound of \( 28\) is due to Kalbfleisch [5] and is more than 30 years old.

The multi-colored Ramsey numbers are related as follows (as a generalization of Equation (2) from this problem):

\(\displaystyle r(k_1,k_2,\ldots,k_m) \leq 2+\sum_{i=1}^m (r(k_1,\ldots, k_{i-1},k_i-1,k_{i+1},\ldots,k_m)-1), \)

where strict inequality holds if \( \sum_{i=1}^m (r(k_1,\ldots, k_{i-1},k_i-1,k_{i+1},\ldots,k_m)-1)\) is even and for some \( i\), \( r(k_1,\ldots, k_{i-1},k_i-1,k_{i+1},\ldots,k_m)\) is even.

Based on this fact, we can then derive:
\begin{eqnarray*} r(\underbrace{3,\dots,3}_k) -1& \leq& 1+k (r(\underbrace{3,\dots,3}_{k-1}) -1)
& \leq& k! (\frac 1 {k!}+ \frac 1{(k-1)!} + \ldots + \frac {1} {5!} + \frac{r(3,3,3,3)-1}{4!})
& < & k! (e-\frac 1 {12}) \end{eqnarray*}
for \( k \geq 4\).

The lower bound for \( r(\underbrace{3,\dots,3}_k)\) is closely related to the Schur number \( s_k\). A subset of numbers \( S\) is said to be sum-free if, whenever \( i\) and \( j\) are (not necessarily distinct) numbers in \( S\), then \( i+j\) is not in \( S\). The Schur number \( s_k\) is the largest integer such that numbers from \( 1\) to \( s_k\) can be partitioned into \( k\) sum-free sets. It can be shown [2] that, for \( k \geq l\),

\(\displaystyle r(\underbrace{3,\dots,3}_k)-2\geq s_k \geq c (2 s_l+1)^{k/l} \)

for some constant \( c\).

Using a result of Exoo [3] giving \( s_5 \geq 160\), this implies

\(\displaystyle r(\underbrace{3,\dots,3}_k) \geq c (321)^{k/5}. \)

Conjecture ($250, a very old problem of Erdös)

Determine \[ \lim_{k \rightarrow \infty} (r(\underbrace{3,\dots,3}_k))^{1/k}. \]

It is known (see [1]) that \( r(\underbrace{3,\dots,3}_k)\) is supermultiplicative in \( k\), so the above limit exists.

Problem ($100)

Is the above limit finite or not?

Any improvement for small values of \( k\) will give a better general lower bound. The current range for this limit is between \( (321)^{1/5} \approx 3.171765 \ldots\) and infinity.

Bibliography
1 F. R. K. Chung, On the Ramsey numbers N(3,3,...,3;2), Discrete Math. 5 (1973), 317-321.

2 F. R. K. Chung and C. M. Grinstead, A survey of bounds for classical Ramsey numbers, Journal of Graph Theory 7 (1983), 25-37.

3 G. Exoo, A lower bound for Schur numbers and multicolor Ramsey numbers, Electronic J. of Combinatorics 1 (1994), # R8.

4 R. E. Greenwood and A. M. Gleason, Combinatorial relations and chromatic graphs, Canad. J. Math. 7 (1955), 1-7.

5 J. G. Kalbfleisch, Chromatic graphs and Ramsey's theorem, Ph. D. thesis, University of Waterloo, Jan. 1966.

6 K. Piwakowski and S. P. Radziszowski, New upper bound for the Ramsey number \( R(3,3,4)\), preprint.

7 A. Sanchez-Flores, An improved bound for Ramsey number \( N(3,3,3,3;2)\), Discrete Math. 140 (1995), 281-286.