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

Problem statement
---------------
Let $f(n)$ be minimal such that any $f(n)$ points in $\mathbb{R}^2$, no three on a line, contain $n$ points which form the vertices of a convex $n$-gon. Prove that $f(n)=2^{n-2}+1$.

Picture
-------
Many points on a line:

o---o---o---o---o
\
 o   o      o

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

Context
-------
Area hint: incidence geometry / combinatorial geometry.

Benchmarks / known results (from comments)
----------------------------------------
- The problem originated in 1931 when Klein observed that $f(4)=5$.
- Tur\'{a}n and Makai showed $f(5)=9$.
- Erd\H{o}s and Szekeres proved the bounds\[2^{n-2}+1\leq f(n)\leq
  \binom{2n-4}{n-2}+1.\]( and respectively).
- There were several improvements of the upper bound, but all of the form
  $4^{(1+o(1))n}$, until Suk proved\[f(n) \leq 2^{(1+o(1))n}.\]The current
  best bound is due to Holmsen, Mojarrad, Pach, and Tardos, who prove\[f(n)
  \leq 2^{n+O(\sqrt{n\log n})}.\]In Erd\H{o}s clarifies that the \$500 is for
  a proof, and only offers \$100 for a disproof.