Problem Statement
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}))?\]
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}))?\]
Categories:
Geometry
Progress
Erdős writes it is 'easy to see' that this bound would be best possible. This was proved by Szemerédi and Trotter [SzTr83].Source: erdosproblems.com/607 | Last verified: January 15, 2026