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.