Title: Zarankiewicz, VC-dimension, and incidence geometry

Speaker: Dr. Cosmin Pohoata, Yale University
For your reference, here is Dr. Pohoata’s website: https://pohoatza.wordpress.com/

Time: Jan 28, 2022 04:00 PM Central Time (US and Canada)

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 $\operatorname{ex}(n,K_{s,t})$ 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 reasons this problem is particularly interesting is that, for various (rather mysterious) reasons, the extremal graphs seem to have to be of algebraic nature, which is not always the case for Tur\’an-type problems. The most tantalizing case is by far the symmetric problem where $s=t:=k$, for which the value of $\operatorname{ex}(n,K_{k,k})$ is completely unknown for most values of $k$. In this talk, we will discuss a rather surprising new phenomenon related to an important variant of this problem, which is the analogous question in bipartite graphs with VC-dimension at most $d$, where $d$ is a fixed integer such that $k \geq d \geq 2$. We will also present a few consequences of our result in incidence geometry, which improve upon classical results. Based on joint work with Oliver Janzer (ETH).

Location: Join Zoom Meeting
https://memphis.zoom.us/j/87547314942?pwd=aWFsbVpHZGg1ZjJVMVFFNmo5ZTg4QT09

Meeting ID: 875 4731 4942
Passcode: 220994