# 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.