Logo
All Random Solved Random Open
OPEN
Let $g(n)$ be maximal such that in any set of $n$ points in $\mathbb{R}^2$ with no four points on a line there exists a subset on $g(n)$ points with no three points on a line. Estimate $g(n)$.
The trivial greedy algorithm gives $g(n)\gg n^{1/2}$. A similar question can be asked for a set with no $k$ points on a line, searching for a subset with no $l$ points on a line, for any $3\leq l<k$.

Erdős thought that $g(n) \gg n$, but in fact $g(n)=o(n)$, which follows from the density Hales-Jewett theorem proved by Furstenberg and Katznelson [FuKa91] (see [185]).

Additional thanks to: Zach Hunter