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
O ( n 2 / 3 m 2 / 3 + n + m ) . {\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
O ( n 2 k 3 + n k ) . {\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 2.5 n 2 / 3 m 2 / 3 + n + m {\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.
Proof of the first formulation 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
e = O ( n 2 / 3 m 2 / 3 + n + m ) . {\displaystyle e=O\left(n^{2/3}m^{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 ≥ e3 / 33.75n2. In either case e ≤ 3.24(nm)2/3 + 7.5n, giving the desired bound
e = O ( n 2 / 3 m 2 / 3 + n + m ) . {\displaystyle e=O\left(n^{2/3}m^{2/3}+n+m\right).}
Proof of the second formulation 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
m k = O ( n 2 / 3 m 2 / 3 + n + m ) , {\displaystyle mk=O\left(n^{2/3}m^{2/3}+n+m\right),}
… excerpt ends here. Continue reading the full article.
