Some tight lower bounds for Turán problems via constructions of multi-hypergraphs
Zixiang Xu Tao Zhang Gennian Ge
math.CO 05C35, 05C65, 05C80




Adaptive Flight Control in the Presence of Limits on Magnitude and Rate
    Joseph E. Gaudio, Anuradha M. Annaswamy, Michael A. Bolender, and Eugene Lavretsky
J.E. Gaudio and A.M. Annaswamy are with the Department
of Mechanical Engineering, Massachusetts Institute of Technology, Cambridge,
MA, 02139 USA (email: jegaudio@mit.edu and aanna@mit.edu).
M.A. Bolender is with the Air Force Research Laboratory, WPAFB, OH, 45433 USA.
E. Lavretsky is with The Boeing Company, Huntington Beach, CA, 92647 USA (email: eugene.lavretsky@boeing.com).


    
=====================================================================================================================================================================================================================================================================================================================================================================================================================================================================================




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,…,s_r-1, then

    _r(n,K_s_1,s_2,…,s_r^(r))=Θ(s_r^1/s_1s_2⋯ s_r-1n^r-1/s_1s_2⋯ s_r-1).

For complete bipartite r-uniform hypergraphs, we prove that if s is sufficiently larger than t, we have

    _r(n,K_s,t^(r))=Θ(s^1/tn^r-1/t).

In particular, our results imply that the famous Kővári–Sós–Turán's upper bound (n,K_s,t)=O(t^1/sn^2-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.

Key words and phrases: Random algebraic construction, multi-hypergraphs.



AMS subject classifications: 05C35, 05C65, 05C80.







§ INTRODUCTION

The study of Turán problems is one of the essential ingredients in extremal graph theory. In 1907, Mantel <cit.> first showed that every n-vertex graph with more than n^2/4 edges contains a triangle. Later Turán <cit.> generalized this result to K_ℓ-free graphs for ℓ⩾ 4. For general graph H, Erdős and Stone <cit.> gave the asymptotic results for the Turán number (n,H). However, to determine the exact asymptotic results for (n,H) is challenging when H is a bipartite graph. Complete bipartite graphs and even cycles are two important objects when we study such degenerate Turán problems. For complete bipartite graphs, the result of Kővári, Sós and Turán <cit.> showed that (n,K_s,t)=O(n^2-1/s) for any integers t>s. When s=2,3, Erdős, Rényi and Sós <cit.> and Brown <cit.> gave the matched lower bounds respectively. For general values of s and t, Kollár, Rónyai and Szabó <cit.> indicated that ex(n,K_s,t)=Ω(n^2-1/s) when t⩾ s!+1 via norm graphs, and then this condition was improved to t⩾ (s-1)!+1 by Alon, Rónyai and Szabó <cit.>. Recently, Blagojević, Bukh and Karasev <cit.> gave a new type of K_s,t-free graph via topological obstructions and algebraic constructions. Then Bukh <cit.> established an elegant method, which is named random algebraic construction, to show that (n,K_s,t)=Ω(n^2-1/s) when t is sufficiently larger than s. From then on, the random algebraic method was applied to several Turán type problems, see <cit.>.

For even cycles, the extremal results of (n,C_2ℓ) were first studied by Erdős <cit.>, and then Bondy and Simonovits <cit.> gave a general upper bound (n,C_2ℓ)⩽ 100ℓ n^1+1/ℓ. Recently, Bukh and Jiang <cit.> improved the upper bound to (n,C_2ℓ)⩽ 80√(ℓ)logℓ n^1+1/ℓ, and this upper bound is the current record. However, the order of magnitude for (n,C_2ℓ) is unknown for any ℓ∉{2,3,5}, see <cit.>. For general ℓ∉{2,3,5,7}, the best known lower bounds for (n,C_2ℓ) were obtained by Lazebnik, Ustimenko and Woldar <cit.>, and the best known lower bound for (n,C_14) was shown in <cit.>.

Due to the similarity of theta graphs and even cycles, the Turán number of theta graphs have been studied recently. Let theta graph Θ_ℓ,t be a graph made of t internally disjoint paths of length ℓ connecting two endpoints. Since it is unclear whether (n,C_2ℓ)=Ω(n^1+1/ℓ) holds in general, the study of (n,Θ_ℓ,t) is of interest. Faudree and Simonovits <cit.> first showed the general upper bound (n,Θ_ℓ,t)=O_ℓ,t(n^1+1/ℓ). Recently, Conlon <cit.> showed the matched lower bounds when t is a sufficiently large constant. After that Bukh and Tait <cit.> studied the behavior of (n,Θ_ℓ,t) when ℓ is fixed and t is very large, and they further determined the dependence on t when ℓ is odd. When ℓ and t are relatively small, Verstraëte and Williford <cit.> showed that (n,Θ_4,3)⩾ (1/2-o(1))n^5/4, and this result is perhaps the evidence that the Turán number of the octagon is also of order n^5/4.

