The Extremal Problems In Combinatorics

Turán type of problems of hypergraphs is one of the core problems in extremal graph theorem.Given integers r≥2,n≥1 and a family F of r-uniform hypergraphs,the Turán number ex(n,F)of F is the maximum number of edges in an F-free r-uniform hypergraphs on n vertices.The Turán density of F is defined as π(F)=limn→∞ex(n,F)/(rn).In 1941,Turán determined the Turán number of all complete graphs.Erd?s-Stone-Simonovits determined asymptotic values of Turán densities of all graphs except for bipartite graphs.However,there are few results for hypergraphs.In fact,we do not know any Turán densities of complete r-uniform hypergraphs for r≥ 3.Denote ∏∞(r)={π(F):F is a family of r-uniform graphs},∏fin(r)={π(F):F is a finite family of r-uniform graphs} and ∏t(r)={π(F):F is a family of runiform graphs and |F|≤t}.Erd?s-Stone-Simonovits showed that ∏∞(2)=∏fin(2)=∏1(2)={0,1/2,2/3,…,l-1/l,…}.Inspired by this,Chung-Graham conjectured that ∏fin(r)is composed of rational numbers.Later,Baber-Talbot,Pikhurko showed that ∏3(3),∏fin(r)contains an irrational number,respectively.In the same paper,Baber-Talbot asked whether ∏1(r)contains an irrational number.We prove that ∏1(3)contains an irrational number by using the Lagrangian method,answering the question of Baber and Talbot.The Lagrangian method is a useful tool in the study of Turán type of problems.Given an r-uniform hypergraph F,the Lagrangian density of F is πλ(F)=sup{r!λ(G):G is F-free}.Frankl-R?dl,Sidorenko and Pikhurko found that there is a close relationship between the Lagrangian density of hypergraphs and its Turán density:Frankl-R?dl,Sidorenko showed that π(F)≤πλ(F),and Pikhurko showed that π(F)=π(ET(F)),where ET(F)is the extension of F.It is clear that determining the Lagrangian densities of hypergraphs is very helpful for understanding the Turán densities,and on the other hand,determining the Lagrangian densities of hypergraphs is a challenging problem.We first obtain the Lagrangian densities of short hypergraph cycles in this dissertation.By the definition of Lagrangian density,we know that πλ(F)≥r!λ(K|V(F)|-1r).We show that some hypergraphs F satisfy πλ(F)=r!λ(K|V(F)|-1r).We call such a hypergraph λ-perfect hypergraph.In this dissertation we show that:the disjoint union of some λ-perfect hypergraph and some non-λ-perfect hypergraph is λ-perfect,the disjoint union of any λ-perfect hypergraph and some λ-perfect hypergraph is λ-perfect.Hence,we obtain Lagrangian densities of many hypergraphs.There is a close relationship between the jumping number and Turán density.A real number α∈[0,1)is a jump for a positive integer r,if there exists ?>0 satisfying ∏∞(r)∩(α,α+?)=?.Erd?s conjectured that any α∈[0,1)is a jump for integer r≥2.Frankl-R?dl gave an counterexample by using the Lagrangian method.Note that Erd?s showed that every number in[0,r!/rr)is a jump for r≥3.He asked:whether r!/rr is a jump for r≥3?What is the smallest non-jump?In this dissertation,we improve the results of Frankl-Peng-R?dl-Talbot and give a smaller non-jump.Note that there was no know on irrational non-jump before,we give the first irrational non-jump in this dissertation.