Problem Statement
Let $f_k(n)$ be minimal such that if $n$ points in $\mathbb{R}^2$ have no $k+1$ points on a line then there must be at most $f_k(n)$ many lines containing at least $k$ points. Is it true that\[f_k(n)=o(n^2)\]for $k\geq 4$?
Categories:
Geometry
Progress
A generalisation of [101] (which asks about $k=4$).The restriction to $k\geq 4$ is necessary since Sylvester has shown that $f_3(n)= n^2/6+O(n)$. (See also Burr, Grünbaum, and Sloane [BGS74] and Füredi and Palásti [FuPa84] for constructions which show that $f_3(n)\geq(1/6+o(1))n^2$.)
For $k\geq 4$, Kárteszi [Ka63] proved\[f_k(n)\gg_k n\log n\](resolving a conjecture of Erdős that $f_k(n)/n\to \infty$). Grünbaum [Gr76] proved\[f_k(n) \gg_k n^{1+\frac{1}{k-2}}.\]Erdős speculated this may be the correct order of magnitude, but Solymosi and Stojaković [SoSt13] give a construction which shows\[f_k(n)\gg_k n^{2-O_k(1/\sqrt{\log n})}\]
Source: erdosproblems.com/588 | Last verified: January 15, 2026