On the contrary to the simple graph cases, there are only a few results on hypergraph Turán problems. There are two ways of generalizing complete bipartite graphs to hypergraphs. The first one is complete r-partite r-uniform hypergraph K_s_1,s_2,…,s_r^(r). Mubayi <cit.> conjectured that ex_r(n,K_s_1,s_2,…,s_r^(r))=Θ(n^r-1/s_1s_2⋯ s_r-1), where s_1⩽ s_2⩽…⩽ s_r, and he proved this conjecture in certain situations. Recently, Ma, Yuan and Zhang <cit.> showed that if s_r is sufficiently larger than s_1,s_2,…,s_r-1, then this conjecture is true. The other object is complete bipartite r-uniform hypergraph K_s,t^(r). In <cit.>, Mubayi and Verstraëte showed some general bounds for _r(n,K_s,t^(r)) when s<t. More recently, Xu, Zhang and Ge <cit.> gave the lower bound _r(n,K_s,t^(r))=Ω(n^r-1/t) when s is sufficiently larger than t, and the general upper bound _r(n,K_s,t^(r))=O(s^1/tn^r-1/t) when s is large.

The Turán problem for cycles in hypergraphs has been investigated for so-called Berge cycles. Győri <cit.> first determined _3(n,C_3^B) for all n, then Bollobás and Győri <cit.> showed that _3(n,C_5^B)=O(n^3/2). Győri and Lemons <cit.> showed the general upper bounds _r(n,C_2ℓ^B)=O(n^1+1/ℓ) and _r(n,C_2ℓ+1^B)=O(n^1+1/ℓ) for all ℓ⩾ 2 and r⩾ 3. It is known in <cit.> that _r(n,C_4^B)=Θ(n^3/2) when 2⩽ r⩽ 6, but the order of magnitude is still unknown for r⩾ 7. It is widely open whether the general upper bounds are tight for all r,ℓ⩾ 3. For more extremal results of Berge cycles, we refer the readers to <cit.> and the references therein.

Since there are few exact asymptotic results of _r(n,C_2ℓ^B), we are interested in the generalization of theta graphs to hypergraphs. Let r-uniform Berge theta hypergraph Θ_ℓ,t^B be a set of distinct vertices x,y,v_1^1,⋯,v_ℓ-1^1,⋯,v_1^t, ⋯,v_ℓ-1^t and a set of distinct edges e_1^1,⋯, e_ℓ^1,⋯,e_1^t,⋯,e_ℓ^t such that {x,v_1^i}⊂ e_1^i, {v_j-1^i,v_j^i}⊂ e_j^i and {v_ℓ-1^i,y}⊂ e_ℓ^i for 1⩽ i⩽ t and 2⩽ j⩽ℓ-1. Recently, He and Tait <cit.> studied the Turán number _r(n,Θ_ℓ,t^B), in particular, they showed that for fixed ℓ and r, there is a large constant t such that _r(n,Θ_ℓ,t^B) can be determined in order of magnitude.

 As far as we know, the random algebraic method always requires one of some parameters to be very large, therefore determining the dependence on this large parameter is interesting. Inspired by Bukh-Tait's results on theta graph <cit.>, we investigate three important objects including complete r-partite r-uniform hypergraphs, complete bipartite r-uniform hypergraphs and Berge theta hypergraphs. Our main idea is to construct the random multi-hypergraphs via a variant of random algebraic method, and our main contributions in this paper are listed as follows.

  
    
  * Complete r-partite r-uniform hypergraphs:
    
   For any positive integers s_1,s_2,…,s_r-1 and r⩾ 2, when s_r is sufficiently large, we have
    
    _r(n,K_s_1,s_2,…,s_r^(r))=Ω(s_r^1/s_1s_2… s_r-1n^r-1/s_1s_2… s_r-1).


By the result of <cit.>, the dependence on large s_r is tight.

    
  * Complete bipartite r-uniform hypergraphs:

   In 2004, Mubayi and Verstraëte <cit.> considered a hypergraph extension of the complete bipartite graph. In this paper, we call it complete bipartite r-uniform hypergraph for simplicity. Recall the definition of complete bipartite r-uniform hypergraph as follows.

  Let X_1,X_2,…,X_t be t pairwise disjoint sets of size r-1, and let Y be a set of s elements, disjoint from ⋃_i∈ [t]X_i. Then K_s,t^(r) denotes the complete bipartite r-uniform hypergraph with vertex set (⋃_i∈ [t]X_i)∪ Y and edge set {X_i∪{y}:i∈ [t],y∈ Y}.

Using our tools, we obtain the following result.
    
 For any positive integers t and r⩾ 2, when s is sufficiently large, we have
    
    _r(n,K_s,t^(r))=Ω(s^1/tn^r-1/t).


By the result of <cit.>, the dependence on large s is tight.

