Problem Statement
There exists some constant $c>0$ such that
$$R(C_4,K_n) \ll n^{2-c}.$$
$$R(C_4,K_n) \ll n^{2-c}.$$
Categories:
Graph Theory Ramsey Theory
Progress
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édi (mentioned in [EFRS78]), and the lower bound is due to Spencer [Sp77].This problem is #17 in Ramsey Theory in the graphs problem collection.
Source: erdosproblems.com/159 | Last verified: January 13, 2026