Problem 159

Erdős Problem #159: declared status 'open'. Formalized: no. There exists some constant $c>0$ such that $$R(C_4,K_n) \ll n^{2-c}.$$ Current best: The current bounds are$$\frac{n^{3/2}}{(\log n)^{3/2}}\ll R(C_4,K_n)\ll \frac{n^2}{(\log n)^2}.$$The upper bound is due to Szemer\'{e}di (mentioned in [EFRS78]), and the lower bound is due to Spencer [Sp77]. [Sp77] Spencer, J., Asymptotic lower bounds for Ramsey functions. Prize: no. Tags: graph theory, ramsey theory.