\(r(3, 3, n)\) is much larger than \(r(3, n)\)
Home
Search
Subjects
About Erdös
About This Site
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})\).
A conjecture on the ratio of multiRamsey numbers and Ramsey numbers (Proposed by Erdös and Sós [1])
\[ \frac{r(3,3,n)}{r(3,n)} \rightarrow \infty \] as \(n \rightarrow \infty\).Erdös [1]said, "It is very surprising that this problem which seems trivial at first sight should cause serious difficulties. We further expect that
\(\displaystyle \frac{r(3,3,n)}{n^2} \rightarrow \infty \)
as
\( n \rightarrow \infty\)
and perhaps
\(\displaystyle r(3,3,n) > n^{3\epsilon} \)
for every
\( \epsilon>0\) if \( n\) is sufficiently large."
In 2002, this conjecture was proven by Alon and Rodl [2].
P>
Bibliography  

1  P. Erdös and V. T. Sós. Problems and results on RamseyTurán type theorems (preliminary report), Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (Humboldt State Univ., Arcata, Calif., 1979), Congress. Numer. XXVI, pp. 1723, Utilitas Math., Winnipeg, Man., 1980.

1  N. Alon and V. Rodl. Sharp bounds for some multicolor Ramsey numbers, Combinatorica, 25 2005, 125141.
