Decompositions Of 3-uniform Hypergraphs And Related Problems

A hypergraph H is a pair (V, E), where V is a finite set of vertices, E is a family of subsets of V (called hyperedges or edges).In the past 40 years, Graph theory was widely considered to be a very useful tool when solve the combinatorial problems in the field such as geometry, number theory, operations research and optimization. In order to solve more combinatorial problems, promote the concept grape to the hypergraph is a very natural thing. We will use the method in the combinatorial designs to study hypergraphs. In this thesis, we will consider the decompositions of 3-uniform hypergraphs into some special hypergraphs which are called K4(3)-e and W4(3).LetΓbe a set of simple t-uniform hypergraphs. A t-(v,Γ, A) packing(covering) is a pair (X, B), where X is a set of v points,B is a collection of hypergraphs (called blocks) on the subsets of X, such that for each B∈B, B is isomorphic to one ofΓ, and every t-subset of X is contained in at most(least) A blocks. The t-(v,Γ, A) packing(covering) which has the largest(smallest) number of blocks is called maximum(minimum). Its number of blocks is called packing(covering) number.If t≥3, the research of t-(v,Γ,λ) packing and covering is still in the early stage, there have not many results in this field. We will deal with the case t= 3. When t= 3, for the specialization of blocks and variety of the choose ofΓ, the difficulty of research is greater than the case t= 2. We follow the method which was used when t= 2, letΓbe a hyperwheel K4(3)-e or W4(3). We will consider the packing and covering about these hypergraphs. The research of such hypergraphs will provide fundamental basis for the research of complex hypergraph decompositions.This thesis is organized as follows.Chapter 1 gives a brief introduction on the background of t-designs, graph decom-positions and hypergraph decompositions and gives main results of this thesis. In Chapter 2, we introduce some auxiliary designs to establish the fundamental construction for 3-(v,K4(3)-e,λ) packing. Both direct and recursive constructions are used to show that:an MPλ(3,K4(3)-e, v) with dh dλ(3, K4(3)-e, v) blocks exists for any positive integers v≥4 andλ, its leave has at most 2 edges. Here, pλ(3, K4(3)-e, v)=dλ(3, K4(3)-e, v)=[λv(v-1)(v-2)/18].In Chapter 3, we deal with the 3-(v, W4(3),λ) maximum packing. The method used here is similar with which is used in Chapter 2. In this case, the discussion about the number of edges in the leave is more complex. For the characteristic of hypergraph W4(3), we can get some special constructions. Use these constructions, we can proof that the packing number can reach the bound in theoretical. That is,In Chapter 4 and Chapter 5, we deal with the caseΓis K4(3)-e and W4(3) respectively. We will construct 3-(v,Γ,λ) minimum coverings. Both direct and recursive construc-tions are used to show that the covering number cλ(3, K4(3)-e, v)=[λv(v-1)(v-2)/181, and the bound of the covering number cλ(3,W4(3),v) in the theoretical is also admissible. That is,...