MATH Seminar

Title: Zarankiewicz problem, VC-dimension, and incidence geometry
Seminar: Discrete Mathematics
Speaker: Cosmin Pohoata of Yale University
Contact: Dwight Duffus, dwightduffus@emory.edu
Date: 2022-01-21 at 10:00AM
Venue: Zoom and W201
Download Flyer
Abstract: The Zarankiewicz problem is a central problem in extremal graph theory, which lies at the intersection of several areas of mathematics. It asks for the maximum number of edges in a bipartite graph on $2n$ vertices, where each side of the bipartition contains $n$ vertices, and which does not contain the complete bipartite graph $K_{s,t}$ as a subgraph. One of the many reasons this problem is rather special among Tur\'an-type problems is that the extremal graphs in question, whenever available, always seem to have to be of an algebraic nature, in particular witnesses to basic intersection theory phenomena. The most tantalizing case is by far the diagonal problem, for which the answer is unknown for most values of $s = t$, and where it is a complete mystery what the extremal graphs could look like. In this talk, we will discuss a new phenomenon related to an important variant of this problem, which is the analogous question in bipartite graphs with bounded VC-dimension. We will present several new consequences in incidence geometry, which improve upon classical results. \\ \\ This is based on joint work with Oliver Janzer.