Algebraic and Analytic Methods in Combinatorics: On Zarankiewicz's Problem for Intersection Hypergraphs of Geometric Object
Presenter
March 18, 2025
Keywords:
- extremal combinatorics
- extremal graph theory
- probabilistic combinatorics
- discrete geometry
- additive combinatorics
- combinatorial geometry
- incidence geometry
- arithmetic progressions
- Discrete analysis
MSC:
- 05C25 - Graphs and abstract algebra (groups rings fields
- etc.) [See also 20F65]
- 05C35 - Extremal problems in graph theory [See also 90C35]
- 05C50 - Graphs and linear algebra (matrices eigenvalues etc.)
- 05D40 - Probabilistic methods in extremal combinatorics including polynomial methods (combinatorial Nullstellensatz etc.)
- 52C35 - Arrangements of points flats hyperplanes (aspects of discrete geometry) [See also 14N20 32S22]
Abstract
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