As a corollary, both of Theorems <ref> and <ref> imply that the upper bound of Kővári, Sós and Turán <cit.> is tight for all sufficiently large t.


  For given positive integer s, when t is sufficiently large, we have
  
    (n,K_s,t)=Θ(t^1/sn^2-1/s).



    
  * Berge theta hypergraphs:

     For general ℓ, by the upper bound for (n,Θ_ℓ,t)=O_ℓ(t^1-1/ℓn^1+1/ℓ) in <cit.>, Gerbner, Methuku and Palmer <cit.> showed the following upper bound when t is sufficiently large.
  
    For fixed ℓ⩾ 2, when t is sufficiently large, we have
    
    _r(n,Θ_ℓ,t^B)=O_ℓ,r(t^r-1-1/ℓn^1+1/ℓ).

  
    However we do not know whether the general upper bound is tight. Using our tools, we can show a lower bound as follows.

    
    Let ℓ⩾ 2 be a fixed integer, when t is sufficiently large, we have
    
    _r(n,Θ_ℓ,t^B)=Ω_ℓ,r(t^1/ℓn^1+1/ℓ).

  
  

  The rest of this paper is organized as follows. In Section <ref>, we introduce some basic facts about random algebraic method. In Section <ref>, we use a variant of random algebraic method to construct various multi-hypergraphs and then prove our main results of complete r-partite r-uniform hypergraphs, complete bipartite r-uniform hypergraphs and Berge theta hypergraphs. Finally we conclude in Section <ref>, and provide some remarks and open problems on the main topics.



§ PRELIMINARIES OF RANDOM ALGEBRAIC METHOD

 Let t,r be positive integers with r⩾ 2, q be a sufficiently large prime power, and 𝔽_q be the finite field of order q. Let X^i=(X_1^i,X_2^i,…,X_t^i)∈𝔽_q^t for each i∈ [r]. Consider polynomials f∈𝔽_q[X^1,X^2,…,X^r] with rt variables over 𝔽_q. We say such a polynomial f has degree at most d in X^i, if each of its monomials has degree at most d with respect to X^i, that is,  (X_1^i)^α_1(X_2^i)^α_2⋯(X_t^i)^α_t satisfies ∑_j=1^tα_j⩽ d. Moreover, a polynomial f is called symmetric if exchanging X^i with X^j for every 1⩽ i⩽ j⩽ r does not affect the value of f. Let 𝒫_d⊆𝔽_q[X^1,X^2,…,X^r] be the set of all symmetric polynomials of degree at most d in X^i for every 1⩽ i ⩽ r.

 We use the term random polynomial to represent a polynomial chosen uniformly at random from 𝒫_d. Since the constant term of a random polynomial is chosen uniformly from 𝔽_q, one can easily show that
 
    ℙ[f(v_1,v_2,…,v_r)=0]=1/q

 for a random polynomial f and any fixed r-tuple (v_1,v_2,…,v_r).

In our constructions of random hypergraphs, the edges will appear when one polynomial or a system of polynomials vanishes, hence we can describe subhypergraphs as varieties. Let 𝔽̅_q be the algebraic closure of 𝔽_q, a variety over 𝔽̅_q is a set of the form
 
    W={x∈𝔽̅_q^t: f_1(x)=f_2(x)=⋯=f_s(x)=0}

 for given polynomials f_1,f_2,…,f_s. That is, a variety is the set of common roots of a set of polynomials. Let W(𝔽_q)=W∩𝔽_q, and we say that W has complexity at most M if the above parameters s,t and the maximum degree of the polynomials are all bounded by M.

 Now we introduce two important lemmas which will be useful in our constructions. The first lemma is the key insight of the random algebraic construction, which provides very non-smooth probability distributions. While the second lemma will help us calculate the probability in certain situations.

 
   Suppose W and D are varieties over 𝔽̅_q of complexity at most M which are defined over 𝔽_q. Then either |W(𝔽_q)∖ D(𝔽_q)|⩽ c_M or |W(𝔽_q)∖ D(𝔽_q)|⩾q/2, where c_M depends only on M.
 


    Given a set U⊆𝔽_q^tr, let V⊆𝔽_q^t be the set consisting of all points appeared as an element of an r-tuple in U. Suppose that |U|2<q, |V|2<q and |U|⩽ d. If f is a random polynomial chosen from 𝒫_d, then
  
    ℙ[f(u^1,u^2,…,u^r)=0,  ∀{u^1,u^2,…,u^r}∈ U]=q^-|U|.

 



§ CONSTRUCTIONS OF RANDOM MULTI-HYPERGRAPHS 

In this section, we will show some lower bounds for _r(n,𝒯) via constructions of random multi-hypergraphs. Here we illustrate our main idea briefly. We first construct a random multi-hypergraph by taking union of h random hypergraphs. Our goal is to show that averagely this multi-hypergraph contains many edges, with very few copies of 𝒯 and multiple edges. For different forbidden hypergraphs 𝒯, we will define the corresponding bad structures and estimate their number. Finally we will delete one vertex from each bad structure and delete all of the multiple edges to obtain a new hypergraph, which is 𝒯-free and has expected number of edges.

