Problem #165: Give an asymptotic formula for $R(3,k)$

---

Progress

It is known that there exists some constant $c>0$ such that for large $k$\[(c+o(1))\frac{k^2}{\log k}\leq R(3,k) \leq (1+o(1))\frac{k^2}{\log k}.\]The lower bound is due to Kim [Ki95], the upper bound is due to Shearer [Sh83], improving an earlier bound of Ajtai, Komlós, and Szemerédi [AKS80].

The value of $c$ in the lower bound has seen a number of improvements. Kim's original proof gave $c\geq 1/162$. The bound $c\geq 1/4$ was proved independently by Bohman and Keevash [BoKe21] and Pontiveros, Griffiths and Morris [PGM20]. The latter collection of authors conjecture that this lower bound is the true order of magnitude.

This was, however, improved by Campos, Jenssen, Michelen, and Sahasrabudhe [CJMS25] to $c\geq 1/3$, and further by Hefty, Horn, King, and Pfender [HHKP25] to $c\geq 1/2$. Both of these papers conjecture that $c=1/2$ is the correct asymptotic.

See also [544], and [986] for the general case. See [1013] for a related function.