On Zarankiewicz’s Problem for Intersection Hypergraphs of Geometric Objects
Chan, Timothy M., Keller, Chaya, Smorodinsky, Shakhar · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2025
In this paper we study the hypergraph Zarankiewicz’s problem in a geometric setting - for r-partite intersection hypergraphs of families of geometric objects. Our main results are essentially sharp bounds for families of axis-parallel boxes in ℝ^d and families of pseudo-discs. For axis-parallel boxes, we obtain the sharp bound O_{d,t}(n^{r-1}((log n)/(log log n))^{d-1}). The best previous bound was larger by a factor of about (log n)^{d(2^{r-1}-2)}. For pseudo-discs, we obtain the bound O_t(n^{r-1}(log n)^{r-2}), which is sharp up to logarithmic factors. As this hypergraph has no algebraic structure, no improvement of Erdős' 60-year-old O(n^{r-(1/t^{r-1})}) bound was known for this setting. Futhermore, even in the special case of discs for which the semialgebraic structure can be used, our result improves the best known result by a factor of Ω̃(n^{(2r-2)/(3r-2)}). To obtain our results, we use the recently improved results for the graph Zarankiewicz’s problem in the corresponding settings, along with a variety of combinatorial and geometric techniques, including shallow cuttings, biclique covers, transversals, and planarity.