# $$r(3, 3, n)$$ is much larger than $$r(3, n)$$

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

P>

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.