2024/12/09 by Chan, Timothy M., Keller, Chaya, Smorodinsky, Shakhar · 1 citation
#05C35 #05C65 #Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2412.06490
The hypergraph Zarankiewicz's problem, introduced by Erdős in 1964, asks for the maximum number of hyperedges in an r-partite hypergraph with n vertices in each part that does not contain a copy of Kt,t,…,t. Erdős obtained a near optimal bound of O(n^r-1/tr-1) for general hypergraphs. In recent years, several works obtained improved bounds under various algebraic assumptions -- e.g., if the hypergraph is semialgebraic. In this paper we study the 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 Od,r(tnr-1((log n)/(log log n))d-1). The best previous bound was larger by a factor of about (log n)^d(2r-1-2). For pseudo-discs, we obtain the bound Or(tnr-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/tr-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.