Erdős Problems

Tags Prizes

SOLVED - $250

For a set of $n$ points $P\subset \mathbb{R}^2$ let $\ell_1,\ldots,\ell_m$ be the lines determined by $P$, and let $A=\{\lvert \ell_1\cap P\rvert,\ldots,\lvert \ell_m\cap P\rvert\}$.

Let $F(n)$ count the number of possible sets $A$ that can be constructed this way. Is it true that \[F(n) \leq \exp(O(\sqrt{n}))?\]

#607: [Er85]

geometry

Erdős writes it is 'easy to see' that this bound would be best possible. This was proved by Szemerédi and Trotter [SzTr83].

Additional thanks to: Noga Alon