The uniform Turán density of large stars
Ander Lamaison Zhuo Wu


Constituent Automorphism Decoding of Reed–Muller Codes
    Yicheng Qu, Amir Tasbihi, and Frank R. KschischangThe
authors are with the Edward S. Rogers Sr. Dept. of Electrical and
Computer Engineering, University of Toronto, 10 King's College Road,
Toronto, Ontario M5S 3G4, Canada.  Email: ,
, .  Submitted for
publication on July 19th, 2024.
    September 9, 2024
===============================================================================================================================================================================================================================================================================================



§ ABSTRACT 
We asymptotically resolve the the uniform Turán density problem for the large stars. In particular, we show that the uniform Turán density of the k-star S_k is k^2-5k+7/(k-1)^2 for k≥ 48, matching a lower construction by Reiher, Rödl and Schacht.


Introduction


Turán problems constitute one of the central areas of study in extremal combinatorics. Given an r-uniform hypergraph (or r-graph for short) F and a positive integer n, the extremal number (n,F) is the maximum number of edges in an r-graph F not containing F as a subgraph. The Turán density of F is the limit 

    π(F):=lim_n→∞(n,F)/nr.


While Turán problems on graphs are well-understood <cit.>, much less is known about Turán problems on hypergraphs. For example, the exact value of the Turán density of K_k^(r), the complete r-graph on k vertices, is not known for any k>r≥ 3. In fact, the Turán density of K_4^(3)-, which is obtained by removing an edge from K_4^(3), is currently unknown.

In the conjectured extremal constructions for most hypergraph Turán problems, the set of edges is distributed very unevenly among the vertices. For instance, there is a family of K_4^(3)-free 3-graphs whose density tends to 5/9 (conjectured to be the value of π(K_4^(3))). In each hypergraph in the family, the vertex set can be partitioned into three independent sets. This motivated Erdős and Sós <cit.> to propose studying Turán density problems with a condition on the edge distribution.


A 3-graph H is said to be (d,ε,)-dense
if any subset S⊆ V(H) contains at least d|S|3-ε|V(H)|^3 edges. 
The uniform Turán density (F) of a 3-graph F
is defined as the infimum of the values of d, 
for which there exists ε>0 and N such that 
every (d,ε,)-dense hypergraph
on at least N vertices
contains F as a subgraph.


In the last decade, a number of results about the uniform Turán density of 3-graphs have been published. The first non-zero value of  to be computed was (K_4^(3)-)=1/4, solving a conjecture of Erdős and Sós. This was first proved by Glebov, Král' and Volec <cit.> using flag algebras, and later by Reiher, Rödl and Schacht <cit.> using the hypergraph regularity method. The latter set of authors also characterized in <cit.> the 3-graphs F with (F)=0, and as a consequence, deduced that there does not exist a 3-graph F with (F)∈(0,1/27). 


Bucić, Cooper, Král', Mohr and Munha-Correia <cit.> determined the uniform Turán densities of all tight cycles of length at least 5. They showed that (C_ℓ^(3)) equals 0 if ℓ is divisible by 3, and 4/27 otherwise. Additionally, 3-graphs with uniform Turán density equal to 1/27 and 8/27 have also been found <cit.>. Further results can be found in a survey by Reiher <cit.>.




One simple hypergraph family whose uniform Turán density has been studied is stars. Let S_k be the 3-graph on k+1 vertices u,v_1, v_2, …, v_k, containing the edges uv_iv_j for all 1≤ i<j≤ k. We call this graph the k-star. For example, S_3 is just the graph K_4^(3)-. Despite the simplicity of their structure, attempts to extend the idea used to determine the uniform Turán density of K_4^(3)- to any larger star have been unsuccessful. The current best bounds were given by Reiher, Rödl and Schacht <cit.>, who showed that 
    k^2-5k+7/(k-1)^2≤(S_k)≤(k-2/k-1)^2.


In this paper we show that the lower bound is sharp for all large stars, and thereby asymptotically resolve the the uniform Turán density problem for the large stars.



