Problem 558

Erdős Problem #558: declared status 'open'. Formalized: no. 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. Current best: 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\'{o}nyai, and Szab\'{o} [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.$$This problem is #27 in Ramsey Theory in the graphs problem collection. Prize: no. Tags: graph theory, ramsey theory.