Erdős Problem #986

declared status 'open'. Formalized: no. For any fixed $k\geq 3$,$$R(k,n) \gg \frac{n^{k-1}}{(\log n)^c}$$for some constant $c=c(k)>0$. Current best: 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\'{o}s, and Szemer\'{e}di [AKS80]. Li, Rousseau, and Zang [LRZ01] have shown that $\ll_k$ in the upper bound can be improved to $\leq (1+o(1))$. and Zang, Wenan, Asymptotic upper bounds for {R}amsey functions. Prize: no. OEIS: A000791, A059442. Tags: graph theory, ramsey theory.

Notation is rendered from the stored source. The pinned checkout remains the exact record.