(S_k)=k^2-5k+7/(k-1)^2 for all k≥ 48.




The key concept in the proof of Theorem <ref> is the notion of palette, introduced by Reiher <cit.> as a generalization of a construction of Rödl <cit.>.


A palette  is a pair (𝒞,𝒜), 
where 𝒞 is a finite set (whose elements we call colors) 
and a set of (ordered) triples of colors 𝒜⊆𝒞^3, 
which we call the admissible triples.
The density of  is d():=|𝒜|/|𝒞|^3.

We say that a 3-graph F admits a palette 
if there exists an order ≼ on V(F)
and a function φ:V(F)2→𝒞
such that for every edge uvw∈ E(F) with u≺ v≺ w
we have (φ(uv), φ(uw), φ(vw))∈𝒜.


Palettes can be used to give lower bounds on the uniform Turán density of 3-graphs. Indeed, if the 3-graph F does not admit the palette , then one can use an analogous of Rödl's construction to obtain a (d(),o(1),)-dense family of F-free hypergraphs, meaning that (F)≥ d(). For this reason, it is worth considering the largest density of a palette which is not admitted by F.


 The palette Turán density of a 3-graph F is
 
 
    (F):=sup{d(): palette, F does not admit }.



As discussed above, for every 3-graph F we have (F)≥(F). In <cit.>, the first author showed that equality always holds. This result will be the main tool in the proof of Theorem <ref>.


For every 3-graph F, we have (F)=(F).






  
Idea. The main technical step we develop to prove Theorem <ref> is transforming the hypergraph condition to a digraph condition (see  <ref>). We rely on a property of the structure of S_k: each edge uvw contains a pair of vertices which is not contained in any other edge.  That means that, when we consider the palette condition (φ(uv), φ(uw), φ(vw))∈𝒜, one of the three entries can be selected freely without affecting any other edge. For this reason it is enough to consider, for each 1≤ i<j≤ 3, the pairs of colors (a,b) for which there exists a triple (c_1, c_2, c_3)∈ such that c_i=a and c_j=b. 





  
Notation. For any palette =(, ), let _a^1, _a^2,_a^3 be the set of the triples in  with the first, second, third entry equal to a, respectively. The palette '_a, i.e, the palette obtained by removing the color a from  is 

    '_a=(∖{a},  (∖{a})^3∩).






Proof of Theorem <ref>



By Theorem <ref>, it is sufficient to show that (S_k)=k^2-5k+7/(k-1)^2. The lower bound was first shown to hold in <cit.>, here we will give a short proof for completeness.

Consider the palette =(𝒞,𝒜) with 𝒞={0, ⋯, k-2},

    𝒜={(x,y,z)|  x≠ y,   y≠ z,   z≢x+1k-1}.

It is easy to calculate that  has density k^2-5k+7/(k-1)^2. Now we prove that  does not admit S_k, which shows that (S_k)≥k^2-5k+7/(k-1)^2.

For contradiction, assume that there exist an order ≼ on V(F) and a function φ:V(F)2→𝒞
such that for every edge uvw∈ E(F) with u≺ v≺ w
we have (φ(uv), φ(uw), φ(vw))∈𝒜. By symmetry, assume that the order ≼ on V(F) is v_1≼⋯≼ v_t ≼ u≼ v_t+1⋯≼ v_k. Consider the following k elements:

    φ(uv_1)+1,⋯, φ(uv_t)+1,   φ(uv_t+1),  ⋯, φ(uv_k).


By the pigeonhole principle, at least two of them are the same modulo k-1. Now we have 3 cases:





  * φ(uv_i)+1=φ(uv_j)+1 for some i<j≤ t. Then (φ(v_iv_j), φ(v_iu), φ(v_ju))∉.


  * φ(uv_i)+1=φ(uv_j) for some i≤ t<j. Then (φ(v_iu), φ(v_iv_j), φ(uv_j))∉.


  * φ(uv_i)=φ(uv_j) for some t<i<j. Then (φ(uv_i), φ(uv_j), φ(v_iv_j))∉.

