Lagrangian And Turán Numbers Of Hypergraph

Turán problems are central to the development of extremal combinatorics.Given a positive integer n and an r-uniform hypergraph F,the Turán number ex(n,F)is the maximum number of edges in an F-free r-uniform hypergraph on n vertices.The Turán density of F is defined as ?(F)= limn??.ex(n,F)—(nr)How to de-termine Turán numbers and Turán densities of hypergraphs?This is a challenging extremal problems in combinatorial mathematics.For ordinary graphs(r= 2)the picture is fairly complete.In 1941,Turán solved the case when F = Kt is a,com-plete graph on t vertices.This result inspired the development of Extremal Graph Theory.For general graphs F,Erdos-Stone-Simonovits showed that:if x(F)=t,then ex(n,F)=1-2(1-1—t-1)n2+o(n2).In 1961,Turán posed the natural question of determining ex(n,KTt),where t>r>2,KTt is a complete r-uniform hypergraph on t vertices.To date,no case of this question has been cormpletely solved,even asymptotically.For hypergraphs,there are very few results on this problem.Lagrangian is an important tool in the study of the Turán problem.The La-grangian density of F is ???F)= sup?r!?(G):G is F-free}.The Lagrangian den-sity of an r-graph is closely related to its Turán density.Sidorenko observed that?(F)???(F)and Pikhurko observed that ?(F)= ??(F)if every pair of vertices in F is contained in an edge of F.Recently,Lagrangian densities of hypergraphs and Turán numbers of their extensions have been studied actively.Determining the Lagrangian density of hypergraphs is an interesting and challenging problem.In 2013,by the analysis of the structure on intersecting graphs,Hefetz-Keevash de-termined the Lagrangian density of a 3-uniform matching of size 2,i.e.,{123,456},and applied it to obtained the the Turán number of its extension.In this paper,we obtain the Lagrangian density of the 3-uniform graph {123,234}(?)M3t for t ?1,i.e.,the 3-uniform graph spanned by the disjoint union of a 3-uniform tight path of length 2 and a 3-uniform matching of size t.Applying it,we get the Turán number of its extension,and show that the unique extremal hypergraph is the balanced complete(3t+3)-partite 3-uniform hypergraph on n vertices.In 1965,Motzkin and Straus provided a connection between the order of a maximum clique in a graph G and the Lagrangian of G,Applying the connection,they gave a new proof of Turán's theorem.However,the obvious generalization of Motzkin-Strous' result to hypergraphs is false.In fact,the Lagrangian of a hypergraph is not always the same as the Lagrangian of its maximum cliques.In 2009,Rota Bulo and Pelillo extended the Motzkin-Straus result to r-uniform hypergraphs by establishing a one-to-one correspondence between local(global)minimizers of a family of homogeneous polynomial functions of degree r and the maximal(maximum)cliques of an r-uniform hypergraph.In 2013,Peng et al.gave a definition of the generalized Lagrangian of a non-uniform hypergraphs,and obtained an extension of a Motzkin-Straus type result to {1,2}-graphs.In this paper,we study similar optimization problems and obtain the connection to maximum cliques for {s,r?-hypergraphs and ?p,s,r}-hypergraphs,which can be applied to obtain upper bounds on the Turán densities of the complete {s,r}-hypergraphs and ?p,s,r}-hypergraphs.