Some Extremal Problems Of Turán,Covering And Tiling Type

Extremal graph theory considers problems of maximizing or minimizing certain graph parameters in graph classes of interest and we denote the corresponding graphs by extremal graphs.It contains several kinds of problems such as shortest path,minimumcost flows,the existence of some given subgraphs and graph covering with certain properties.These problems not only play important roles in graph theory,but also relate to some other branches such as computer science,transportation and big data.In this thesis,we concentrate on Turán,covering and tiling types of extremal problems.We first put our interest in Turin problems in graph and hypergraph.Our work has two aspects.1.Given a graph F and an integer p≥ 3,the edge blow-up of F,denoted by Fp,is the graph obtained from replacing each edge in F by a clique of size p where the new p-2 vertices of the cliques are all different.In this thesis,we concern about the Turán problem for the edge blow-up of trees.Given a tree T,denote by A and B its two color classes with a=|A|≤|B|.If δ_T（A）≥3,then for any p≥3,when n is sufficiently large,we completely determine the value of ex（n,Tp+1）and its extremal graphs.These results solve some problems remaining in Liu’s research.At the same time,we determine the maximum number of edges in the family of {K₁,k,kK₂,2K_1,k-1}-free graphs and the extremal graphs,which is an extension of a result given by Abbott et al.（1972）,who solved the Turán problems of {K₁,s,tK₂}-free graphs.2.A hypergraph is called a k-uniform hypergraph（or k-graph）if each of its edges has size k.Given a graph F and an integer r≥2,then a r-uniform linear hypergraph,denoted by F（r）,can be defined as a r-uniform linear hypergraph obtained by enlarging each edge with a new,distinct set of r-2 vertices.We mainly focus on the extremal problems of linear trees.Given a tree T,denote by A and B its two color classes with a=|A|≤|B|.If δ_T（A）≥2 or δ_T（A）=1 and A is a minimum vertex cover of T,then for any r ≥ 5,when n is sufficiently large,we determine the extremal hypergraphs of T（r）and give a more accurate value of exr（n,T（r））,which improves the result given by Füredi for r≥5.On the other hand,we also solve the extremal problem of L_k^r for r ≥5 and n sufficiently large where L_k^r is a r-uniform linear star,which generalizes the results of L_k³ by Chung and Frankl.Next we consider the maximum number of independent sets under covering conditions.For some given graph H,a graph G is H-covered by some given graph H if each vertex in G is contained in a copy of H.Chakraborti and Loh raised an interesting question:consider the problem of maximizing the number of independent sets of order t>2 in an n-vertex H-covered graph.In this thesis,we give the maximum number of independent sets of size t ≥3 in N-vertex K_n-covered graphs and completely determine the extremal graph for N≥n.The result answers the question for H=K_n.The proof uses a new method,called edge-switching operation,on hypergraphs which never increases the number of independent sets.Finally we consider the extremal problem under perfect tiling conditions as a special case of covering.A k-graph is a k-uniform hypergraph tree（or k-tree）if its edges can be ordered as E1,…,Et such that for any i>1,there exists an a（i）<i such that Ei∩（∪j=1i-1Ej）? Eα（i）.A perfect T-tiling（or T-tiling）in a hypergraph G（or a graph G）is a collection of vertex-disjoint copies of a hypergraph T（or graph T）in G（or G）that together cover all the vertices in G（or G）.In this thesis,we investigate in a hypergraph model where one starts with a dense hypergraph and add m random hyperedges to it,which is equal to a random hypergraph G（n,p）.We gave the lower bound of p under the condition of a a.a.s perfect T-tiling,where T is a hypergraph tree.This research generalizes the result in graphs given by Bohman,Frieze and Martin.