Szemerédi–Trotter theorem

In mathematics, the Szemerédi–Trotter theorem is a result in the field of combinatorial geometry. It asserts that given "n" points and "m" lines in the 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\; )$, which is a bound that cannot be improved, except in terms of the implicit constants.

An equivalent formulation of the theorem is the following. Given "n" points and an integer "k" > 2, the number of lineswhich pass through at least "k" of the points is

:$O(\; n^2\; /\; k^3\; +\; n/k).,$

The original proof of Szemerédi and Trottercite journal| last=Szemerédi | first=Endre | authorlink=Endre Szemerédi | coauthors=William T. Trotter | year=1983 | title=Extremal problems in discrete geometry | journal=Combinatorica | volume=3 | issues=3–4 | doi=10.1007/BF02579194 | pages=381–392] was somewhat complicated, using a combinatorial technique known as "cell decomposition". Later, Szekély discovered a much simpler proof using crossing numbers of graphs.cite journal| last=Székely | first=László A. | year=1997 | title=Crossing numbers and hard Erdős problems in discrete geometry | journal=Combinatorics, Probability and Computing | volume=6 | issue=3 | pages=353–358 | url=http://journals.cambridge.org/action/displayAbstract?aid=46513 | doi=10.1017/S0963548397002976] (See below.)

The Szemerédi–Trotter theorem has a number of consequences, including Beck's theorem in incidence geometry.

Proof of the first formulation

We may discard the lines which contain two or fewer of the points, as they can contribute at most 2"m" incidences tothe 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 ofthe "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 leasthalf of the total number of incidences. Thus if we let "e" be the number of such line segments, it will suffice toshow that $e\; =\; O(\; n^\{2/3\}\; m^\{2/3\}\; +\; n\; +\; m\; )$.

Now consider the graph formed by using the "n" points as vertices, and the "e" line segmentsas edges. Since all of the line segments lie on one of "m" lines, and any two lines intersect in at most point, the crossing number of this graph is at most $m^2$. Applying the crossing number inequalitywe thus conclude that either $e\; leq\; 7.5\; n$, or that $m^2\; geq\; e^3\; /\; 33.75\; n^2$. In either casewe obtain the desired bound $e\; =\; O(\; n^\{2/3\}\; m^\{2/3\}\; +\; n\; +\; m\; )$.

Proof of the second formulation

Since every pair of points can be connected by at most one line, there can be at most $frac\{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:$mk\; =\; O(\; n^\{2/3\}\; m^\{2/3\}\; +\; n\; +\; m\; )$and so at least one of the statements $mk\; =\; O(\; n^\{2/3\}\; m^\{2/3\}\; )$, $mk\; =\; O(n)$, or$mk\; =\; O(m)$ is true. The third possibility is ruled out since "k" was assumed to be large, so we are leftwith the first two. But in either of these two cases, some elementary algebra will give the bound $m\; =\; O(\; n^2\; /\; k^3\; +\; n/k\; )$ as desired.

References