# Multi-color Ramsey number for complete bipartite graphs

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 bipartite graphs (proposed by Chung, Erdös and Graham [1], [2])

Determine $$r(\underbrace{K_{s,t}, \ldots, K_{s,t}}_k)$$.

In [2], the following bounds are given:

$$\displaystyle (2 \pi \sqrt{st})^{1/(s+t)}((s+t)/e^2)k^{(st-1)/(s+t)} \leq r(\underbrace{K_{s,t}, \ldots, K_{s,t}}_k) \leq (t-1)(k+k^{1/s})^s$$

for $$k >1, 2 \leq s \leq t$$.

In particular, it would be of interest to determine $$r(\underbrace{K_{3,3}, \ldots, K_{3,3}}_k)$$.

By using Turán numbers, one can show

$$\displaystyle r(\underbrace{K_{3,3}, \ldots, K_{3,3}}_k) > c \frac{k^3}{ \log^3 k}.$$

Bibliography
1 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.

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