Hypergraph Turán Numbers And Lagrangian Method

Turán type problems are central to the development of extremal combina-torics.The classical and fundamental result of Erdos-Stone-Simonovits gave the asymptotic values of Turán numbers of all non-bipartite graphs.For hypergraphs,we know very little about their Turán numbers.Hefetz and Keevash gave the La-grangian density of a 3-uniform matching with 2 edges and the Turán number of its extension.They conjectured the Lagrangian density of an r-uniform matching with 2 edges is obtained in the r-uniform hypergraph Snr that all edges intersecting with one fixed vertex and the Turán number of its extension is the number of edges of the blow-up of S(r-1)n/rr(clone the fixed vertex for about n/r times).We show this conjecture holds for r = 4.We also obtained the Lagrangian density of the 3-uniform linear path of length 3,length 4 or the disjoint union of a linear path of length 2 and a matching of arbitrary size,and the Turán numbers of the extensions and show the uniqueness of the extremal 3-uniform hypergraphs.Lagrangian method has been an important tool in Turán type problems.An r-uniform graph G is dense if and only if every proper subgraph G' of G satis-fies ?(G')<?(G),where ?(G)is the Lagrangian of a hypergraph G.In 1980's,Sidorenko showed that ?(F),the Turán density of an r-uniform hypergraph F is r!multiplying the supremum of the Lagrangians of all dense F-hom-free r-uniform hypergraphs.This connection has been applied in estimating Turán density of hypergraphs.When r = 2,the result of Motzkin and Straus shows that a graph is dense if and only if it is a complete graph.However,when r ? 3,it becomes much harder to estimate the Lagrangians of r-uniform hypergraphs and to characterize the structure of all dense r-uniform graphs.In this dissertation,we give some suf-ficient and necessary conditions for 3-uniform graphs with given substructures to be dense.For example,if G is a 3-graph with vertex set[t]and m edges containing[t-1](3),then G is dense if and only if m ?(t-1/3)+(t-2/2)+1.We also give sufficient condition on the number of edges for a 3-uniform hypergraph containing a large clique minus 1 or 2 edges to be dense.In 1965,Motzkin-Straus established the connection between the maximum cliques and the Lagrangian of a graph.This connection gave a proof of the Turán's classical result on Turán densities of complete graphs.In 1980's,Sidorenko and,Frankl and Fiiredi further developed this method for hypergraph Turán problem-s.However,the connection between the Lagrangian and the maximum cliques of a graph cannot be extended to hypergraphs.In 2009,S.Rota Bulo and M.Pelillo defined a homogenous polynomial function of degree r determined by an r-uniform hypergraph and gave the connection between the minimum value of this polynomial function and the maximum cliques of an r-uniform hypergraph.In this dissertation,we provide a connection between the local(global)minimizers of non-homogeneous polynomial functions and the maximal(maximum)cliques of hypergraphs whose edges containing r-1 and r vertices.This connection can be applied to obtain an upper bound on the Turán densities of complete {r-1,r}-type hypergraphs.