There are three major ingredients. First, the random multi-hypergraph is the union of several random hypergraphs, which are defined by some bounded-degree random polynomials. Hence Lemma <ref> can help us estimate the expectation of number of single edges and multiple edges, respectively. Second, since the independence between different random hypergraphs, Lemma <ref> still works when we need to estimate the expectation of number of some structures, though the edges of such structures in multi-hypergraph are from distinct original random hypergraphs. The third ingredient is that, since the random hypergraphs are defined by bounded-degree polynomials, we can define the bad structure in multi-hypergraph properly. Then we regard the set of bad structures as variety, Lemma <ref> can help us bound the expectation of number of the bad structures, combining the Markov's inequality.



 §.§ Complete r-partite r-uniform hypergraphs

In this subsection we consider the Turán number of complete r-partite r-uniform hypergraph K_s_1,s_2,…,s_r^(r). We construct the random multi-hypergraph based on the construction of <cit.>.


 For given integers s_1,s_2,…,s_r-1 and r, let b=∏_i=1^r-1s_i, t=∑_i=1^r-1s_i, s=b(t-1)+2 and d=bs. Let N=q^b, we pick a symmetric polynomial f from 𝒫_d uniformly at random. Then we define an r-uniform hypergraph 𝒢 on N vertices as following: the vertex set is a copy of 𝔽_q^b, and the r-tuple {v_1,v_2,…,v_r} forms an edge of 𝒢 if and only if f(v_1,v_2,…,v_r)=0.


We pick h independent random symmetric polynomials f_1,f_2,…,f_h from 𝒫_d uniformly, and denote their associated hypergraphs as 𝒢_1,𝒢_2,…,𝒢_h. Let 𝒢̅ be a multi-hypergraph which is the union of 𝒢_1,𝒢_2,…,𝒢_h. In the multi-hypergraph 𝒢̅, let T be a fixed labelled copy of K_s_1,s_2,…,s_r-1,1^(r) and denote its vertices as u and v_j^i for 1⩽ i⩽ r-1, 1⩽ j⩽ s_i such that v_1^i,v_2^i,…,v_s_i^i are in the same specified part. Fix a sequence of vertices w_1^i,w_2^i,…,w_s_i^i for 1⩽ i⩽ r-1, and these vertices form b distinct (r-1)-tuples according to the fixed labelled copy of T. Since every edge can be in one of h distinct original hypergraphs 𝒢_k, there are totally h^b types of given labelled T. Let p be a positive integer and W be the family of copies of T which contains the fixed sequence w_1^i,w_2^i,…,w_s_i^i in 𝒢̅ for 1⩽ i⩽ r-1. We call a sequence of vertices w_1^i,w_2^i,…,w_s_i^i a p-bad sequence, if the corresponding set W has size |W|⩾ p. Let B_p be the set of all p-bad sequences in 𝒢̅.


   There exist constants p and C depending on s_1,s_2,…, s_r-1,r such that
   
    𝔼[|B_ph^b|]⩽ Ch^bN^1-2/b.



  Fix a type I∈[h]^b, call a sequence of vertices {w_1^i,w_2^i,…,w_s_i^i : 1⩽ i⩽ r-1} a (p,I)-bad sequence if the corresponding set W_I has size |W_I|⩾ p, where p will be determined later. By the linearity of expectation, it suffices to prove that the expected number of (p,I)-bad sequences is O(N^1-2/b) since the total number of types is h^b.

  Now we focus on the size of W_I. It is difficult to estimate |W_I| directly, hence we consider the s-th moment of |W_I|. Note that |W_I|^s counts the number of ordered collections of s copies of T from W_I, and these copies of T may be the same, hence each member of such collections can be an element P in

    𝒦:={K_s_1,s_2,…,s_r-1,1^(r),K_s_1,s_2,…,s_r-1,2^(r),…,K_s_1,s_2,…,s_r-1,s^(r)}.

 For given P∈𝒦, let N_s(P) be the number of all possible ordered collections of s copies of T∈ W_I which appear in 𝒢̅ as a copy of P. Note that the number of unfixed vertices in P is |P|-t, so N_s(P)=O(n^|P|-t). The edge set of P can be written as
 
    E(P)=E(P_1)∪ E(P_2)∪⋯∪ E(P_h)

 according to the fixed type I, where E(P_i) consists of edges from the original hypergraph 𝒢_i, i=1,2,…,h. Since the random hypergraphs 𝒢_1,𝒢_2,…,𝒢_h are picked independently, by Lemma <ref>, we have
 
    𝔼[|W|^s]=∑_P∈𝒦N_s(P)∏_i=1^hq^e(P_i)=∑_P∈𝒦O(N^|P|-t)· q^b(|P|-t)=O(1).


For a fixed type I, W_I is a variety which consists of vertices x∈𝔽_q^b satisfying the system of b equations f_k(w_j_1^1,w_j_2^2,…,w_j_r-1^r-1,x)=0 for all 1⩽ i⩽ r-1 and 1⩽ j_i⩽ s_i, where the choice of k for certain edge (w_j_1^1,w_j_2^2,…,w_j_r-1^r-1,x) only depends on the fixed type I. Note that every random polynomial f_k(w_j_1^1,w_j_2^2,…,w_j_r-1^r-1,x) is chosen from 𝒫_d, we have that W_I has complexity at most bs. By Lemma <ref>, either |W_I|⩽ c_I or |W_I|⩾q/2. Then we can use the Markov's inequality to bound the probability as

    ℙ[|W_I|> c_I]=ℙ[|W_I|⩾q/2]=ℙ[|W_I|^s⩾ (q/2)^s]⩽𝔼[|W_I|^s]/(q/2)^s=O(1)/q^s.

