OPEN - $100
Give a constructive proof that $R(k)>C^k$ for some constant $C>1$.
Erdős gave a simple probabilistic proof that $R(k) \gg k2^{k/2}$.
Equivalently, this question asks for an explicit construction of a graph on $n$ vertices which does not contain any clique or independent set of size $\geq c\log n$ for some constant $c>0$. Cohen
[Co15] (see the introduction for further history) constructed a graph on $n$ vertices which does not contain any clique or independent set of size
\[\geq 2^{(\log\log n)^{C}}\]
for some constant $C>0$. Li
[Li23b] has recently improved this to
\[\geq (\log n)^{C}\]
for some constant $C>0$.
This problem is #4 in Ramsey Theory in the graphs problem collection.