Research On Partition And Covering Of Edge-Colored Hypergraphs

Partition and covering by monochromatic structures is a classical subject of Ramsey theory.The subject contains two subproblems.One is: How many vertices can we find a monochromatic subgraph(subhypergraph)of a certain type in an r-edge-colored complete graph(hypergraph)? The other is: How many monochromatic subgraphs(subhypergraphs)of certain type do we need so that their vertex sets form either a partition or a covering of the vertices of the redge-colored complete graph(hypergraph)? There are many revelent results and conjectures in the subject for edge-colored graphs.However,in contrast to the graph case,there are only a few results on covering the vertices of hypergraphs with monochromatic pieces.Even paths and cycles partition or covering in 2-edge-colored uniform complete hypergraphs,and the revelent Ramsey number problems,are not solved completely.The thesis mainly study partition and covering of edge-colored hypergraphs by loose paths and loose cycles.Then we extend the results to ?-paths,?-cycles and other subhypergraphs partition and covering problems of edge-colored hypergraphs.The thesis contains five chapters as follows.In Chapter 1,we first introduce some useful basic notations and definitions,and then give a relatively complete introduction to the background,results and conjectures of partition and covering of edge-colored graphs.In Chapter 2,we give some known results of partition and covering of edgecolored hypergraphs.We mainly study the loose paths partition conjecture for2-edge-colored k-uniform complete hypergraphs,which was presented by Gy?arf?as and S?ark¨ozy in 2013.Conjecture.In every 2-edge-colored k-uniform complete hypergraph Kk n,there are two disjoint monochromatic loose paths of distinct colors covering all but at most k-2 vertices.Gy?arf?as and S?ark¨ozy showed that if the conjecture is true then the result is sharp for sufficiently large n.They also showed that in every 2-edge-colored k-uniform complete hypergraph Kk n,there are two disjoint monochromatic loose paths of distinct colors covering all but at most 2k-5 vertices.The statement means that the conjecture is true for k = 3.we prove the following slightly stronger result than Gy?arf?as and S?ark¨ozy's conjecture.Theorem.Let k ? 3 be an integer and n = r(k-1)+ 2 for some integer r.If the edges of the complete k-uniform hypergraph Kk nare colored with two colors,then V(Kk n)can be partitioned into two monochromatic loose paths of distinct colors.Based on the result,we focus on the following natural question: For every2-edge-colored Kk n,can we find two monochromatic loose paths(not necessarily disjoint)of distinct colors to cover all vertices of V(Kk n)such that the two paths share as few vertices as possible? We have the following statement.Theorem.For each 2-edge-colored Kk n,all the vertices can be covered by two monochromatic loose paths of distinct colors such that the two paths share at most k-2 vertices.Besides,the result is best possible.In Chapter 3,we pay our attention to cycles partition and covering.We show some known results,and give the following conjecture: For each 2-edge-colored Kk n,all the vertices of Kkn)can be covered by two monochromatic loose cycles(not necessarily disjoint)of distinct colors.We show that the conjecture holds for k = 3.Theorem.For each 2-edge-colored K3 n,all the vertices can be covered by two monochromatic loose cycles of distinct colors such that the two cycles share at most 2 vertices.In Chapter 4,we study the partition and covering edge-colored complete hypergraphs by ?-paths and ?-cycles.We give the following conjecture: Let s be an integer and n = s(k-?)+ 2?.If the edges of the complete k-uniform hypergraph Kk nare colored with two colors,then V(Kkn)can be partitioned into two monochromatic ?-paths of distinct colors.We confirm the conjecture for ?|k or ? ?k3.Theorem.Let ?,s,k be three integers,? ?k3and n = s(k-?)+ 2?.If the edges of the complete k-uniform hypergraph Kk nare colored with two colors,then V(Kk n)can be partitioned into two monochromatic ?-paths of distinct colors.In Chapter 5,we make a brief summary of this thesis and put forward the main problems for future research.