# Multi-color Ramsey number for even cycles

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.

# A multi-colored Ramsey problem for even cycles (proposed by Erdös and Graham [2])

Determine $$r(\underbrace{C_{2m}, \ldots, C_{2m}}_k)$$.

It was proved [1] that
\begin{eqnarray*} r(\underbrace{C_4, \ldots, C_4}_k)& \leq& k^2 + k +1 \mbox{~~~for all $$k$$}
r(\underbrace{C_4, \ldots, C_4}_k)& >& k^2 - k +1 \mbox{~~~for prime power $$k$$}. \end{eqnarray*}

The following upper and lower bounds for $$r(\underbrace{C_{2m}, \ldots, C_{2m}}_k)$$ were given in [2]:

$$\displaystyle c k^{1+1/2m} \leq r(\underbrace{C_{2m}, \ldots, C_{2m}}_k) \leq c' k^{1+1/(m-1)}.$$

The lower bound can be further improved by using results in [3]:

$$\displaystyle r(\underbrace{C_{2m}, \ldots, C_{2m}}_k) \geq c'' (\frac k {\log k})^{1+ 2/(3m-5)}.$$

Bibliography
1 F. R. K. Chung and R. L. Graham. On multicolor Ramsey numbers for complete bipartite graphs, J. Comb. Th. (B) 18 (1975), 164-69.

2 P. Erdös, Some new problems and results in graph theory and other branches of combinatorial mathematics, Combinatorics and graph theory (Calcutta, 1980), Lecture Notes in Math., 885, 9-17, Springer, Berlin-New York, 1981.

3 F. Lazebnik, V. A. Ustimenko and A. J. Woldar, A new series of dense graphs of high girth, Bull. Amer. Math. Soc. 32 (1995), 73-79.