Szemerédi–Trotter theorem

Remarks

Székely gave a short proof with the crossing number inequality. Draw a graph whose vertices are the points and whose edges join consecutive points on each line. It has at least $I - \abs{L}$ edges and at most $\abs{L}^2$ crossings, and the crossing number inequality gives the bound. The bound is sharp up to the constant. Take the grid $\set{1, \dots, k} \times \set{1, \dots, 2k^2}$ and the lines $y = ax + b$ with $1 \le a \le k$ and $1 \le b \le k^2$. Each such line meets the grid in $k$ points, so there are $k^4$ incidences, with $2k^3$ points and $k^3$ lines. The theorem fails over finite fields. In $\F_q^2$, the $q^2$ points and the $q^2 + q$ lines have $q^3 + q^2$ incidences, which is more than a constant times $q^{8/3}$ for large $q$.

Going deeper

For a student

The Szemerédi–Trotter theorem is the basic result of incidence geometry. A corollary: $n$ points determine at most $O(n^2/k^3 + n/k)$ lines that contain at least $k$ of the points. It has applications to the Erdős distinct distances problem and to sum-product estimates in additive combinatorics. Its proof uses the topology of the real plane, which explains why it fails over finite fields.