This completes the proof of the lower bound.



 We then prove the upper bound. Indeed, suppose for the sake of contradiction that (S_k)>k^2-5k+7/(k-1)^2. Then there exist palettes with density greater than k^2-5k+7/(k-1)^2 not admitted by S_k. Let =(, ) be one such palette with the minimum number of colors. Removing any color from  must decrease the density of .   

Let ||=n. Given colors a,b∈, and i≠ j∈{1,2,3}, we say that (a,b) is (i,j)-good if there exists a triple (c_1, c_2, c_3)∈ such that c_i=a and c_j=b, otherwise (a,b) is (i,j)-bad.  Let d_i,j(a) denote the number of colors b such that (a,b) is (i,j)-good, and e_i,j(a)=d_i,j(a)/n. Moreover, define d_i,j'(a)=n-d_i,j(a), i.e, the number of colors b such that (a,b) is (i,j)-bad, and e'_i,j(a)=d'_i,j(a)/n. The following claim give an estimate on the lower bound of d_i,j(a).


    e_i,j(a)≥ 3d()-2 for all a∈ and all i≠ j∈{1,2,3}.



By symmetry, assume that i=1,j=2. Let '=(', ') be the palette obtained by removing the color a from . Then

    n^3d()=||
       =|'|+|∖'|
       = |'|+|_a^1|+|_a^2∖_a^1|+|_a^3∖(_a^1∪_a^2)|
       ≤ |'|+nd_i,j(a)+n(n-1)+(n-1)^2
       ≤ (n-1)^3d()+nd_i,j(a)+2n^2-3n+1,

where the last inequality uses the condition that removing any color from  decreases the density of . Hence,

    nd_i,j(a)
       ≥ (n^3-(n-1)^3)d()-2n^2+3n-1
       =d()(3n^2-3n+1)-2n^2+3n-1
       =(3d()-2)n^2+(3n-1)(1-d())
       ≥ (3d()-2)n^2,

which proves our claim.


In the next lemma we bound the density of the palette by e_i,j.



    d()≤1/4+1/2n∑_a∈∑_i≠ j∈{1,2,3}(e_i,j(a)-1/2)^2.



 Define

    X_1={(a,b,c)|(a,b,c)∈^3, for all d∈, (d,b,c)∉},
    
    X_2={(a,b,c)|(a,b,c)∈^3,for all d∈, (a,d,c)∉},
    
    X_3={(a,b,c)|(a,b,c)∈^3,for all d∈, (a,b,d)∉}.



Clearly  does not contain any element from X_1, X_2 or X_3, so by the inclusion-exclusion principle, we have 

    ||   ≤ |X_1∩X_2∩X_3|
       ≤ n^3-|X_1|-|X_2|-|X_3|+|X_1∩ X_2|+|X_1∩ X_3|+|X_2∩ X_3|.


 Note that (a,b,c)∈ X_1 is equivalent to (b,c) being (2,3)-bad, hence

    |X_1|=n∑_a∈d'_2,3(a)=n∑_a∈d'_3,2(a)=n/2(∑_a∈d'_2,3(a)+∑_a∈d'_3,2(a)).


Besides, (a,b,c)∈ X_1∩ X_2 is equivalent to (b,c) being (2,3)-bad and (a,c) being (1,3)-bad, hence

    |X_1∩ X_2|=∑_a∈d'_3,1(a)d'_3,2(a).


Using the same argument for X_2,X_3, we have


    ||   ≤ n^3-|X_1|-|X_2|-|X_3|+|X_1∩ X_2|+|X_1∩ X_3|+|X_2∩ X_3|
       ≤ n^3-n/2∑_a∈∑_i≠ jd'_i,j(a)+∑_a∈(d'_1,2(a)d'_1,3(a)+d'_2,1(a)d'_2,3(a)+d'_3,1(a)d'_3,2(a)),

