Sets of Rich Lines in General Position

Abstract

Given a set of $n$ points in $R^2$, the Szemerédi-Trotter theorem establishes that the number of lines which can be incident to at least $k>1$ of these points is $O(n^2/k^3+n/k)$. J.\ Solymosi conjectured that if one requires the points to be in a grid formation and the lines to be in general position---no two parallel, no three meeting at a point---then one can get a much tighter bound. We prove: for every $\epsilon >0$ there exists some $\delta >0$ such that for sufficiently large values of $n$, every set of lines in general position, each intersecting an $n\times n$ grid of points in at least $n^{1-\delta }$ places, has size at most $n^{\epsilon }$.

A few corrections; some material added at the end. Submitted