A semi-algebraic version of Zarankiewicz's problem

Source 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 \geq 3 , we show that all such semi-algebraic graphs have at most C\left((mn)^{ \frac{d}{d+1} + \epsilon} + m + n\right) edges, where here \epsilon is an arbitrarily small constant and C = C(d,k,t,\epsilon) . 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.