which is equivalent to

    d()≤ 1+1/n∑_a∈(e'_1,2(a)e'_1,3(a)+e'_2,1(a)e'_2,3(a)+e'_3,1(a)e'_3,2(a)-1/2∑_i≠ je'_i,j(a)).


Note that we have the local inequality

    ab-1/2(a+b)=(a-1/2)(b-1/2)-1/4≤1/2((a-1/2)^2+(b-1/2)^2)-1/4,


Hence

    d()
       ≤ 
    1+1/n∑_a∈(e'_1,2(a)e'_1,3(a)+e'_2,1(a)e'_2,3(a)+e'_3,1(a)e'_3,2(a)-1/2∑_i≠ je'_i,j(a))
       ≤ 1+1/n∑_a∈∑_i≠ j∈{1,2,3}1/2(e'_i,j(a)-1/2)^2-3/4
       =1/4+1/2n∑_a∈∑_i≠ j∈{1,2,3}(e_i,j(a)-1/2)^2.









Now we want to use the condition that  does not admit S_k to bound e_i,j(a). To give a better characterization of the condition, we define a digraph D(V,E) as follows:


  * V=_1∪_2, which consists of two disjoint copies of . Besides, for each color a∈, let a^1 and a^2 denote the copies of a in _1 and _2.


  * For a pair of colors (a,b)∈^2, 


  * we add an edge a^1b^1 in _1 if (a,b) is (2,3)-good,

  * we add an edge a^2b^2 in _2 if (a,b) is (1,2)-good,

  * we add the edges a^1b^2 and b^2a^1 if (a,b) is (1,3)-good.

Here, we use ab to express the arc from a to b.



One important thing is to show that D is well-defined, i.e, D has no loop. Assume that D contains an edge a^1a^1, then (a,a) is (2,3)-good, hence there exists a triple (b,a,a)∈𝒜. Recall S_k be the 3-graph on k+1 vertices u,v_1, v_2, …, v_k, containing the edges uv_iv_j for all 1≤ i<j≤ k. We define a order ≼ on V(F) as v_1≼⋯≼ v_k ≼ u, and  construct a function 
φ:V(F)2→𝒞 such that φ(v_iv_j)=b, φ(v_iu)=a. Then, for every edge v_iv_ju∈ E(F) with 
v_i≼ v_j≼ u, we have (φ(ab), φ(ac), φ(bc))=(a,a,b)∈𝒜, a contradiction. Similarly,  D also cannot contains an edge a^2a^2, hence D is well-defined.




    D does not contain a transitive tournament on k vertices as a subgraph.




We prove the claim by contradiction. Assume that K is a transitive tournament on k vertices in D, and V(K)∩_1=K_1,V(K)∩_2=K_2. Let |K_1|=s, |K_2|=t. We can label the vertices of this transitive tournament ℓ_1^1, ℓ_2^1, …, ℓ_s^1, r_1^2, r_2^2, …, r_t^2 in such a way that we have the edge ℓ_i^1ℓ_j^1 for any 1≤ i<j≤ s and the edge r_i^2r_j^2 for any 1≤ i<j≤ t. By the definition of D, we can find some ℓ_ij such that (ℓ_i,j,ℓ_i,ℓ_j)∈, some m_ij such that (ℓ_i,m_ij,r_j)∈ and some r_ij such that (r_i,r_j,r_ij)∈. 

Now we show that  admits S_k, which is a contradiction. Note that s+t=k, to be convenient, assume the star S_k has vertices u,v_1,⋯,v_s,w_1,⋯,w_t. We define an order ≼ on V(S_k) as follows:


    v_1≼⋯≼ v_s≼ u ≼ w_1≼⋯≼ w_t.


We then construct  a function φ:V(S_k)2→𝒞
such that for every edge abc∈ E(F) with a≺ b≺ c
we have (φ(ab), φ(ac), φ(bc))∈𝒜. Define

    φ(uv_i)=ℓ_i,  φ(uw_i)=r_i,  φ(v_iv_j)=ℓ_ij,  φ(v_iw_j)=m_ij,  φ(w_iw_j)=r_ij.





By the definition of S_k, u∈{a,b,c}. Now we have 3 cases:




  * a=u,b=w_i, c=w_j. Then (φ(ab), φ(ac), φ(bc))=(r_i,r_j,r_ij)∈.


  * b=u,a=ℓ_i, c=w_j. Then (φ(ab), φ(ac), φ(bc))=(ℓ_i,m_i,j,r_j)∈, 


  * c=u,a=ℓ_i, c=ℓ_j. Then (φ(ab), φ(ac), φ(bc))=(ℓ_i,j,ℓ_i,ℓ_j)∈.





We then introduce a variation of the Caro-Wei theorem in digraph. It is similar to Theorem 4 in <cit.>.


Let H be a digraph on n vertices, which does not contain a transitive tournament on k vertices as a subgraph. For each vertex v, let m(v)=max{d^+(v), d^-(v)}. Then 
    ∑_v∈ V(H)1/n-m(v)≤ k-1.





We proceed by induction on k. The statement is clear for k=2, since H is the empty graph. Suppose that the statement holds for k-1. Let w be a vertex with the maximum value of m(w), and by symmetry assume that m(w)=d^+(w). Let S be the set of out-neighbors of w, and D[S] be the digraph induced by D in S. Then D[S] does not contain a transitive tournament on k-1 vertices, otherwise we could extend it by adding w. Let d^+_S(v) and d^-_S(v) denote the out-degree and in-degree of v in G_S, and let m_S(v)=max{d^+_S(v), d^-_S(v)}. Hence,





    ∑_v∈ v(H)1/n-m(v)   =∑_v∈ S1/n-m(v)+∑_v∈ V(H)∖ S1/n-m(v)
       ≤∑_v∈ S1/n-m(v)+∑_v∈ V(H)∖ S1/n-m(w)       (by the maximality of m(w))
       ≤∑_v∈ S1/n-m(v)+1
       ≤∑_v∈ S1/|S|-m_S(v)+1        (m(v)≤ m_S(v)+(n-|S|))
       ≤ k-1.        (by the induction hypothesis)





We then combine <ref> and <ref> to give an estimation of e_i,j. 

0.1 em

For each a∈, set 

    m_A(a)   =max{e_2,3(a), e_3,2(a)},     m_C(a)=max{e_1,2(a), e_2,1(a)}, 
    
    m_B(a)   =m_A(a)+e_1,3(a),          m_D(a)=m_C(a)+e_3,1(a).


For each a∈, set M_A(a)=1/1-m_A(a), M_C(a)=1/1-m_C(a). Consider the digraph D[_1]. For each a∈, the maximum of its in-degree and out-degree in D[_1] is m_A(a)n, so by Lemma <ref>, we have 

    ∑_a∈M_A(a)=∑_a∈1/1-m_A(a)≤ (k-1)n,

and the inequality is also true when we replace M_A(a) with M_C(a). 

0.15 em

Recall that m(v)=max{d^+(v), d^-(v)}. In D, for each a∈, m(a^1)=m_B(a)n, m(a^2)=m_D(a)n. Set M_B(a)=1/2-m_B(a), M_D(a)=1/2-m_D(a), then by Lemma <ref> again we have  

    ∑_a∈(M_B(a)+M_D(a))=∑_a∈(1/2-m_B(a)+1/2-m_D(a))≤  (k-1)n.




Now, by Lemma <ref>, we have


    d()
       ≤1/4+1/2n∑_a∈∑_i≠ j∈{1,2,3}(e_i,j(a)-1/2)^2 
       ≤1/4+1/2n∑_a∈(2(m_A(a)-1/2)^2+(m_B(a)-m_A(a)-1/2)^2)
       +1/2n∑_a∈(2(m_C(a)-1/2)^2+(m_D(a)-m_C(a)-1/2)^2).






Note that for all real numbers a,b we have the local inequality

    2(a-1/2)^2+(b-a-1/2)^2
       =(a-1/2)^2+1/2(b-1)^2+2(a-b/2)^2
       ≤ (a-1/2)^2+1/2(b-1)^2+4(k-2/k-1-a)^2+4(k-2/k-1-b/2)^2
       =f(a)+g(b),

where f(x)=(x-1/2)^2+4(k-2/k-1-x)^2, g(x)=1/2(x-1)^2+4(k-2/k-1-x/2)^2.

0.4 em

Substituting (<ref>) in (<ref>), we have

    d()
       ≤1/4+1/2n∑_a∈( f(m_A(a))+f(m_C(a))+g(m_B(a))+g(m_D(a)) )
       = 1/4+1/2n∑_a∈( f_1(M_A(a))+f_1(M_C(a))+g_1(M_B(a))+g_1(M_D(a)) ),

where  f_1(x)=f(1-1/x), g_1(x)=g(2-1/x). We can calculate that

    f_1(x)=5/x^2-(k+7)/(k-1)x+4/(k-1)^2+1/4,     g_1(x)=3/2x^2-(k+3)/(k-1)x+4/(k-1)^2+1/2.



Now we bound the four sums in (<ref>) separately.  The idea is to use a tangent-type local inequality.


For any x≥5(k-1)/k-3,

    f_1(x)≤(k-3)/(k-1)^3x+k^2-10k+21/(2k-2)^2.




The inequality is equivalent to (x-(k-1))^2((k-3)x-5(k-1))≥ 0.




By Claim <ref>, we have m_A(a)≥ 3d()-2 for every a∈, therefore 

    M_A(a)≥1/3-3d()≥(k-1)^2/9(k-2)≥5(k-1)/k-3


when k≥ 48. Hence, by Claim <ref> and (<ref>), we have

    ∑_a∈f_1(M_A(a))
       ≤∑_a∈((k-3)/(k-1)^3M_A(a)+k^2-10k+21/(2k-2)^2)
       ≤(k-3)/(k-1)^3(k-1)n+k^2-10k+21/(2k-2)^2n
       =n(k-3)^2/(2k-2)^2.


Similarly, we have

    ∑_a∈f(m_C(a)) ≤ n(k-3)^2/(2k-2)^2.




For any x≥3(k-1)/2k-6,

    g_1(x)≤4k-12/(k-1)^3x+k^2-10k+21/2(k-1)^2.




The inequality is equivalent to (2x-(k-1))^2((2k-6)x-3(k-1))≥ 0.


By Claim <ref>, we have m_B(a)≥ 6d()-4 for every a∈, then 


    M_B(a)≥1/6-6d()≥(k-1)^2/18(k-2)≥3(k-1)/2k-6

when k≥ 30. Similarly, M_D(a)≥3(k-1)/2k-6, hence by Claim <ref> and  (<ref>) we have

    ∑_a∈(g_1(M_B(a))+g_1(M_D(a))   ≤∑_a∈(4k-12/(k-1)^3(M_B(a)+M_D(a))+k^2-10k+21/(k-1)^2)
       ≤4k-12/(k-1)^3(k-1)n+k^2-10k+21/(k-1)^2n
       =n(k-3)^2/(k-1)^2. 8


Hence, putting together (<ref>), (<ref>), (<ref>) and (<ref>), we have

    d()   ≤1/4+1/2n∑_a∈( f(m_A(a))+f(m_C(a))+g(m_B(a))+g(m_D(a)) )
       ≤1/4+3(k-3)^2/4(k-1)^2
       =k^2-5k+7/(k-1)^2.



which finishes the proof.


Concluding remarks

Using computer calculations, one can show that the inequalities (<ref>), (<ref>) hold for k≥ 40, which means that <ref> is also true for k≥ 40. 





  
Acknowledgements

The authors want to thank Haoran Luo for computer calculation. The authors are also grateful to  Daniel Král, Hong Liu and Oleg Pikhurko for careful reading and some writing suggestions.


    



abbrv

