Szemerédi–Trotter theorem

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

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

This bound cannot be improved, except in terms of the implicit constants in its big O notation. An equivalent formulation of the theorem is the following. Given n points and an integer k ≥ 2, the number of lines which pass through at least k of the points is

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

The original proof of Endre Szemerédi and William T. Trotter was somewhat complicated, using a combinatorial technique known as cell decomposition. Later, László Székely discovered a much simpler proof using the crossing number inequality for graphs. This method has been used to produce the explicit upper bound ${\displaystyle 2.5n^{2/3}m^{2/3}+n+m}$ on the number of incidences. Subsequent research has lowered the constant, coming from the crossing lemma, from 2.5 to 2.44. On the other hand, this bound would not remain valid if one replaces the coefficient 2.44 with 0.42.

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.