Problem Statement
Let $r,k\geq 2$ be fixed. Let $A\subset \mathbb{R}^2$ be a set of $n$ points with no $k$ points on a line. Determine the threshold $f_{r,k}(n)$ such that if there are at least $f_{r,k}(n)$ many ordinary lines (lines containing exactly two points) then there is a set $A'\subseteq A$ of $r$ points such that all $\binom{r}{2}$ many lines determined by $A'$ are ordinary.
Is it true that $f_{r,k}(n)=o(n^2)$, or perhaps even $\ll n$?
Is it true that $f_{r,k}(n)=o(n^2)$, or perhaps even $\ll n$?
Categories:
Geometry
Progress
Turán's theorem implies\[f_{r,k}(n) \leq \left(1-\frac{1}{r-1}\right)\frac{n^2}{2}+1.\]See also [209].Source: erdosproblems.com/960 | Last verified: January 19, 2026