Erdős Problems

Tags Prizes

SOLVED

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.

#733: [Er81]

combinatorics, geometry

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].