Turán Problem And Decomposition Number Problem Of Graphs And Hypergraphs

The emergence and development of graph theory has gone through hundreds of years.At present,the graph theory has spawned numerous research branches,and it has been widely used in many disciplines such as management,economics,physics and computer science,etc.Extremal graph theory is an important branch of graph theory.The classic extremal problem is Turán problem.Turán problem is to study the maximum number of edges in any the graph with fixed number of vertices,which doesn't contain some given graph as subgraph.An H-decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms a copy of H.The decomposition number of H is the smallest number?such that any graph admits an H-decomposition with at most?parts,when the number of its vertices is given.The decomposition number of graphs are closely related to the Turán problem of graphs,which are also research hotspots of extremal graph theory.As a natural generalization of graphs,hypergraphs model more general types of relations than graphs do.Therefore,the extremal problems of Turán number and decomposition number of hypergraphs are also significant research topics.This paper mainly studies the extremal problems of Turán number and decomposition number of graphs and hypergraphs,which consists of six chapters.It is organized as follows:In Chapter 1,we introduce the research progress of Turán problem and decomposition number problem of graphs and uniform hypergraphs,as well as the basic knowledge and related marks.In Chapter 2,we study the extremal graphs of blow-ups of C_s(k)(k?3,s?1).In recent years,the Turán problem of blow-up of graphs have been widely concerned.In2017,Glebov gave the Turán number for blow-up of paths,and characterized their extremal graphs.Subsequently,Liu gave the Turán numbers of blow-up of cycles and some trees,and characterized their extremal graphs.On this basis,we determine the extremal number and find the extremal graphs for the blow-ups of C_s(k)(k?3,s?1).At the same time,we find that this result can partially answer a question proposed by Simonovits:for any r?1 and p?2,characterize graphs whose unique extremal graph is of the form K_p-1?T_n-p+1,r.In Chapter 3,we study the Turán number for Berge-hypergraph.In recent years,some results about Tur'an number of Berge hypergraphs have emerged one after another.In2017,Gerbner and Palmer estimated the upper and lower bounds of Turán number of Berge complete bipartite graph.In 2020,Gerbner et al.gave the bounds of Turán number of Berge complete graph and Berge tree.They determined the r-uniform Turán number and extremum graph of Berge-k when r>k+2.On this basis,we first determine the Turán number of Berge-(k+1)K₂when r?k-1 or r?2k+2,characterize the extremal hypergraphs of Berge-(k+1)K₂,and establish bounds of the Turán number of Berge-(k+1)K₂for k?r?2k+1.Furthermore,we determine the bounds of the Turán number of Berge-F when F is a(k,p)-fan for k?2,p?3 and r?3.In Chapter 4,we study the decomposition number of the r-blow-up of C_k.In 2012,Pikhurko and Sousa proved that for a fixed graph H,if the color number of H satisfies?(H)?3,its decomposition number satisfies?(n,H)=ex(n,H)+o(n²).At the same time,they put forward a conjecture:for any graph H with chromatic number?(H)?3,there is an integer n₀=n₀(H)such that?(n,H)=ex(n,H)for all n?n₀.In this chapter,we show that Pikhurko-Sousa conjecture holds for the r-blow-up of C_kwhen k?3 and r?4.In Chapter 5,we study the decomposition number of hypertrees.In 2010,Sousa gave the asymptotic value of the decomposition number of H when H is a r-uniform hypergraph consisting of 2 hyperedges,and determined the exact value of its decomposition number in the special cases In 2019,Hou et al.determined the exact value of the decomposition number of H when H is an r-uniform hypergraph consisting of 2 hyperedges,and determined the exact value of decomposition number of H when H is an r-uniform hypergraph consisting of exactly k independent hyperedges.On this basis,We determine the exact value of?_r(n,T)when T is an arbitrary r-uniform hypertree with t hyperedges.In chapter 6,we briefly summarize the whole paper and put forward some problems that can be further studied.