Szemerédi–Trotter theorem

We may discard the lines which contain two or fewer of the points, as they can contribute at most 2m incidences to the total number. Thus we may assume that every line contains at least three of the points.

If a line contains k points, then it will contain k − 1 line segments which connect two consecutive points along the line. Because k ≥ 3 after discarding the two-point lines, it follows that k − 1 ≥ k/2, so the number of these line segments on each line is at least half the number of incidences on that line. Summing over all of the lines, the number of these line segments is again at least half the total number of incidences. Thus if e denotes the number of such line segments, it will suffice to show that

${\displaystyle e=O\left(n^{\frac {2}{3}}m^{\frac {2}{3}}+n+m\right).}$

Now consider the graph formed by using the n points as vertices, and the e line segments as edges. Since each line segment lies on one of m lines, and any two lines intersect in at most one point, the crossing number of this graph is at most the number of points where two lines intersect, which is at most m(m − 1)/2. The crossing number inequality implies that either e ≤ 7.5n, or that m(m − 1)/2 ≥ e³ / 33.75n². In either case e ≤ 3.24(nm)^2/3 + 7.5n, giving the desired bound

${\displaystyle e=O\left(n^{\frac {2}{3}}m^{\frac {2}{3}}+n+m\right).}$

Since every pair of points can be connected by at most one line, there can be at most n(n − 1)/2 lines which can connect at k or more points, since k ≥ 2. This bound will prove the theorem when k is small (e.g. if k ≤ C for some absolute constant C). Thus, we need only consider the case when k is large, say k ≥ C.

Suppose that there are m lines that each contain at least k points. These lines generate at least mk incidences, and so by the first formulation of the Szemerédi–Trotter theorem, we have

${\displaystyle mk=O\left(n^{\frac {2}{3}}m^{\frac {2}{3}}+n+m\right),}$

and so at least one of the statements ${\displaystyle mk=O(n^{2/3}m^{2/3}),mk=O(n)}$, or ${\displaystyle mk=O(m)}$ is true. The third possibility is ruled out since k was assumed to be large, so we are left with the first two. But in either of these two cases, some elementary algebra will give the bound ${\displaystyle m=O(n^{2}/k^{3}+n/k)}$ as desired.

Except for its constant, the Szemerédi–Trotter incidence bound cannot be improved. To see this, consider for any positive integer N ∈ Z⁺ a set of points on the integer lattice

${\displaystyle P=\left\{(a,b)\in \mathbf {Z} ^{2}\$ :\ 1\leq a\leq N;1\leq b\leq 2N^{2}\right\},}

and a set of lines

${\displaystyle L=\left\{(x,mx+b)\$ :\ m,b\in \mathbf {Z} ;1\leq m\leq N;1\leq b\leq N^{2}\right\}.}

Clearly, ${\displaystyle |P|=2N^{3}}$ and ${\displaystyle |L|=N^{3}}$. Since each line is incident to N points (i.e., once for each ${\displaystyle x\in \{1,\cdots ,N\}}$), the number of incidences is ${\displaystyle N^{4}}$ which matches the upper bound.[6]

One generalization of this result to arbitrary dimension, R^d, was found by Agarwal and Aronov.[7] Given a set of n points, S, and the set of m hyperplanes, H, which are each spanned by S, the number of incidences between S and H is bounded above by

${\displaystyle O\left(m^{\frac {2}{3}}n^{\frac {d}{3}}+n^{d-1}\right).}$

Equivalently, the number of hyperplanes in H containing k or more points is bounded above by

${\displaystyle O\left({\frac {n^{d}}{k^{3}}}+{\frac {n^{d-1}}{k}}\right).}$

A construction due to Edelsbrunner shows this bound to be asymptotically optimal.[8]

József Solymosi and Terence Tao obtained near sharp upper bounds for the number of incidences between points and algebraic varieties in higher dimensions, when the points and varieties satisfy "certain pseudo-line type axioms". Their proof uses the Polynomial Ham Sandwich Theorem.[9]

There has been some interest in proving analogs to the Szemerédi–Trotter theorem in planes over fields other than R. All known proofs of the Szemerédi–Trotter theorem over R rely in a crucial way on the topology of Euclidean space, so do not extend easily to other fields. Nevertheless, the following results have been obtained:

• Tóth successfully generalized the original proof of Szemerédi and Trotter to the complex plane C² by introducing additional ideas.[10] This result was also obtained independently and through a different method by Zahl.[11]