Research On Extremal Problems Of Graphs And Hypergraphs

Graph theory originated from the problem of Seven Bridges of Konigsberg and has developed for hundreds of years.Nowadays,graph theory is widely used in other disciplines such as computer science,management,economics,etc.As an important branch of graph theory,the extremal problem in this paper is to study the maximum number of edges when the graph doesn’t contain some fixed subgraph and the number of its vertices is given.This kind of problem is called Turán type extremal problem.Since Turán Theorem was proved in 1941,Turán type extremal problem has won wide attention,and many classical results in graph theory have been derived.Hypergraphs is a natural generalization of graphs,and Turán type extremal problems of hypergraphs are also research hotspots.In this paper,we study Turán type extremal problem of Berge hypergraph,a special kind of hypergraphs.Berge hypergraph is a generalization of Berge path and Berge cycle.Since 2003,scholars have studied the Turán number of Berge hypergraph of cycles,paths,and trees.In recent years,Gy（?）ri et al.and Davoodi et al.extended the Erd（?）s-Gallai Theorem on paths to Berge paths.Then,results about the Turán problems of Berge hypergraphs on uniform hypergraphs such as Berge complete bipartite graphs,Berge complete graphs,as well as the Turán problems of Berge hypergraphs on general hypergraphs have emerged one after another.And also,some instrumental conclusions have been proved.At present,the study of Turán type extremal problem on Berge hypergraphs has become an active subject.Since the concept of Berge hypergraph was put forward relatively late,there are still few extremal results on it rightnow.Thus,there are lots of meaningful problems in this field worthy of further exploration.For a fixed graph（hypergraph）,it’s usually hard to determine its Turán number and extremal graph（hypergraph）.In this paper,we mainly study several Turán type extremal problems of graphs and hypergraphs on the basis of previous studies.This paper consists of six chapters,and it is organized as follows:·In chapter 1,we mainly introduce the development of extremal graph（hypergraph）theory,and some relevant concepts of graphs and hypergraphs.·In chapter 2,we introduce two important Decomposition Theorems of Simonovits.Three main theorems in this paper are proved by using Simonovits’Decomposition Theorems to obtain the approximate structure of extremal graphs.·The blow-up of a graph is obtained from the graph by repalcing each edge by a clique of the same order where the new vertices in cliques are all different.Erd（?）s et al.and Chen et al.studied the extremal graphs for blow-up of stars respectively.Glebov studied the extremal graphs for blow-up of paths.We find that extremal graphs for blow-up of stars contain blow-up of paths as subgraphs,and extremal graphs for blow-up of paths contain blow-up of stars as subgraphs.Therefore,in Chapter 3,we determine the exact value of exn,{S_k^p+1,P_k+1^p+1}and characterize the unique extremal graph.·The odd-ballooning of a graph is obtained from the graph by repalcing each edge by an odd cycle with length between 3 and q（q is odd and q≥3）where the new vertices in odd cycles are all different.So far,there are only a few results on the extremal problems of odd-ballooning of stars.In chapter 4,by using Simonovits’Decomposition Theorem,we determine the Turán numbers of odd-ballooning of paths and odd-ballooning of cycles and characterize their extremal graphs respectively.At the same time,we find that these two results can partially answer a question proposed by Simonovits:characterize graphs whose unique extremal graph is of the form K_s-1∨T_n-s+1,p,where s≥1,p≥2.·In 2019,Gyárfás proved that when the number of vertices of the extremal hypergraphs are 3,4,5,6,the Turán numbers of Berge-K₄in 3-graph are 1,4,5,8,respectively.In 2020,Gerner,Methuku and Palmer proved that when n≥9,the Turán number of Berge-K₄in3-graph is e（T₃（n,3））.In Chapter 5,we prove that when the number of vertices of the extremal hypergraphs are 7,8,the Turán numbers of Berge-K₄in 3-graph are e（T₃（7,3））and e（T₃（8,3））,respectively.Thus we completely determine the Turán number of Berge-K₄in 3-graph.·In chapter 6,we briefly summarize the paper and put forward some problems worthy of further study.