论文标题
关于具有有限的VC-Dimension图的Zarankiewicz问题
On the Zarankiewicz problem for graphs with bounded VC-dimension
论文作者
论文摘要
Zarankiewicz的问题要求在$ N $ VERTICES上的双分图中的最大边数，该图形不包含完整的两部分图$ k_ {k，k，k} $作为子图。由于KőVári，Sós和Turán引起的经典定理说，这一数字为$ o \ left（n^{2-1/k} \ right）$。这个问题的一个重要变体是在具有VC-Dimension的两部分图中的类似问题，最多是$ d $，其中$ d $是固定整数，因此$ k \ geq d \ geq 2 $。 Fox，Pach，Sheffer，Suk和Zahl的显着结果[J.欧元。数学。 Soc。 （JEMS），不。 19，1785-1810]在发病率的几何形状中有多个应用程序表明，在此其他假设下，在$ n $ Vertices上的两部分图中的边数，并且没有$ k_ {k，k，k} $的副本，作为一个子图，必须为$ o \ weft（n^{2-1/d} \ right）$。当$ k = d = 2 $时，该定理很清晰，因为通过设计，任何$ k_ {2,2} $ - 免费图形自动最多具有VC-dimension，最多只有$ 2 $，并且有$ω\ left（n^{3/2}} \ right）$ω\ weft的众所周知的示例。但是，事实证明，这种现象不再持续到任何较大的$ d $。 我们显示了以下改进的结果：两分之一图中的最大边数，没有$ k_ {k，k} $和$ d $的VC-dimension $ d $ is $ o（n^{2-1/d}）$，每$ k \ geq d \ geq d \ geq 3 $。
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\left(n^{2 - 1/k}\right)$. 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 \geq d \geq 2$. 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 $O\left(n^{2 - 1/d}\right)$. 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 $Ω\left(n^{3/2}\right)$ 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 \geq d \geq 3$.
