$\newcommand{\N}{\mathbb{N}}\newcommand{\Z}{\mathbb{Z}}\newcommand{\R}{\mathbb{R}}\DeclareMathOperator{\E}{E}$

$\newcommand{\S}{\mathcal{S}}$This is a famous open problem, due to Erdős and certainly very hard. I’ve played around with some probabilistic arguments but gotten nowhere further than the simple lower bounds.

For each $r\in\N$, let $\S_r$ denote the class of point sets in $\R^2$ with no $r$ points on a line and let \[ f(n) = \min_{S\in\S_4}\max_{R\in\S_3}|R\cap S| \enspace . \]

Determine the asymptotic behaviour of $f(n)$.

There are several easy proofs that $f(n)\in\Omega(\sqrt{n})$, that is, every $n$ point set with no four points collinear contains a subset of size $\Omega(\sqrt{n})$ in general position. Füredi upped this bound to $\Omega(\sqrt{n\log n})$ and showed a lower bound of $o(n)$. The best upper bound currently is $O(n/\sqrt{\log^* n})$, which is also in the same paper of Füredi combined with the best version of the Hales-Jewett Theorem.

Pór and Wood’s expository paper contains many generalizations and open problems. The recent paper by Cardinal, Toth, and Wood has some extensions to higher dimensions.