Problem #558: Let $R(G;k)$ denote the minimal $m$ such that if the edges...

---

Progress

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.\]This problem is #27 in Ramsey Theory in the graphs problem collection.