Zarankiewicz's problem in hereditary families of graphs, with geometric applications

Zarankiewicz's problem is one of the central problems in extremal graph theory, and it asks for the maximum number of edges in a bipartite graph with vertex classes of size n, which does not contain the complete bipartite graph K_{s, s}. In general graphs, the maximum number of such edges is at most O(n^{2-1/s}), as shown by the classical Kovari-Sos-Turan theorem. In recent years, an interesting twist on this problem attracted the interest of many researchers: given a family of graphs F closed under taking induced subgraphs, what is the maximum number of edges in a graph of F with n vertices, which does not contain the complete bipartite graph K_{s, s}? This setup subsumes several questions from combinatorial geometry and structural graph theory, and it turns out that the behavior of this number often depends more on the family F than on s. We will discuss this problem for several natural families F (such as the family of graphs avoiding a fixed induced subgraph), and give some geometric applications of our results.

This talk is based on joint work with Zach Hunter, Benny Sudakov and Istvan Tomon.