| Extremal graph theory is an important branch of graph theory.It concerns the relations between parameters such as order,size,coloring,the maximum degree,the minimum degree,as well as the extremal graphs that satisfy some certain properties.In extremal graph theory,partitioning graphs and Hamiltonian structure are two important topics.The thesis is devoted to investigate judicious partitioning problems and the minimum degree conditions for Hamiltonian cycles in hypergraphs.We show that every digraph with some properties admits a bipartition V1,V2,such that both of e(V1,V2)and e(V2,V1)are relatively large,and we also prove that the extremal case of the problem determining the minimum 3-degree threshold for a 4-uniform hypergraph containing a tight Hamilton cycle.The main contents can be summarized as follows.In the first part,we consider judicious partitioning problems of digraphs with outdegree at least d.Lee,Loh and Sudakov proposed a famous conjecture in 2006:Every digraph with m arcs and minimum outdegree at least d admits a bipartition V1,V2 with min {e(Vi,V2),e(V2,V1)}≥((d-1)/(2(2d-1))+o(1))m.Firstly,using the classic probability method,there is a bipartition of a digraph such that the values of arcs crossing in difference direction between these two sets are relatively large.Next,by considering some properties of gap and "huge" vertices,we can prove the conjecture is true for digraphs with d huge vertices or a unique huge vertex.Furthermore,we give a simple and unified proof for the cases d=2 and d=3.The second part is devoted to study judicious partitioning problems of digraphs with outdegree at least 4.We proved that if a digraph with m arcs satisfies this property,then there is a bipartition(Vi,V2),such that the values of the crossing arcs e(V1,V2)and e(V2,V1)are not less than(3/14+o(1))m.Through a partition of general digraphs and the concepts of tight components and difference of these huge vertices,there exist several properties of digraphs that cannot admit the above inequality.By showing these properties cannot be satisfied at the same time,it is proved that the conjecture of Lee,Loh and Sudakov is true for d=4.Finally,the third part presents the Dirac-type condition for Hamiltonian paths and cycles in hypergraphs.We proved the extremal case of the problem determining the minimum 3-degree threshold for a 4-graph containing a tight Hamiltonian path and cycle,and also show that the bound is best.Firstly,we give the definition of the "typical" set in the hypergraph,and show that almost all vertices,pair of vertices and triples of vertices are typical if the 4-graph has few atypical edges and large minimal 3-degree.Next,we get a Hamiltonian path by building a bridge,takeing care of atypical vertices and connecting the remaining typical vertices.At last,by the definition of switch,we find out a good family that can form a Hamiltonian cycle,and get the exact Dirac-type condition for tight Hamiltonian paths and cycles in 4-graph. |
