Talk information

Date: Sunday, May 26, 2024
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Shakhar Smorodinsky (Ben-Gurion University)
Title: On Zarankiewicz's Problem for intersection graphs

Abstract:

The classical Zarankiewicz’s problem asks for the maximum number of edges in a bipartite graph on $n$ vertices which does not contain the complete bipartite graph $K_{t,t}$. In one of the cornerstones of extremal graph theory K{\H o}v{' a}ri S{' o}s and Tur{' a}n proved an upper bound of $O(n^{2-\frac{1}{t}})$. In a celebrated result Fox et al. obtained an improved bound of $O(n^{2-\frac{1}{d}})$ for graphs with (so-called) VC-dimension $d$ (where $d < t$). Recently, Chan and Har-Peled presented (quasi-)linear upper bounds for several classes of geometrically-defined incidence graphs, including a bound of $O(n \log \log n)$ for the incidence graph of points and pseudo-discs in the plane. In this talk we present a new approach to Zarankiewicz’s problem, via $(\epsilon,t)$-nets — a recently introduced generalization of the classical notion of $\epsilon$-nets for hypergraphs. Using the new approach, we obtain a very simple new proof of the $O(n^{2-\frac{1}{d}})$ bound of Fox et al., and a sharp bound of $O(n)$ for the intersection graph of two families of pseudo-discs, thus both improving and generalizing the result of Chan and Har-Peled from incidence graphs to intersection graphs. The talk is self contained and no prior knowledge on VC-dimension nor $\epsilon$-nets is needed.

Joint work with Chaya Keller.