On Zarankiewicz's Problem for Intersection Hypergraphs of Geometric Object
Algebraic and Analytic Methods in Combinatorics March 17, 2025 - March 21, 2025
Location: SLMath: Eisenbud Auditorium, Online/Virtual
On Zarankiewicz's Problem for Intersection Hypergraphs of Geometric Object
The hypergraph Zarankiewicz's problem, introduced by Erd\H{o}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 $K_{t,t,\ldots,t}$. Erd\H{o}s obtained a near optimal bound of $O(n^{r-1/t^{r-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 talk 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 $\mathbb{R}^d$ and for families of pseudo-discs.
Joint work with Timothy Chan and Shakhar Smorodinsky
On Zarankiewicz's Problem for Intersection Hypergraphs of Geometric Object
Please report video problems to itsupport@slmath.org.
See more of our Streaming videos on our main VMath Videos page.