Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 8

Problem 588

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$ ?

Status. Open.

Source. erdosproblems.com/588, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #588, https://www.erdosproblems.com/588.

References.

[BGS74] Burr, Stefan A. and Grünbaum, Branko and Sloane, N. J. A., The orchard problem. Geometriae Dedicata (1974), 397-424.
[FuPa84] Füredi, Z. and Palásti, I., Arrangements of lines with a large number of triangles. Proc. Amer. Math. Soc. (1984), 561-566.
[Gr76] Grünbaum, Branko, New views on some old questions of combinatorial geometry. Colloquio Internazionale sulle Teorie Combinatorie (Roma, 1973), Tomo I (1976), 451-468.
[Ka63] F. Kárteszi, Sylvester egy tételéről és Erdős egy sejtéséről. Matematikai Lapok (1963), 3-10.
[SoSt13] Solymosi, József and Stojaković, Miloš, Many collinear $k$ -tuples with no $k+1$ collinear points. Discrete Comput. Geom. (2013), 811-820.

Formalization. None recorded.

Progress

Not yet compiled.

Known Results

Not yet compiled.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (7)

Discrete and Convex Geometry discrete_geometry/burr_1974_orchard_problem Theorem 1 (p. 397): t(p) >= 1 + floor(p(p-3)/6) for every p >= 3, by points on a cubic curve discrete_geometry/erdos_1984_research_problems Conjecture (1) (p. 101): f_k(n)/n tends to infinity and f_k(n)/n^2 tends to 0 for fixed k > 3 discrete_geometry/solymosi_2013_many_collinear_k_tuples Theorem 1 (p. 3): more than n^(2 - c/sqrt(log n)) lines with exactly k points and none with k+1

Graph