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 general 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\] and determined \[R(K_{2,2},k)=(1+o(1))k^2.\] Alon, Rónyai, and Szabó [ARS99] have proved that \[R(K_{3,3},k)=(1+o(1))k^3\] and that if $s\geq (t-1)!+1$ then \[R(K_{s,t},k)\asymp k^t.\]

See also the entry in the graphs problem collection.

Additional thanks to: Noga Alon