Let p=max_I∈ [h]^bc_I, the expected number of (p,I)-bad sequences is at most t!N^t·O(1)/q^s=O(N^1-2/b). By the linearity of expectation, Lemma <ref> follows since the total number of types is h^b.


Now we are ready to prove our main result of complete r-partite r-uniform hypergraphs.

   Let 𝒢̅ be the multi-hypergraph defined as above. It is easy to see the expected number of edges in 𝒢̅ is h/qNr. Let e_M be the number of multiple edges, we can bound the expected number of e_M as
  
    𝔼[e_M]⩽Nr∑_i=2^hhiq^-i=O(N^r-2/b).

  Moreover, by Lemma <ref>, the expected number of ph^b-bad sequences is at most Ch^bN^1-2/b. We remove all of the multiple edges and remove one vertex from each ph^b-bad sequence to obtain a new hypergraph 𝒢', since each vertex is contained in at most O(N^r-1) edges, hence the expected number of edges in 𝒢' is at least
  
    h/qNr-Nr∑_i=2^hhiq^-i-O(N^r-1)Ch^bN^1-2/b.

  When s_r is sufficiently large, we choose h=(s_r/p)^1/b, then there exists a K_s_1,s_2,…,s_r^(r)-free hypergraph with Ω(s_r^1/s_1s_2… s_r-1n^r-1/s_1s_2… s_r-1) edges, the proof of Theorem <ref> is finished.





 §.§ Complete bipartite r-uniform hypergraphs

In this subsection, we consider the Turán number of complete bipartite r-uniform hypergraph K_s,t^(r). We still take advantage of the construction in <cit.>.


  For given integers t and r, let N=q^t, m=(r-1)t^2-t+2, and d=mt, we pick a symmetric polynomial f from 𝒫_d uniformly at random. Then we define an r-uniform hypergraph ℋ on N vertices as following: the vertex set is a copy of 𝔽_q^t, and the r-tuple {v_1,v_2,…,v_r}∈𝔽_q^tr forms an edge of ℋ if and only if f(v_1,v_2,…,v_r)=0.

We then choose h independent random symmetric polynomials f_1,f_2,…,f_h from 𝒫_d uniformly, and denote their associated hypergraphs as ℋ_1,ℋ_2,…,ℋ_h. Let ℋ̅ be a multi-hypergraph which is the union of ℋ_1,ℋ_2,…,ℋ_h. In the multi-hypergraph ℋ̅, let R be a fixed labelled copy of K_1,t^(r), and we denote its vertices as a and u_j^i for 1⩽ j⩽ t and i∈ [r-1] such that u_j^1,u_j^2,…,u_j^r-1 form t distinct (r-1)-tuples corresponding to the fixed labelled copy of R. Since each edge of R can belong to one of h distinct original hypergraphs ℋ_k, there are in total h^t types of given labelled copy of R. Now fix any sequence of vertices w_j^i for 1⩽ j⩽ t and i∈ [r-1] in ℋ̅.  Let W be the family of copies of R in ℋ̅ such that w_j^i corresponds to u_j^i for all 1⩽ j⩽ t and i∈ [r-1]. We say such a sequence p-bad if the corresponding set W satisfies |W|⩾ p. Let B_p be the set of all p-bad sequences in the multi-hypergraph ℋ̅.


    There exist constants p=p(t,r) and C=C(t,r) such that
   
    𝔼[|B_ph^t|]⩽ Ch^tq^t-2.




Fix a type J∈[h]^t, call a sequence of vertices {w_j^1,w_j^2,…,w_j^r-1 : 1⩽ j⩽ t} a (p,J)-bad sequence if the corresponding set W_J has cardinality |W_J|⩾ p with p to be determined later. In the following we will prove that the expected number of (p,J)-bad sequences is O(q^t-2).


 We prefer to bound the value of |W_J|^m rather than estimate |W_J| directly. Note that |W_J|^m counts the number of ordered collections of m copies of R from W_J, where these copies of R may be identical. So each member of such collections can be an element L in

    ℒ:={K_1,t^(r),K_2,t^(r),…,K_m,t^(r)}.

For given L∈ℒ, denote N_m(L) as the total number of all possible ordered collections of m copies of R∈ W_J, which could appear in ℋ̅ as a copy of L. Note that the number of unfixed vertices in L is |L|-t(r-1), so N_m(L)=O(q^t(|L|-t(r-1))). On the other hand, according to the type J∈[h]^t, the edge set E(L) can be written as

    E(L)=E(L_1)∪ E(L_2)∪⋯∪ E(L_h),

where E(L_i) consists of edges from the original hypergraph ℋ_i, i=1,2,…,h. Since the random hypergraphs ℋ_1,ℋ_2,…,ℋ_h are picked independently, by Lemma <ref>, we have

    𝔼[|W_J|^m]=∑_L∈ℒN_m(L)∏_i=1^hq^-e(L_i)=∑_L∈ℒO(q^t(|L|-t(r-1)))q^-e(L)=O(1).

