Zarankiewicz’s Problem via ϵ-t-Nets

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 Kt,t. Kővári, Sós and Turán proved an upper bound of O(n^{2− 1t} ). Fox et al. obtained an improved bound of O(n^{2− d1} ) for graphs of VC-dimension d (where d < t). Basit, Chernikov, Starchenko, Tao and Tran improved the bound for the case of semilinear graphs. Chan and Har-Peled further improved Basit et al.’s bounds and 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 paper we present a new approach to Zarankiewicz’s problem, via ϵ-t-nets – a recently introduced generalization of the classical notion of ϵ-nets. Using the new approach, we obtain 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 a short proof of the O(n^{2− d1} ) bound of Fox et al., and show improved bounds for several other classes of geometric intersection graphs, including a sharp O(n _log^log_logⁿ_n ) bound for the intersection graph of two families of axis-parallel rectangles.