The Szemerédi–Trotter theorem is a mathematical result in the field of Discrete geometry.
It asserts that given n points and m lines in the Euclidean plane, the number of incidences (i.e., the number of point-line pairs, such that the point lies on the line) is
This bound cannot be improved, except in terms of the implicit constants in its big O notation.
The original proof of Endre Szemerédi and William T. Trotter was somewhat complicated, using a combinatorial technique known as cell decomposition.
[1][2] Later, László Székely discovered a much simpler proof using the crossing number inequality for graphs.
[4] Subsequent research has lowered the constant, coming from the crossing lemma, from 2.5 to 2.44.
[5] On the other hand, this bound would not remain valid if one replaces the coefficient 2.44 with 0.42.
[6] The Szemerédi–Trotter theorem has a number of consequences, including Beck's theorem in incidence geometry and the Erdős-Szemerédi sum-product problem in additive combinatorics.
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 if e denotes the number of such line segments, it will suffice to show that
Now consider the graph formed by using the n points as vertices, and the e line segments as edges.
In either case e ≤ 3.24(nm)2/3 + 7.5n, giving the desired bound 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
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
Equivalently, the number of hyperplanes in H containing k or more points is bounded above by
A construction due to Edelsbrunner shows this bound to be asymptotically optimal.
[9] 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".
rely in a crucial way on the topology of Euclidean space, so do not extend easily to other fields.
Tóth successfully generalized the original proof of Szemerédi and Trotter to the complex plane
When the point set is a Cartesian product, Solymosi and Tardos show that the Szemerédi-Trotter bound holds using a much simpler argument.
A Szemerédi-Trotter bound is impossible in general due to the following example, stated here in
This example shows that the trivial, combinatorial incidence bound is tight.
Incidence bounds over finite fields are of two types: (i) when at least one of the set of points or lines is `large' in terms of the characteristic of the field; (ii) both the set of points and the set of lines are `small' in terms of the characteristic.
Stevens and de Zeeuw[16] show that the number of incidences between
If the point set is a Cartesian Product, then they show an improved incidence bound: let
Note that by point-line duality in the plane, this incidence bound can be rephrased for an arbitrary point set and a set of lines having a Cartesian product structure.
In both the reals and arbitrary fields, Rudnev and Shkredov[17] show an incidence bound for when both the point set and the line set has a Cartesian product structure.