---

Source. Problem 36, pp. 102--103, of P. Erdős, Research problems, Period. Math. Hungar. 15 (1984), no. 1, 101--103, doi:10.1007/BF02109375. The edition read is named on the source card.

Statement

Setting (p. 101). $X_n$ is a set of $n$ points in the plane; property $P_k$ means that no line contains more than $k$ of its points (conjecture (1)).

Theorem (pp. 102--103, quoted). "I conjectured and Beck proved$^{1}$ [1] that there is an absolute constant $c$ so that if $X_n$ has property $P_{n-k}$ then $X_n$ determines at least $ckn$ distinct lines (here we only assume $2\le k\le n$)."

In words: at most $n-k$ of the $n$ points lie on any one line, and the points determine at least $ckn$ lines, with $c>0$ not depending on $n$ or $k$. The range $2\le k\le n$ is the print's.

Footnote 1 (p. 102). The conjecture is also a consequence of the results of Szemerédi and Trotter.

Exact count (p. 103). Erdős adds that Kelly and Moser obtained the exact number of these lines when $3k^2<n$.

Proof pointer

The note gives no proof; it cites J. Beck, The lattice property of the plane and some problems of Dirac, Motzkin and Erdős in combinatorial geometry, Combinatorica 3 (1983), 281--297, and, for the footnote, Szemerédi and Trotter, Combinatorica 3 (1983), 381--392. Erdős's comments on the size of $c$ are on conjecture_p103.

Read depth

Claims checked: the statement, the footnote and the sentence on Kelly and Moser were read clause by clause on the page images of pp. 102--103. The cited proofs were not read here. Nothing here is independently reviewed.

Dependencies

• Beck's paper, which the library does not hold.
• Szemerédi and Trotter, Extremal problems in discrete geometry (card szemeredi_1983_extremal_problems_discrete_geometry).
• Kelly and Moser, On the number of ordinary lines determined by n points (card kelly_1958_number_ordinary_lines_determined_points).

Bears on

• Problem 211: the problem asks whether, for $1\le k<n$, $n$ points with at most $n-k$ on a line determine $\gg kn$ lines, which is the statement reported here; the note's range is $2\le k\le n$ instead. The note reports the proofs of Beck and of Szemerédi and Trotter and proves nothing itself.