Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


The result credited here is a consequence of the paper's incidence bounds, drawn by Erdős (1984) and by the site, not a theorem the paper states. Szemerédi and Trotter prove that nn points and tt lines in the real plane have at most c1n2/3t2/3c_1n^{2/3}t^{2/3} incidences when n≤t≤(n2)\sqrt n\le t\le\binom n2, and deduce that fewer than c2n2/k3c_2n^2/k^3 lines carry at least kk of nn points when 2≤k≤n2\le k\le\sqrt n. From these bounds it follows that nn points with at most n−kn-k of them on any line determine ≫kn\gg kn distinct lines, the statement of Problem 211. The paper does not state that consequence as a numbered theorem; the source card [[../library/discrete_geometry/szemeredi_1983_extremal_problems_discrete_geometry/_index|records its Theorems 1 through 4]], and Erdős's 1984 problem note, whose card [[../library/discrete_geometry/erdos_1984_research_problems/_index|records the footnote]], states that his conjecture is also a consequence of the Szemerédi-Trotter results. The same statement was proved directly by Beck in the same issue of the journal.

The refereed evidence covers the premises, Theorems 1 and 2 of Endre Szemerédi and William T. Trotter, Jr., Extremal problems in discrete geometry, Combinatorica 3 (1983), no. 3-4, 381-392; the deduction of the ≫kn\gg kn bound rests on the curator's credit and on Erdős's note. The site's curator, T. F. Bloom, marks the problem proved and credits this paper beside Beck's, and Erdős records the deduction in his 1984 note.