Note that W_J is a variety which consists of vertices x∈𝔽_q^t satisfying the system of t equations

    f_k(w_j^1,w_j^2,…,w_j^r-1,x)=0

  for 1⩽ j⩽ t. The choice of k is dependent on the fixed type J, and f_k is the random polynomial used to define random hypergraph ℋ_k. It is easy to check that for each k∈ [h], the random polynomial f_k(w_j^1,w_j^2,…,w_j^r-1,x) has degree at most d, hence the variety W_J has complexity at most d. Then by Lemma <ref>, either |W_J|⩽ c_J or |W_J|⩾q/2, where c_J is dependent on d and the type J. With the Markov's inequality, we obtain that
  
    ℙ[|W_J|> c_J]=ℙ[|W_J|⩾q/2]=ℙ[|W_J|^m⩾ (q/2)^m]⩽𝔼[|W_J|^m]/(q/2)^m=O(1)/q^m.

  Set p=max_J∈ [h]^tc_J, the expected number of (p,J)-bad sequences is at most (t(r-1))!N^t(r-1)·O(1)/q^m=O(q^t-2). Since the number of types J∈ [h]^t is h^t, then Lemma <ref> follows by the linearity of expectation.


Now we are ready to prove the main result of complete bipartite r-uniform hypergraphs.


  Let ℋ̅ be the random multi-hypergraph defined as above. Then by Lemma <ref>, the expected number of edges in ℋ̅ is h/qNr. Let e_M be the number of multiple edges, we can bound the expected number of e_M as
  
    𝔼[e_M]⩽Nr∑_i=2^hhiq^-i=O(N^r-2/t).

    As we have shown in Lemma <ref>, the expected number of ph^t-bad sequences is at most Ch^tq^t-2. We remove all of the multiple edges and remove one vertex from each ph^t-bad sequence to obtain a new hypergraph ℋ', since each vertex is contained in at most O(N^r-1) edges, hence the expected number of edges in ℋ' is at least
  
    h/qNr-Nr∑_i=2^hhiq^-i-O(N^r-1)Ch^tq^t-2.

  When s is sufficiently large, let h=(s/p)^1/t, then there exists a K_s,t^(r)-free hypergraph with Ω(s^1/tn^r-1/t) edges. The proof of Theorem <ref> is finished.





 §.§ Berge theta hypergraphs

 Now we define a random hypergraph model that we will use in our construction.

 
  For given integers r and ℓ, let d=rℓ^2 and N=q^ℓ, we pick ℓ(r-1)-1 symmetric polynomials f_1,f_2,…,f_ℓ(r-1)-1 from 𝒫_d uniformly at random. Let ℱ be an r-partite r-uniform hypergraph ℱ on rN vertices as following: the vertex set V(ℱ)={V_1,V_2,…,V_r} is r distinct copies of 𝔽_q^ℓ, and for v_i∈ V_i, 1⩽ i⩽ r, the r-tuple {v_1,v_2,…,v_r} forms an edge of ℱ if and only if
   
    f_1(v_1,v_2,…,v_r)=f_2(v_1,v_2,…,v_r)=⋯ =f_ℓ(r-1)-1(v_1,v_2,…,v_r)=0.

 

  We pick h random hypergraphs ℱ_1,ℱ_2,…,ℱ_h independently and let ℱ̅ be a multi-hypergraph which is the union of the ℱ_i. For the random multi-hypergraph ℱ̅ and positive integer p, we say that a pair of vertices x,y is p-bad if there are at least p Berge paths of length at most ℓ between x and y. Now we need to bound the number of ph^ℓ-bad pairs in ℱ̅.

 
   Let B_ph^ℓ be the set of all ph^ℓ-bad pairs in ℱ̅, there exist constants p=p(r,ℓ) and C=C(r,ℓ) such that
   
    𝔼[|B_ph^ℓ|]⩽ Ch^ℓq^ℓ(2-r).

 

 
   Let ℓ_0⩽ℓ be an integer and K=(k_1,k_2…,k_ℓ_0)∈ [h]^ℓ_0 be a fixed type. A Berge path made of edges e_1,e_2,…,e_ℓ_0 is of type (k_1,k_2,…,k_ℓ_0) if e_j∈ E(ℱ_k_j) for 1⩽ j⩽ℓ_0. For some fixed type K=(k_1,k_2,…,k_ℓ_0)∈ [h]^ℓ_0, we say that a pair of vertices x,y is (p,K)-bad if there are at least p Berge paths of type K between x and y. Since the total number of types is ∑_ℓ_0⩽ℓh^ℓ_0⩽ℓ h^ℓ, we then show that for each fixed type K, there is a constant p=p(r,ℓ) such that the expected number of (p/ℓ,K)-bad pairs is O_r,ℓ(q^ℓ(2-r)).

   The first step is to estimate the expected number of short Berge paths between pairs of vertices. Let x and y be fixed vertices in ℱ̅ and K=(k_1,k_2,…,k_ℓ_0) be a fixed type. Denote S_K as the set of Berge paths of type K between x and y. It is difficult to estimate |S_K| directly, hence we consider the value of |S_K|^rℓ, which counts the number of ordered collections of rℓ Berge paths of type K from x to y. These Berge paths can be overlapping or
