Problem Statement
Call a sequence $1<X_1\leq\cdots X_m\leq n$ line-compatible if there is a set of $n$ points in $\mathbb{R}^2$ such that there are $m$ lines $\ell_1,\ldots,\ell_m$ containing at least two points, and the number of points on $\ell_i$ is exactly $X_i$.
Prove that there are at most\[\exp(O(n^{1/2}))\]many line-compatible sequences.
Prove that there are at most\[\exp(O(n^{1/2}))\]many line-compatible sequences.
Categories:
Combinatorics Geometry
Progress
This problem is essentially the same as [607], but with multiplicities.Erdős writes that it is 'easy' to prove there are at least\[\exp(cn^{1/2})\]many such sequences for some constant $c>0$, but expected proving the upper bound to be difficult. Once it is done, he asked for the existence and value of\[\lim_{n\to \infty}\frac{\log f(n)}{n^{1/2}},\]where $f(n)$ counts the number of line-compatible sequences.
This is true, and was proved by Szemerédi and Trotter [SzTr83].
See also [732].
Source: erdosproblems.com/733 | Last verified: January 16, 2026