A semi-algebraic version of Zarankiewicz's problem (Q2628329)

Summary: 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} + \varepsilon} + m + n\right)\) edges, where here \(\varepsilon\) is an arbitrarily small constant and \(C = C(d,k,t,\varepsilon)\). 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.