Videos

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