Problem 165

Erdős Problem #165: declared status 'open'. Formalized: no. Give an asymptotic formula for $R(3,k)$. Current best: 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\'{o}s, and Szemer\'{e}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]. Prize: $250. OEIS: A000791. Tags: graph theory, ramsey theory.