Problem #78: Give a constructive proof that $R(k)>C^k$ for some constant...

---

Progress

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$.

In [Er69b] Erdős asks for even a construction whose largest clique or independent set has size $o(n^{1/2})$, which is now known.

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.