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

Problem statement
---------------
Give an asymptotic formula for $R(3,k)$.

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)
----------------------------------------
- It is known that there exists some constant $c>0$ such that for large
  $k$\[(c+o(1))\frac{k^2}{\log k}\leq R(3,k) \leq (1+o(1))\frac{k^2}{\log
  k}.\]The lower bound is due to Kim, the upper bound is due to Shearer,
  improving an earlier bound of Ajtai, Koml\'{o}s, and Szemer\'{e}di.
- The value of $c$ in the lower bound has seen a number of improvements.
- Kim's original proof gave $c\geq 1/162$.
- The bound $c\geq 1/4$ was proved independently by Bohman and Keevash and
  Pontiveros, Griffiths and Morris.