Lower bounds for incidences with hypersurfaces

Lower bounds for incidences with hypersurfaces, Discrete Analysis 2016:16, 14pp.

A fundamental result in combinatorial geometry, the Szemerédi-Trotter theorem, states that among any $n$ points and $m$ lines in $\mathbb R^2$ there can be at most $O((mn)^{2/3}+m+n)$ incidences, where an incidence is a pair that consists of one of the points and one of the lines with the point contained in the line. Simple examples show that this result is best possible. (The interesting case is when $m$ and $n$ are of roughly comparable size: the terms $m$ and $n$ in the bound are there to deal with the case when $m$ is much bigger than $n$ or $n$ is much bigger than $m$, when trivial examples are best.)

The Szemerédi-Trotter theorem has been generalized in various ways. To begin with, it holds not just for incidences between points and lines, but also for incidences between points and pseudolines: if we define a pseudoline system to be a set of curves in the plane such that no two of them intersect in more than a point, then we can replace “line” by “pseudoline” in the Szemerédi-Trotter theorem, and several of its proofs are almost unaffected.

It is also possible to relax the condition on pseudolines and merely to insist that any two curves intersect in at most $s$ points for some fixed $s$: this introduces an extra constant factor into the bound. In particular, this implies that, under appropriate conditions, the Szemerédi-Trotter theorem holds for incidences between points and algebraic curves of bounded degree.

Another direction of generalization is to higher dimensions: for example, one can consider incidences between points and hyperplanes in $\mathbb R^d$. Considering the case of planes in $\mathbb R^3$, one sees that for an interesting result some kind of non-degeneracy condition is needed, since otherwise one can take a collection of planes that all meet in a line and a collection of points that all lie in that line. The obvious condition is that any three planes from the set meet in at most one point, or for general $d$ that any $d$ of the hyperplanes meet in at most one point.

Again, we can consider not just affine subspaces. One quite general result, due to Fox, Pach, Sheffer, Suk and Zahl, states that if $P$ is a set of points in $\mathbb R^d$ and $\Gamma$ is a set of varieties in $\mathbb R^d$ of dimension at most $D$, and if the incidence graph of points and varieties (defined in an obvious way) contains no copy of the complete bipartite graph $K_{s,t}$ – or equivalently any $t$ of the varieties intersect in at most $s-1$ points – then the number of incidences is at most
$$C(m^{(d-1)s/(ds-1)+\epsilon}n^{(d(s-1)/(ds-1)}+m+n)$$
for a constant $C$ that depends on $D, s, t$ and $\epsilon$ only.

The purpose of this paper is to find matching lower bounds for this result and other results of a similar kind, at least in certain situations. In particular, for every $d\geq 4$ the author finds a collection of $m$ points and $n$ hyperplanes such that the incidence graph contains no copy of $K_{2,(d-1)/\epsilon)}$ and the number of incidences is at least $cm^{2(d-1)/(2d-1)}n^{d/(2d-1)-\epsilon}$. Here, $n$ is in the range for which the dominant term in the upper bound above is the first one, so this construction shows that up to the $\epsilon$ in the exponent that result is best possible.

Such matching bounds are not very common in the area, and there are still plenty of open problems. For instance, the dependence on $s$ is not very well understood: it is conjectured that when there are at least as many points as curves, increasing $s$ should not have an effect on the exponent (so the fact that it does in the upper bound stated above would be an artefact of the proof rather than reflecting what is actually going on). This blog post by the author discusses an example with $s=3$ that gives a larger exponent than the Szemerédi-Trotter bound for $s=2$, but nothing better is known when $s>3$.

Another blog post of the author discusses applications of incidence problems to several other areas, including harmonic analysis, theoretical computer science, and number theory.