The Szemerédi–Trotter theorem is a mathematical result in the field of combinatorial 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. As for the implicit constants, it was shown by Pach, Radoičić, Tardos and Tóth that the upper bound holds. On the other hand, Pach and Tóth showed that the statement does not hold true if one replaces the coefficient 2.5 with 0.42.
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
The original proof of Endre Szemerédi and William T. Trotter was somewhat complicated, using a combinatorial technique known as cell decomposition. Later, Székely discovered a much simpler proof using the crossing number inequality for graphs. (See below.)
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 of the n points. In particular it will contain at least k/2 such line segments, since we have assumed k ≥ 3. Adding this up over all of the m lines, we see that the number of line segments obtained in this manner is at least half of the total number of incidences. Thus if we let e be 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. Since all of the line segments lie on one of m lines, and any two lines intersect in at most one point, the crossing number of this graph is at most m2. Applying the crossing number inequality we thus conclude that either e ≤ 7.5n, or that m2 ≥ e3 / 33.75n2. In either case e ≤ 3.24(nm)2/3 + 7.5n and we obtain the desired bound
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
and so at least one of the statements , or 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 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
and a set of lines
Clearly, and . Since each line is incident to N points (i.e., once for each ), the number of incidences is which matches the upper bound.
Generalization to Rd
One generalization of this result to arbitrary dimension, Rd, was found by Agarwal and Aronov. 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
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.
Analogs over other fields
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 C2 by introducing additional ideas. This result was also obtained independently and through a different method by Zahl.
- Pach, János; Radoičić, Radoš; Tardos, Gábor; Tóth, Géza (2006). "Improving the Crossing Lemma by Finding More Crossings in Sparse Graphs". Discrete & Computational Geometry. 36 (4): 527–552. doi:10.1007/s00454-006-1264-9.
- Pach, János; Tóth, Géza (1997). "Graphs drawn with few crossings per edge". Combinatorica. 17 (3): 427–439. doi:10.1007/BF01215922.
- Szemerédi, Endre; Trotter, William T. (1983). "Extremal problems in discrete geometry". Combinatorica. 3 (3–4): 381–392. doi:10.1007/BF02579194. MR 0729791.
- Szemerédi, Endre; Trotter, William T. (1983). "A Combinatorial Distinction Between the Euclidean and Projective Planes" (PDF). European Journal of Combinatorics. 4 (4): 385–394. doi:10.1016/S0195-6698(83)80036-5.
- Székely, László A. (1997). "Crossing numbers and hard Erdős problems in discrete geometry". Combinatorics, Probability and Computing. 6 (3): 353–358. doi:10.1017/S0963548397002976. MR 1464571.
- Terence Tao (March 17, 2011). "An incidence theorem in higher dimensions". Retrieved August 26, 2012.
- Agarwal, Pankaj; Aronov, Boris (1992). "Counting facets and incidences". Discrete and Computational Geometry. Springer. 7 (1): 359–369. doi:10.1007/BF02187848.
- Edelsbrunner, Herbert (1987). "6.5 Lower bounds for many cells". Algorithms in Combinatorial Geometry. Springer-Verlag. ISBN 3-540-13722-X.
- Solymosi, J.; Tao, T. (September 2012). "An incidence theorem in higher dimensions". Discrete and Computational Geometry. 48 (2). arXiv: . doi:10.1007/s00454-012-9420-x.
- Tóth, Csaba D. (2015). "The Szemerédi-Trotter Theorem in the Complex Plane". Combinatorica. 35 (1): 95–126. arXiv: . doi:10.1007/s00493-014-2686-2.
- Zahl, Joshua (2015). "A Szemerédi-Trotter Type Theorem in ℝ4". Discrete & Computational Geometry. 54 (3): 513–572. doi:10.1007/s00454-015-9717-7.