论文标题
不平衡Zarankiewicz编号的确切值
Exact values for unbalanced Zarankiewicz numbers
论文作者
论文摘要
For positive integers $s$, $t$, $m$ and $n$, the Zarankiewicz number $Z_{s,t}(m,n)$ is defined to be the maximum number of edges in a bipartite graph with parts of sizes $m$ and $n$ that has no complete biparitite subgraph containing $s$ vertices in the part of size $m$ and $t$ vertices in the part of size $ n $。一个简单的参数表明，对于每种$ t \ geq 2 $，$ z_ {2，t}（m，n）=（t-1）\ binom {m} {2} {2}+n $时，$ n \ geq（t-1）\ binom {m} {m} {2} {2} $。在这里，对于大$ m $，我们在几乎所有剩余的情况下，确定$ z_ {2，t}（m，n）$的确切值，其中$ n =θ（tm^2）$。我们在$ z_ {2，t}（m，n）$上建立了一个上限的新家庭，该家庭补充了罗马已经获得的家庭。然后，我们证明这些界限中最好的地板几乎总是实现的。我们还表明，在某些情况下，无法实现这一楼层，而其他确定是否实现的情况可能是一个很难的问题。通过线性超图的镜头查看问题，我们的结果证明了我们的结果，我们的构造利用了在密集图的边缘分解上的现有结果。
For positive integers $s$, $t$, $m$ and $n$, the Zarankiewicz number $Z_{s,t}(m,n)$ is defined to be the maximum number of edges in a bipartite graph with parts of sizes $m$ and $n$ that has no complete biparitite subgraph containing $s$ vertices in the part of size $m$ and $t$ vertices in the part of size $n$. A simple argument shows that, for each $t \geq 2$, $Z_{2,t}(m,n)=(t-1)\binom{m}{2}+n$ when $n \geq (t-1)\binom{m}{2}$. Here, for large $m$, we determine the exact value of $Z_{2,t}(m,n)$ in almost all of the remaining cases where $n=Θ(tm^2)$. We establish a new family of upper bounds on $Z_{2,t}(m,n)$ which complement a family already obtained by Roman. We then prove that the floor of the best of these bounds is almost always achieved. We also show that there are cases in which this floor cannot be achieved and others in which determining whether it is achieved is likely a very hard problem. Our results are proved by viewing the problem through the lens of linear hypergraphs and our constructions make use of existing results on edge decompositions of dense graphs.
