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 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. We show that the existence of `small'-sized $\epsilon-t$-nets implies upper bounds for Zarankiewicz's problem. 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. We also obtain improved bounds for other classes of geometric intersection graphs.
The talk is self contained and no prior knowledge on VC-dimension nor $\epsilon$-nets is needed.
Joint work with Chaya Keller.