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ővari, Sós and Turán proved an upper bound of O(n^{2-1/t}). In a celebrated result, Fox, Pach, Sheffer, Suk and Zahl obtained an improved bound of O(n^{2-1/d}) for graphs of 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. 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 new proof of the O(n^{2-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 several other classes of geometric intersection graphs, including a sharp O(n log n / log log n) bound for the intersection graph of two families of axis-parallel rectangles.
Joint work with Shakhar Smorodinsky.