论文标题
在三方图的子图上
On subgraphs of tripartite graphs
论文作者
论文摘要
Bollobás，Erdős和Szemerédi[离散数学13（1975），97--107]调查了Zarankiewicz问题的三方概括：哪些最低度迫使三方图形图形图形图，每个部分都包含octahedral Graph $ k_3（2）$？他们证明了$ n+2^{ - 1/2} n^{3/4} $足够，并建议将其削弱至$ n+cn^{1/2} $，对于某些常数$ c> 0 $。在本说明中，我们表明他们的方法仅给出$ n+（1+ o（1））n^{11/12} $，并提供了许多构造，如果true，则可以更好地显示出$ n+ c n^{1/2} $。
Bollobás, Erdős, and Szemerédi [Discrete Math 13 (1975), 97--107] investigated a tripartite generalization of the Zarankiewicz problem: what minimum degree forces a tripartite graph with $n$ vertices in each part to contain an octahedral graph $K_3(2)$? They proved that $n+2^{-1/2}n^{3/4}$ suffices and suggested it could be weakened to $n+cn^{1/2}$ for some constant $c>0$. In this note we show that their method only gives $n+ (1+o(1)) n^{11/12}$ and provide many constructions that show if true, $n+ c n^{1/2}$ is better possible.
