标题： 三部图上的Zarankiewicz问题 显示英文标题

标题： The Zarankiewicz problem on tripartite graphs

摘要： 1975年，Bollobás、Erdős和Szemerédi要求最小的$\tau$，使得具有最小度数$n + \tau$的$n \times n \times n$三部图必须包含$K_{t, t, t}$，并猜想$\tau = \mathcal{O}(n^{1/2})$对$t = 2$成立。 我们证明了$\tau = \mathcal{O}(n^{1 - 1/t})$，这证实了他们的猜想，并且在广泛接受的猜想$\operatorname{ex}(n, K_{t, t}) = \Theta(n^{2 - 1/t})$的前提下是最佳的。 我们的证明使用了密度增加的方法。 我们还构造了一个极值图的无限族。 显示英文摘要

摘要： In 1975, Bollob\'{a}s, Erd\H{o}s, and Szemer\'{e}di asked for the smallest $\tau$ such that an $n \times n \times n$ tripartite graph with minimum degree $n + \tau$ must contain $K_{t, t, t}$, conjecturing that $\tau = \mathcal{O}(n^{1/2})$ for $t = 2$. We prove that $\tau = \mathcal{O}(n^{1 - 1/t})$ which confirms their conjecture and is best possible assuming the widely believed conjecture that $\operatorname{ex}(n, K_{t, t}) = \Theta(n^{2 - 1/t})$. Our proof uses a density increment argument. We also construct an infinite family of extremal graphs.