A semi-algebraic version of Zarankiewicz's problem

Fox, Jacob and Pach, János and Sheffer, Ádám and Suk, Andrew and Zahl, Joshua (2017) A semi-algebraic version of Zarankiewicz's problem. JOURNAL OF THE EUROPEAN MATHEMATICAL SOCIETY, 19 (6). pp. 1785-1810. ISSN 1435-9855

Preview

Text 1407.5705v2.pdf Download (351kB) | Preview

Abstract

A bipartite graph G is semi-algebraic in Rd if its vertices are represented by point sets P; Q Rd and its edges are defined as pairs of points.p; q/2 P × 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 Kk;k-free semi-algebraic bipartite graph G D.P; Q; E/in R2 with P D m and Q D n is at most O.mn/2=3 C m C n/, and this bound is tight. In dimensions d = 3, we show that all such semi-algebraic graphs have at most C.mn/d=.dC1/C" C m C n/edges, where " is an arbitrarily small constant and C D C.d; k; t; "/. 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 Rd, an improved bound for a d-dimensional variant of the Erdos unit distances? problem, and more. © 2017 European Mathematical Society.

Actions (login required)

Edit Item