The celebrated Szemerédi-Trotter theorem gives a bound for the set of incidences between a finite set of points and a finite set of lines in the Euclidean plane . Specifically, the bound is
where we use the asymptotic notation or to denote the statement that for some absolute constant . In particular, the number of incidences between points and lines is . This bound is sharp; consider for instance the discrete box with being the collection of lines . One easily verifies that , , and , showing that (1) is essentially sharp in the case ; one can concoct similar examples for other regimes of and .
On the other hand, if one replaces the Euclidean plane by a finite field geometry , where is a finite field, then the estimate (1) is false. For instance, if is the entire plane , and is the set of all lines in , then are both comparable to , but is comparable to , thus violating (1) when is large. Thus any proof of the Szemerédi-Trotter theorem must use a special property of the Euclidean plane which is not enjoyed by finite field geometries. In particular, this strongly suggests that one cannot rely purely on algebra and combinatorics to prove (1); one must also use some Euclidean geometry or topology as well.
Nowadays, the slickest proof of the Szemerédi-Trotter theorem is via the crossing number inequality (as discussed in this previous post), which ultimately relies on Euler’s famous formula ; thus in this argument it is topology which is the feature of Euclidean space which one is exploiting, and which is not present in the finite field setting. Today, though, I would like to mention a different proof (closer in spirit to the original proof of Szemerédi-Trotter, and also a later argument of Clarkson et al.), based on the method of cell decomposition, which has proven to be a very flexible method in combinatorial incidence geometry. Here, the distinctive feature of Euclidean geometry one is exploiting is convexity, which again has no finite field analogue.
which is inferior to (1). (On the other hand, this estimate works in both Euclidean and finite field geometries, and is sharp in the latter case, as shown by the example given earlier.) Dually, the axiom that two lines determine at most one point gives the bound
An inspection of the proof of (2) shows that it is only expected to be sharp when the bushes associated to each point behave like “independent” subsets of , so that there is no significant correlation between the bush of one point and the bush of another point .
However, in Euclidean space, we have the phenomenon that the bush of a point is influenced by the region of space that lies in. Clearly, if lies in a set (e.g. a convex polygon), then the only lines that can contribute to are those lines which pass through . If is a small convex region of space, one expects only a fraction of the lines in to actually pass through . As such, if and both lie in , then and are compressed inside a smaller subset of , namely the set of lines passing through , and so should be more likely to intersect than if they were independent. This should lead to an improvement to (2) (and indeed, as we shall see below, ultimately leads to (1)).
More formally, the argument proceeds by applying the following lemma:
Lemma 1 (Cell decomposition) Let be a finite collection of lines in , let be a finite set of points, and let . Then it is possible to find a set of lines in , plus some additional open line segments not containing any point in , which subdivide into convex regions (or cells), such that the interior of each such cell is incident to at most lines.
Let be a parameter to be optimised later. We apply the cell decomposition to subdivide into open convex regions, plus a family of lines. Each of the convex regions has only lines through it, and so by (2) contributes incidences. Meanwhile, on each of the lines in used to perform this decomposition, there are at most transverse incidences (because each line in distinct from can intersect at most once), plus all the incidences along itself. Putting all this together, one obtains
We optimise this by selecting ; from (4) we can ensure that , so that . One then obtains
We can iterate away the error (halving the number of lines each time) and sum the resulting geometric series to obtain (1).
It remains to prove (1). If one subdivides using arbitrary lines, one creates at most cells (because each new line intersects the existing lines at most once, and so can create at most distinct cells), and for a similar reason, every line in visits at most of these regions, and so by double counting one expects lines per cell “on the average”. The key difficulty is then to get lines through every cell, not just on the average. It turns out that a probabilistic argument will almost work, but with a logarithmic loss (thus having lines per cell rather than ); but with a little more work one can then iterate away this loss also. The arguments here are loosely based on those of Clarkson et al.; a related (deterministic) decomposition also appears in the original paper of Szemerédi and Trotter. But I wish to focus here on the probabilistic approach.)
It is also worth noting that the original (somewhat complicated) argument of Szemerédi-Trotter has been adapted to establish the analogue of (1) in the complex plane by Toth, while the other known proofs of Szemerédi-Trotter, so far, have not been able to be extended to this setting (the Euler characteristic argument clearly breaks down, as does any proof based on using lines to divide planes into half-spaces). So all three proofs have their advantages and disadvantages.
— 1. The trivial incidence estimate —
We first give a quick proof of the trivial incidence bound (2). We have
and thus by Cauchy-Schwarz
On the other hand, observe that
Because two distinct points are incident to at most one line, the right-hand side is at most , thus
A more informal proof of (2) can be given as follows. Suppose for contradiction that was much larger than . Since , this implies that that the are much larger than on the average. By the birthday paradox, one then expects two randomly chosen to intersect in at least two places ; but this would mean that two lines intersect in two points, a contradiction. The use of Cauchy-Schwarz in the rigorous argument given above can thus be viewed as an assertion that the average intersection of and is at least as large as what random chance predicts.
As mentioned in the introduction, we now see (intuitively, at least) that if nearby are such that are drawn from a smaller pool of lines than , then their intersection is likely to be higher, and so one should be able to improve upon (2).
— 2. The probabilistic bound —
Now we start proving Lemma 1. We can assume that , since the claim is trivial otherwise (we just use all the lines in to subdivide the plane, and there are no lines left in to intersect any of the cells). Similarly we may assume that , and that is large. We can also perturb all the lines slightly and assume that the lines are in general position (no three are concurrent), as the general claim then follows from a limiting argument (note that this may send some of the cells to become empty). (Of course, the Szemerédi-Trotter theorem is quite easy under the assumption of general position, but this theorem is not our current objective right now.)
We use the probabilistic method, i.e. we construct by some random recipe and aim to show that the conclusion of the lemma holds with positive probaility.
The most obvious approach would be to choose the lines at random from , thus each line has a probability of of lying in . Actually, for technical reasons it is slightly better to use a Bernoulli process to select , thus each line lies in with an independent probability of . This can cause to occasionally have size much larger than , but this probability can be easily controlled (e.g. using the Chernoff inequality). So with high probability, consists of lines, which therefore carve out cells. The remaining task is to show that each cell is incident to at most lines from .
Observe that each cell is a (possibly unbounded) polygon, whose edges come from lines in . Note that (except in the degenerate case when consists of at most one line, which we can ignore) any line which meets a cell in , must intersect at least one of the edges of . If we pretend for the moment that all cells have a bounded number of edges, it would then suffice to show that each edge of each cell was incident to lines.
Let’s see how this would go. Suppose that one line was picked for the set , and consider all the other lines in that intersect ; there are of these lines , which (by the general position hypothesis) intersect at distinct points on the line. If one of these lines intersecting is also selected for , then the corresponding point will become a vertex of one of the cells (indeed, it will be the vertex of four cells). Thus each of these points on has an independent probability of of becoming a vertex for a cell.
Now consider consecutive such points on . The probability that they all fail to be chosen as cell vertices is ; if , then this probability is . Thus runs of much more than points without vertices are unlikely. In particular, setting , we see that the probability that any given consecutive points on any given line are skipped is . By the union bound, we thus see that with probability , that every line has at most points between any two adjacent vertices. Or in other words, the edge of every cell is incident to at most lines from . This yields Lemma 1 except for two things: firstly, the logarthmic loss of , and secondly, the assumption that each cell had only a bounded number of edges.
To fix the latter problem, we will have to add some line segments to . First, we randomly rotate the plane so that none of the lines in are vertical. Then we do the following modified construction: we select lines from as before, creating cells, some of which may have a very large number of edges. But then for each cell, and each vertex in that cell, we draw a vertical line segment from that vertex (in either the up or down direction) to bisect the cell into two pieces. (If the vertex is on the far left or far right of the cell, we do nothing.) Note that almost surely this construction will avoid hitting any point in . Doing this once for each vertex, we see that we have subdivided each of the old cells into a number of new cells, each of which have at most four sides (two vertical sides, and two non-vertical sides). So we have now achieved a bounded number of sides per cell. But what about the number of such cells? Well, each vertex of each cell is responsible for at most two subdivisions of one cell into two, and the number of such vertices is at most (as they are formed by intersecting two lines from the original selection of lines together), so the total number of cells is still .
Is it still true that each edge of each cell is incident to lines in ? We have already proven this (with high probability) for all the old edges – the ones that were formed from lines in . But there are now some new edges, caused by dropping a vertical line segment from the intersection of two lines in . But it is not hard to see that one can use much the same argument as before to see that with high probability, each of these line segments is incident to at most lines in as desired.
Finally, we have to get rid of the logarithm. An inspection of the above arguments (and a use of the first moment method) reveals the following refinement: for any , there are expected to be at most cells which are incident to more than lines, where is an absolute constant. This is already enough to improve the bound slightly to . But one can do even better by using Lemma 1 as an induction hypothesis, i.e. assume that for any smaller set of lines with , and any , one can partition into at most cells using at most lines such that each cell is incident to at most lines, where are absolute constants. (When using induction, asymptotic notation becomes quite dangerous to use, and it is much safer to start writing out the constants explicitly. To close the induction, one has to end up with the same constants as one started with.) For each between and which is a power of two, one can apply the induction hypothesis to all the cells which are incident to between and (with set equal to the lines in incident to this cell, and set comparable to ), and sum up (using the fact that converges, especially if is restricted to powers of two) to close the induction if the constants are chosen properly; we leave the details as an exercise.