Logo
All Random Solved Random Open
OPEN - $100
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$?
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 [Ka] proved \[f_k(n)\gg_k n\log n.\] 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})}\]