# Journal of the European Mathematical Society

Full-Text PDF (218 KB) | Metadata | Table of Contents | JEMS summary

**Volume 19, Issue 6, 2017, pp. 1785–1810**

**DOI: 10.4171/JEMS/705**

Published online: 2017-04-27

A semi-algebraic version of Zarankiewicz's problem

Jacob Fox^{[1]}, János Pach

^{[2]}, Adam Sheffer

^{[3]}, Andrew Suk

^{[4]}and Joshua Zahl

^{[5]}(1) MIT, Cambridge, USA

(2) EPFL, Lausanne, Switzerland

(3) Tel Aviv University, Israel

(4) MIT, Cambridge, USA

(5) MIT, Cambridge, USA

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.

*Keywords: *Semi-algebraic graph, extremal graph theory, VC-dimension, polynomial partitioning, incidences

Fox Jacob, Pach János, Sheffer Adam, Suk Andrew, Zahl Joshua: A semi-algebraic version of Zarankiewicz's problem. *J. Eur. Math. Soc.* 19 (2017), 1785-1810. doi: 10.4171/JEMS/705