Generalized Turán Problems In Graphs And Hypergraphs

Extremal graph theory is one of the central branches of combinatorics.It has applications in many areas,such as theoretical computer science.Turan problem has always been an important and active topic in extremal graph theory.In 2016,Alon and Shikhelman initiated the systematic study of the generalized Turan problem.Since then,the generalized Turán problem has become one of the most popular topics in extremal graph theory.In this thesis,we study several generalized Turan problems in graphs and hypergraphs.Specifically,for fixed graphs(or hypergraphs)H and T,estimate the maximum number of copies of T in an n-vertex graph(or hypergraph)that contains no copy of H.The following is a brief introduction to the structure of the thesis:In Chapter 1,we introduce some basic definitions and symbols used in this thesis.Some background information about Turán problem,generalized Turán problem and Erd(?)s matching conjecture are included.In Chapter 2,we estimate the maximum number of copies of Kr in a Br,1-free graph,where Br,1 is the graph consisting of two copies of Kr that share exactly one vertex.By Zykov’s symmetrization and the Füredi’s structure theorem,the maximum number of copies of Kr and the unique extremal construction are determined.In Chapter 3,we determine the maximum number of edges in an sKrk-free r-partite k-uniform hypergraph by using the probabilistic argument and a linear programming result.For general graphs,we obtain the maximum number of t-cliques in an sKr-free r-partite graph.Here sKrk and sKr are the s vertex-disjoint r-cliques in k-uniform hypergraphs and graphs,respectively.In Chapter 4,we obtain the maximum number of t-cliques in a k-uniform hypergraph on n vertices with matching number at most s and n sufficiently large.Moreover,we generalize a result due to Huang,Loh and Sudakov,which is about the existence of rainbow matchings in edge-colored hypergraphs.In Chapter 5,by the cyclic permutation method of Katona and shifting method,we get the maximum number of edges in a k-uniform hypergraph on n vertices with matching number at most s and clique number at least q for n≥8k2s.