Erdős Problem #588

declared status 'open'. Formalized: no. 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$? Current best: 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\"{u}nbaum, and Sloane [BGS74] and F\"{u}redi and Pal\'{a}sti [FuPa84] for constructions which show that $f_3(n)\geq(1/6+o(1))n^2$.) For $k\geq 4$, K\'{a}rteszi [Ka63] proved$$f_k(n)\gg_k n\log n$$(resolving a conjecture of Erd\H{o}s that $f_k(n)/n\to \infty$). Prize: $100. OEIS: A006065, A008997. Tags: geometry.

Notation is rendered from the stored source. The pinned checkout remains the exact record.