Problem Statement
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)$.
Categories:
Geometry
Progress
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]).
Füeredi [Fu91b] proved\[n^{1/2}\log n\ll g(n)=o(n).\]Balogh and Solymosi [BaSo18] improved the upper bound to\[g(n) \ll n^{5/6+o(1)}.\]
Source: erdosproblems.com/589 | Last verified: January 15, 2026