A combinatorial distinction between the Euclidean and projective planes (Q793745)

The authors show that for any \(\epsilon>0\) there exist constants c and \(n_ 0\) so that if P is any set of \(n\geq n_ 0\) points in the Euclidean plane then the number of lines each containing at least \(\delta n^{1/2}\) points of P is less than \(cn^{1/2}\). (This answers an old problem of P. Erdős.) This result is best possible! Indeed, for the points (i,j) with integer coordinates \(1\leq i,j\leq n^{1/2}\) there are at least \(2n^{1/2}\) such lines (i.e., each containing at least \(n^{1/2}\) of the points). The proof requires the creation of a covering lemma for points in the plane and an application of the first author's regularity lemma [Problèmes combinatoires et théorie des graphes, Orsay 1976, Colloq. Int. CNRS, No.260, 399-402 (1978; Zbl 0413.05055)]. These two lemmas are significant developments in combinatorial geometry!