On the Zarankiewicz Problem for Graphs with Bounded VC-Dimension.

The problem of Zarankiewicz asks for the maximum number of edges in a bipartite graph on n vertices which does not contain the complete bipartite graph K k , k as a subgraph. A classical theorem due to Kővári, Sós, and Turán says that this number of edges is O n 2 - 1 / k . An important variant of this problem is the analogous question in bipartite graphs with VC-dimension at most d, where d is a fixed integer such that k ≥ d ≥ 2 . A remarkable result of Fox et al. (J. Eur. Math. Soc. (JEMS) 19:1785–1810, 2017) with multiple applications in incidence geometry shows that, under this additional hypothesis, the number of edges in a bipartite graph on n vertices and with no copy of K k , k as a subgraph must be O n 2 - 1 / d . This theorem is sharp when k = d = 2 , because by design any K 2 , 2 -free graph automatically has VC-dimension at most 2, and there are well-known examples of such graphs with Ω n 3 / 2 edges. However, it turns out this phenomenon no longer carries through for any larger d. We show the following improved result: the maximum number of edges in bipartite graphs with no copies of K k , k and VC-dimension at most d is o (n 2 - 1 / d) , for every k ≥ d ≥ 3 . [ABSTRACT FROM AUTHOR]