Problem 87

Erdős Problem #87: declared status 'open'. Formalized: no. Let $\epsilon >0$. Is it true that, if $k$ is sufficiently large, then$$R(G)>(1-\epsilon)^kR(k)$$for every graph $G$ with chromatic number $\chi(G)=k$? Even stronger, is there some $c>0$ such that, for all large $k$, $R(G)>cR(k)$ for every graph $G$ with chromatic number $\chi(G)=k$? Current best: Since $R(k)\leq 4^k$ this is trivial for $\epsilon\geq 3/4$. Yuval Wigderson points out that $R(G)\gg 2^{k/2}$ for any $G$ with chromatic number $k$ (via a random colouring), which asymptotically matches the best-known lower bounds for $R(k)$. Prize: no. OEIS: A059442. Tags: graph theory, ramsey theory.