2026-07-24T03:33:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23185 2025-10-02T12:42:18Z ddc:004 open_access

On Zarankiewicz’s Problem for Intersection Hypergraphs of Geometric Objects Chan, Timothy M. Keller, Chaya Smorodinsky, Shakhar Zarankiewicz’s Problem hypergraphs intersection graphs axis-parallel boxes pseudo-discs 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Timothy M. Chan and Chaya Keller and Shakhar Smorodinsky 2025 Is Part Of LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2025.33 urn:nbn:de:0030-drops-231850 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.33 eng https://creativecommons.org/licenses/by/4.0/legalcode