论文标题
HyperGraph二分之一Turán问题的渐近学问题
Asymptotics of the hypergraph bipartite Turán problem
论文作者
论文摘要
对于正整数$ s，t，r $，让$ k_ {s，t}^{（r）} $表示$ r $ rub-rystriform hypergraph的顶点套件是成对的脱节集合$ x，y_1，y_1，\ dots，y_t $，y__t $，y__t $ = s $和$ | y_1 | = \ dots = | y_t | = r-1 $，其边缘集为$ \ {\ {x \} \ cup y_i：x \ in x，1 \ leq i \ leq t \} $。 $ k_ {s，t}^{（r）} $的Turán功能的研究近年来引起了极大的兴趣。我们的主要结果如下。首先，我们表明 \ begin {equation} \ Mathrm {ex}（n，k_ {s，t}^{（r）}）= o_ {s，r}（t^{\ frac {1} {s-1} {s-1}} n^n^{r- \ frac {1} \ end {equation} 对于所有$ s，t \ geq 2 $和$ r \ geq 3 $，提高了以前最佳限制的$ n $的功率，并解决了$ \ mathrm {exrm {exrm {ex}（n，k_ {2，k_ {2，t}^{（3）}^{（3）} $ to $ t $的依赖性问题。其次，我们证明当$ r $均匀而$ t \ gg s $时，这种上限很紧。这反驳了Xu，Zhang和GE的猜想。第三，我们表明，上述上限并不是$ r = 3 $的紧密，也就是说，$ \ mathrm {ex}（n，k_ {s，t}^{（3）}）= o_ {s，t}（n^{3 - \ frac {1}} {1} {1} {1} {s -1} {s -1} - \ varepsilon_s $ s $ s $ S）这表明$ \ mathrm {ex}（n，k_ {s，t}^{（r）}）$的行为可能取决于$ r $的奇偶校验。最后，我们证明了Ergemlidze，Jiang和Methuku的猜想，这是双方Turán问题的超图类似物，用于一侧有界度的图形。我们的工具包括有关依赖的随机选择方法的新颖扭曲，以及由Kollár，Rónyai和Szabó构建的著名规范图的变体。
For positive integers $s,t,r$, let $K_{s,t}^{(r)}$ denote the $r$-uniform hypergraph whose vertex set is the union of pairwise disjoint sets $X,Y_1,\dots,Y_t$, where $|X| = s$ and $|Y_1| = \dots = |Y_t| = r-1$, and whose edge set is $\{\{x\} \cup Y_i: x \in X, 1\leq i\leq t\}$. The study of the Turán function of $K_{s,t}^{(r)}$ received considerable interest in recent years. Our main results are as follows. First, we show that \begin{equation} \mathrm{ex}(n,K_{s,t}^{(r)}) = O_{s,r}(t^{\frac{1}{s-1}}n^{r - \frac{1}{s-1}}) \end{equation} for all $s,t\geq 2$ and $r\geq 3$, improving the power of $n$ in the previously best bound and resolving a question of Mubayi and Verstraëte about the dependence of $\mathrm{ex}(n,K_{2,t}^{(3)})$ on $t$. Second, we show that this upper bound is tight when $r$ is even and $t \gg s$. This disproves a conjecture of Xu, Zhang and Ge. Third, we show that the above upper bound is not tight for $r = 3$, namely that $\mathrm{ex}(n,K_{s,t}^{(3)}) = O_{s,t}(n^{3 - \frac{1}{s-1} - \varepsilon_s})$ (for all $s\geq 3$). This indicates that the behaviour of $\mathrm{ex}(n,K_{s,t}^{(r)})$ might depend on the parity of $r$. Lastly, we prove a conjecture of Ergemlidze, Jiang and Methuku on the hypergraph analogue of the bipartite Turán problem for graphs with bounded degrees on one side. Our tools include a novel twist on the dependent random choice method as well as a variant of the celebrated norm graphs constructed by Kollár, Rónyai and Szabó.
