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

Abstract

Recently, several hypergraph Turán problems were solved by the powerful random algebraic method. However, the random algebraic method usually requires some parameters to be very large, hence we are concerned about how these Turán numbers depend on such large parameters of the forbidden hypergraphs. In this paper, we determine the dependence on such specified large constant for several hypergraph Turán problems. More specifically, for complete $r$-partite $r$-uniform hypergraphs, we show that if $s_r$ is sufficiently larger than $s_1,s_2,\dots ,s_{r-1},$ then $${\text{ex}}_r(n,K_{s_1,s_2,\dots ,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 $r$-uniform 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ővári--Sós--Turán's upper bound $\text{ex}(n,K_{s,t})=O(t^{\frac{1}{s}}{n}^{2-\frac{1}{s}})$ has the correct dependence on large $t$. The main approach is to construct random multi-hypergraph via a variant of random algebraic method.

arXiv commentAccepted to European Journal of Combinatorics

References in corpus (6)

• Further applications of the Container Method
• A bound on the number of edges in graphs without an even cycle
• Graphs with few paths of prescribed length between any two vertices
• Turán numbers for $K_{s,t}$-free graphs: topological obstructions and algebraic constructions
• Some extremal results on hypergraph Turán problems
• Turán numbers of theta graphs

Cited by in corpus (1)

• A polynomial resultant approach to algebraic constructions of extremal graphs