Logo
All Random Solved Random Open
OPEN
Let $R(G;k)$ denote the minimal $m$ such that if the edges of $K_m$ are $k$-coloured then there is a monochromatic copy of $G$. Determine \[R(K_{s,t};k)\] where $K_{s,t}$ is the complete bipartite graph with $s$ vertices in one component and $t$ in the other.
Chung and Graham [ChGr75] prove the bounds \[(2\pi\sqrt{st})^{\frac{1}{s+t}}\left(\frac{s+t}{e^2}\right)k^{\frac{st-1}{s+t}}\leq R(K_{s,t};k)\leq (t-1)(k+k^{1/s})^s.\] For example this implies that \[R(K_{3,3};k) \ll k^3.\] Using Turán numbers one can show that \[R(K_{3,3};k) \gg \frac{k^3}{(\log k)^3}.\]

See also the entry in the graphs problem collection.