identical, and the total number of hyperedges in any collection of rℓ paths is at most eℓℓ_0.

      Let P_ℓ_0,m be the number of collections of Berge paths between x and y such that their union has m edges in total. Note that the edge set of any particular collection Y_m with m edges in ℱ̅ can be written as
      
    E(Y_m)=E(Y_m,1)∪ E(Y_m,2)∪⋯∪ E(Y_m,h)

      according to the type K, where E(Y_m,i) consists of edges from the original hypergraph ℱ_i, i=1,2,…,h. Since the random hypergraphs ℱ_1,ℱ_2,…,ℱ_h are picked independently, by Lemma <ref>, we obtain that for m⩽ rℓ^2, the probability of any particular collection Y_m with m edges is contained in ℱ̅ is ∏_i=1^hq^e(Y_m,i)(1-ℓ(r-1))=q^m(1-ℓ(r-1)). Hence, we obtain that
   
    𝔼[|S_K|^rℓ]=∑_m=1^rℓ^2P_ℓ_0,mq^m(1-ℓ(r-1)).

   We use the argument of He and Tait <cit.>, which showed that
   
    P_ℓ_0,m=O_ℓ_0,r(q^m(ℓ_0(r-1)-1)).

Hence we obtain that

    𝔼[|S_K|^rℓ]=∑_m=1^rℓ^2P_ℓ_0,mq^m(1-ℓ(r-1))⩽∑_m=1^rℓ^21=C_K,

where the last inequality holds since ℓ_0⩽ℓ.

In the next step, we will show that |S_K| is either bounded by some constant or is at least q/2. However there is no fixed set of polynomials whose set of common roots is exactly S_K, hence it is difficult to write S_K as a variety directly. We need to analyse the set S_K as follows.

By the definition of Berge path, each Berge path of length ℓ_0 in S_K is a sequence of core vertices and edges such as (x,e_1,v_1,e_2,…,v_ℓ_0-1,e_ℓ_0,y). We can partition the set of Berge paths into which partite set each core vertex v_i is in. Hence for fixed type K, S_K can be partitioned into disjoint sets depending on which partite set each core vertex belongs to. Denote S_t_1,t_2,…,t_ℓ_0-1 as the set of Berge paths from x to y such that the i-th core vertex v_i∈ V_t_i. If we view σ as ℓ_0-1 tuple from [r]^ℓ_0-1, then we can write S_K as

    S_K=⋃_σ∈ [r]^ℓ_0-1S_K,σ,

and obviously it is a disjoint union.

Fix any S_K,σ, we denote the core vertices in an arbitrary Berge path of length ℓ_0 as v_1,v_2,…,v_ℓ_0-1 and the non-core vertices in edge e_j as w_1^k_j,w_2^k_j,…,w_r-2^k_j, where edge e_j is in ℱ_k_j. Here we need to make sure that the non-core vertices are ordered based on their partite sets, that is, if w_s_1^i∈ V_t_1 and w_s_2^i∈ V_t_2, where s_1<s_2, then t_1<t_2.

Now we define the variety T_K,σ as

    {z∈𝔽_q^ℓ_0(r-1)-1 : f_i,1^k_1(z)=f_i,2^k_2(z)=⋯=f_i,ℓ_0^k_ℓ_0(z)=0, 1⩽ i⩽ℓ_0(r-1)-1},

where f_i,j^k_j is the j-th random polynomial used to define ℱ_k_j and z∈𝔽_q^ℓ_0(r-1)-1 runs over sequence (v_1,…,v_ℓ_0-1,w_1^k_1,…,w_r-2^k_1,…,w_1^k_ℓ_0,…,w_r-2^k_ℓ_0). Note that each z is a vector ordered with the core vertices first and the non-core vertices after.

We then write the polynomials f_i,1^k_1(z)=f_i,2^k_2(z)=⋯=f_i,ℓ_0^k_ℓ_0(z) more accurately as follows.

  f_i,1^k_1(z)    = f_i^k_1(x,v_1,w_1^k_1,…,w_r-2^k_1), 

  f_i,2^k_2(z)    = f_i^k_2(v_1,v_2,w_1^k_2,…,w_r-2^k_2), 

       ⋯

  f_i,ℓ_0^k_ℓ_0(z)    = f_i^k_ℓ_0(v_ℓ_0-1,y,w_1^k_ℓ_0,…,w_r-2^k_ℓ_0),

where 1⩽ i⩽ℓ_0(r-1)-1. Observe that when σ is fixed, the order of all non-core vertices is fixed, hence we also fix the order of arguments given to f_i^k_j according to σ. For example, suppose v_ℓ_0-1∈ V_1 and y∈ V_3, then we write f_i,ℓ_0^k_ℓ_0(z) as

    f_i,ℓ_0^k_ℓ_0(z)=f_i^k_ℓ_0(v_ℓ_0-1,w_1^k_ℓ_0,y,w_2^k_ℓ_0…,w_r-2^k_ℓ_0).

