A semi-algebraic version of Zarankiewicz's problem

A bipartite graph G is semi-algebraic in R-d if its vertices are represented by point sets P,Q subset of R-d and its edges are defined as pairs of points (p,q) epsilon P x 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-k-free semi-algebraic bipartite graph G = (P, Q E) in R-2 with vertical bar P vertical bar = m and vertical bar Q vertical bar = n is at most O ((mn)(2/3) + m + n), and this bound is tight. In dimensions d >= 3, we show that all such semi-algebraic graphs have at most C((mn)(d/(d+1)+epsilon) + m + n) edges, where epsilon is an arbitrarily small constant and C = C(d, k, t, epsilon). This result is a far-reaching generalization of the classical Szemeredi-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 R-d, an improved bound for a d-dimensional variant of the Erdos unit distances problem, and more.