Problem 607

../

claims/: The 1 claim page of Problem 607, one per claimant's result; the problem's standing derives from them.

---

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

Status. Proved, by Szemerédi and Trotter [SzTr83], whom the site credits; the accepted claim is Szemerédi–Trotter 1983.

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

References.

• [SzTr83] Szemerédi, Endre and Trotter, Jr., William T., Extremal problems in discrete geometry. Combinatorica (1983), 381-392.

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.

• szemeredi_1983_extremal_problems_discrete_geometry