It is easy to see that S_K,σ⊂ T_K,σ. However T_K,σ contains not only all the Berge paths in S_K,σ but also some degenerate walks which are not Berge paths, hence to obtain S_K,σ we need to exclude the walks that are not Berge paths. If T_K,σ contains a degenerate walk x=v_0,v_1,v_2,…,v_ℓ_0-1,v_ℓ_0=y, define

    D_a,b≜ T_K,σ∩{v_0,…,v_ℓ_0,w_1^k_1,…, w_r-2^k_ℓ_0: v_a=v_b},

for 0⩽ a<b⩽ℓ_0 and let D≜⋃_a,bD_a,b. We claim that D is a variety since the union of varieties is a variety, and the complexity of D is bounded.

Now we can use Lemma <ref> to analyse S_K,σ=T_K,σ∖ D. For arbitrary type K and σ∈ [r]^ℓ_0-1, there exists a constant c(K,σ) which is dependent on K and σ, such that either |S_K,σ|⩽ c(K,σ) or |S_K,σ|⩾q/2. Note that |S_K|=∑_σ∈ [r]^ℓ_0-1|S_K,σ|, if there exists a σ such that |S_K,σ|>c(K,σ), then |S_K|⩾|S_K,σ|⩾q/2, otherwise |S_K|⩽ c(K,ℓ_0,r) for some constant c(K,ℓ_0,r) which is dependent on ℓ_0 and r. With the Markov's inequality, we obtain that

    ℙ[|S_K|> c(K,ℓ_0,r)]=ℙ[|S_K|⩾q/2]=ℙ[|S_K|^rℓ⩾(q/2)^rℓ]⩽𝔼(|S_K|^rℓ)/(q/2)^rℓ=C_K/(q/2)^rℓ=O_ℓ_0,r(q^-rℓ).

Let p≜ℓmax_ℓ_0⩽ℓc(K,ℓ_0,r), then we have the expected number of (p/ℓ,K)-bad pairs is at most (rN)^2C_K/(q/2)^rℓ=O_r,ℓ(q^ℓ(2-r)). The proof of Lemma <ref> is finished by linearity of expectation.



When ℓ⩾ 2, let ℱ̅ be a multi-hypergraph defined as above. By Lemma <ref>, there are constants p=p(r,ℓ) and C=C(r,ℓ) such that the expected number of ph^ℓ-bad pairs is at most Ch^ℓq^ℓ(2-r). Let ℱ be obtained from ℱ̅ by removing all of the multiple edges.

Since ℱ_1,ℱ_2,…,ℱ_h are independent random hypergraphs, by Lemma <ref>, the expected number of edges in ℱ̅ is hq^ℓ+1=h(N/r)^1+1/ℓ. Let Y be the number of multiple edges, we can bound its expected number as following

    𝔼[Y]⩽ N^r∑_i=2^hhi(1/q^ℓ(r-1)-1)^i=o(N).

Then we can remove all ph^ℓ-bad pairs in ℱ to obtain a new hypergraph ℱ'. Since each vertex is in at most O(n^r-1) edges, at most O(n^r-1)|B_ph^ℓ| edges are removed.
  Therefore the expected number of edges in ℱ' is at least
  
    𝔼[e(ℱ')]⩾ h(N/r)^1+1/ℓ-2N^r-1𝔼[|B_ph^ℓ|]-N^r∑_i=2^hhi(1/q^ℓ(r-1)-1)^i.

When t is sufficiently large, let h=(t/p)^1/ℓ, then there exists a hypergraph ℱ' which is Θ_ℓ,t^B-free with Θ(n) vertices and Ω_r,ℓ(t^1/ℓn^1+1/ℓ) edges.





§ CONCLUDING REMARKS

In this paper, we mainly consider how the specified large parameter of forbidden hypergraph ℋ affects the Turán number _r(n,ℋ). Using a variant of random algebraic method, we determine the dependence on such specified large constant for Turán number of complete r-partite r-uniform hypergraph and complete bipartite r-uniform hypergraph. In particular, our results can be reduced to the result of complete bipartite graph, which implies the dependence of  Kővári–Sós–Turán's upper bound on large t is correct.

However, we fail in determining whether the upper bound  _r(n,Θ_ℓ,t^B)=O_ℓ,r(t^r-1-1/ℓn^1+1/ℓ) is tight when t is large. We strongly believe this upper bound is tight, for instance, the results of Gerbner, Methuku and Vizer <cit.> determined the asymptotics for _3(n,Θ_2,t^B)=(1+o(1))1/6(t-1)^3/2n^3/2. Moreover, for some relatively small ℓ and t, determining _r(n,Θ_ℓ,t^B) is also of great interest.




§ ACKNOWLEDGEMENT

The authors express their gratitude to the anonymous reviewers for the detailed and constructive comments which were very helpful for the improvement of the presentation of this paper.



abbrv

