On the Zarankiewicz problem for graphs with bounded VC-dimension

MaRDI QIDQ6348113zbMATH OpenFDO

Authors Oliver Janzer, Cosmin Pohoata

Publication date 31 August 2020

Abstract: 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 KH{o}v'ari, S'os, and Tur'an says that this number of edges is $Oleft(n^{2-1/k}ight)$. 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 $kgeqdgeq2$. A remarkable result of Fox, Pach, Sheffer, Suk, and Zahl [J. Eur. Math. Soc. (JEMS), no. 19, 1785-1810] 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 $Oleft(n^{2-1/d}ight)$. 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 $Omegaleft(n^{3/2}ight)$ 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 $kgeqdgeq3$.

This page was built for publication: On the Zarankiewicz problem for graphs with bounded VC-dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6348113)