Problem 78 — Visual explainer (undergrad)
=========================================

Problem statement
---------------
Let $R(k)$ be the Ramsey number for $K_k$, the minimal $n$ such that every $2$-colouring of the edges of $K_n$ contains a monochromatic copy of $K_k$.

Give a constructive proof that $R(k)>C^k$ for some constant $C>1$.

Picture
-------
[Given objects + constraints]  --->  [Count / structure]  --->  [Show bound / existence]

Conjecture / Task: what to look at
------------------------
- Restate the problem as: given the constraint, what asymptotic bound or
  structure must follow?
- Use the comments as benchmarks (best known bounds / constructions).

Benchmarks / known results (from comments)
----------------------------------------
- Erd\H{o}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 Erd\H{o}s asks for even a construction whose largest clique or
  independent set has size $o(n^{1/2})$, which is now known.
- Cohen (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$.