Problem Statement
For any fixed $k\geq 3$,\[R(k,n) \gg \frac{n^{k-1}}{(\log n)^c}\]for some constant $c=c(k)>0$.
Categories:
Graph Theory Ramsey Theory
Progress
Spencer [Sp77] proved this for $k=3$ and Mattheus and Verstraete [MaVe23] proved this for $k=4$.The best general bounds available are\[\frac{n^{\frac{k+1}{2}}}{(\log n)^{\frac{1}{k-2}-\frac{k+1}{2}}}\ll_k R(k,n) \ll_k \frac{n^{k-1}}{(\log n)^{k-2}}.\]The lower bound was proved by Bohman and Keevash [BoKe10]. The upper bound was proved by Ajtai, Komlós, and Szemerédi [AKS80]. Li, Rousseau, and Zang [LRZ01] have shown that $\ll_k$ in the upper bound can be improved to $\leq (1+o(1))$.
The special case $k=3$ is the topic of [165] and $k=4$ is the topic of [166].
This problem is #6 in Ramsey Theory in the graphs problem collection.
See also [920].
Source: erdosproblems.com/986 | Last verified: January 19, 2026