Some tight lower bounds for Turán problems via constructions of multi-hypergraphs

Zixiang Xu, Tao Zhang, Gennian Ge

Published 2019-07-27Version 1

Recently, several Tur\'{a}n type problems were solved by the powerful random algebraic method. In this paper, we use this tool to construct various multi-hypergraphs to obtain some tight lower bounds and determine the dependence on some specified large constant for different Tur\'{a}n problems. We investigate three important objects including complete $r$-partite $r$-uniform hypergraphs, complete bipartite hypergraphs and Berge theta hypergraphs. More specifically, for complete $r$-partite $r$-uniform hypergraphs, we show that if $s_{r}$ is sufficiently larger than $s_{1},s_{2},\ldots,s_{r-1},$ then $$ \text{ex}_{r}(n,K_{s_{1},s_{2},\ldots,s_{r}}^{(r)})=\Theta(s_{r}^{\frac{1}{s_{1}s_{2}\cdots s_{r-1}}}n^{r-\frac{1}{s_{1}s_{2}\cdots s_{r-1}}}).$$ For complete bipartite hypergraphs, we prove that if $s$ is sufficiently larger than $t,$ we have $$ \text{ex}_{r}(n,K_{s,t}^{(r)})=\Theta(s^{\frac{1}{t}}n^{r-\frac{1}{t}}).$$ In particular, our results imply that the famous K\"{o}vari-S\'{o}s-Tur\'{a}n's upper bound $\text{ex}(n,K_{s,t})=O(t^{\frac{1}{s}}n^{2-\frac{1}{s}})$ is tight when $t$ is large.