\(r(3, 3, n)\) is much larger than \(r(3, n)\)

Home
Search
Subjects

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 multi-Ramsey 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].

Bibliography
1	P. Erdös and V. T. Sós. Problems and results on Ramsey-Turá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. 17-23, Utilitas Math., Winnipeg, Man., 1980.
1	N. Alon and V. Rodl. Sharp bounds for some multicolor Ramsey numbers, Combinatorica, 25 2005, 125-141.