Multicolor Ramsey number for triangles
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
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 multicolored Ramsey number is \( r(3,3,3)=17\) (see [4]). For \( r(3,3,3,3) \), the upper bound of \( 64\) was established by SanchezFlores [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 multicolored Ramsey numbers are related as follows (as a generalization of Equation (2) from this problem):
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}_{k1}) 1)
& \leq& k! (\frac 1 {k!}+ \frac 1{(k1)!} + \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 sumfree 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\) sumfree sets. It can be shown [2] that, for \( k \geq l\),
Using a result of Exoo [3] giving \( s_5 \geq 160\), this implies
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), 317321.

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

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), 17.

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. SanchezFlores,
An improved bound for Ramsey number
\( N(3,3,3,3;2)\),
Discrete Math. 140 (1995), 281286.
