A dichotomy for hypergraph Zarankiewicz problems on axis-parallel boxes

Abstract

We study the Zarankiewicz problem for $r$-partite, $r$-uniform intersection hypergraphs arising from $r$ families of axis-parallel boxes in ${\mathbb{R}}^d$ with prescribed directions $F_1,\dots ,F_r\subseteq \{1,\dots ,d\}$. This extends the problems studied by Chan and Har-Peled on points and $d$-dimensional boxes in ${\mathbb{R}}^d$, corresponding to $(F_1,F_2)=(\varnothing ,[d])$, as well as by Chan, Keller, and Smorodinsky on $r$ families of $d$-dimensional boxes, corresponding to $(F_1,\dots ,F_r)=([d],\dots ,[d])$. Our main result establishes a sharp dichotomy for the Zarankiewicz number in this setting: it is either $\hat{I}{˜}_r(t{n}^{r-1})$ or at least $\hat{I}\text{c◯}(t{n}^{r-1}\cdot \frac{\log n}{\log \log n})$, depending only on a simple set-theoretic condition on $(F_1,\dots ,F_r)$, which we call $2$-coherence. Informally, $2$-coherence captures whether the configuration contains an underlying two-dimensional incidence structure, which is precisely what gives rise to the extra polylogarithmic factor. Our proof proceeds via a sequence of reductions and a geometric slicing argument that reduces the problem to planar incidence bounds.