A semi-algebraic version of Zarankiewicz's problem

Abstract

A bipartite graph $G$ is semi-algebraic in ${\mathbb{R}}^d$ if its vertices are represented by point sets $P,Q\subset {\mathbb{R}}^d$ and its edges are defined as pairs of points $(p,q)\in P\times Q$ that satisfy a Boolean combination of a fixed number of polynomial equations and inequalities in $2d$ coordinates. We show that for fixed $k$, the maximum number of edges in a $K_{k,k}$-free semi-algebraic bipartite graph $G=(P,Q,E)$ in ${\mathbb{R}}^2$ with $|P|=m$ and $|Q|=n$ is at most $O((mn{)}^{2/3}+m+n)$, and this bound is tight. In dimensions $d\ge 3$, we show that all such semi-algebraic graphs have at most $C\left((mn{)}^{\frac{d}{d+1}+ϵ}+m+n\right)$ edges, where here $ϵ$ is an arbitrarily small constant and $C=C(d,k,t,ϵ)$. This result is a far-reaching generalization of the classical Szemerédi-Trotter incidence theorem. The proof combines tools from several fields: VC-dimension and shatter functions, polynomial partitioning, and Hilbert polynomials.

We also present various applications of our theorem. For example, a general point-variety incidence bound in ${\mathbb{R}}^d$, an improved bound for a $d$-dimensional variant of the Erdös unit distances problem, and more.