Study Of Several Kinds Of Hypergraph Decomposition Problems

The decomposition of the graph originated from the Hamilton cycle decomposition of the complete graph Kn solved by Walecki.After that,scholars at home and abroad began to study the problem of Hamilton cycle decomposition and extended it to hypergraphs.A hypergraph H is a pair(V,E),where V is a finite set,the elements in V are called vertices,the family of finite non-empty subsets of V is E,and the elements in E are called hyperedges.The Γ decomposition of a hypergraph H refers to the decomposition of a hypergraph into a set of several sub-hypergraphs.Each sub-hypergraph(called a block)is required to be isomorphic with one of the hypergraphs in Γ.The Γ decomposition of a hypergraph H is called(H,Γ)-design.This paper uses the idea of combinatorial design to study the Γ decomposition of hypergraphs.Firstly,the necessary conditions for decomposability are calculated based on the characteristics combined with the conclusions of the existing hypergraph decomposition.Then,the necessary conditions are analyzed in detail,and the decomposition results of some small-order hypergraphs are made.The result of the number decomposition is applied to the recursive construction to prove the adequacy of the necessary conditions.This paper solves the problem of decomposition of λ-fold complete bipartite 3-uniform hypergraphs with Γ={W4(3)},Γ={O},and gives partial decomposition results of complete 3-uniform hypergraphs Γ={W5(3)}.The structure of this article is as follows:The first chapter gives several typical designs of combination design,introduces the background of the emergence of hypergraphs,the significance of studying hypergraph decomposition,the results obtained at this stage,and the research content of this paper.The second chapter studies the decomposition problem of λKm,n(3)to W4(3).Firstly,consider the existence of the decomposition when m=n.The necessary conditions for its existence are calculated as λn(n-1)≡0(mod 4),n≥3.Therefore,we need to consider the existence of the decomposition of λ=1,n≡0(mod 4),n≡1(mod 4)and the existence of the decomposition of λ=2,n≡2(mod 4),n≡3(mod 4).Secondly,based on the known results in related literature,make some recursive structures through inference,and the results of the small order hypergraph decomposition required for the construction.For the case where the small order hypergraph decomposition does not exist,use "digging" and definition New hypergraphs that meet the specified conditions are resolved.Finally,the necessary and sufficient conditions for the decomposition obtained by the proof.When m≠n,the necessary and sufficient conditions of decomposition obtained by the above method.The third chapter studies the decomposition problem of Kn(3)to W5(3).The necessary condition for the existence of this decomposition by calculation is n≡0,1,2(mod 5),n≥6.Because the order is relatively large,the necessary conditions for the decomposition cannot be fully proved.Partially complete 3-uniform hypergraphs were decomposed into W5(3)only by computer search.The fourth chapter studies the decomposition problemof λKm,n(3)to O.The necessary condition for existence of Sλ(3,O,m,n)by calculation is λmn(m+n-2)≡0(mod 16),λm(2n+m-3)≡0(mod 8),λn(2m+n-3)≡0(mod 8),λm≡0(mod 2),λn≡0(mod 2),λ(m+n-2)≡0(mod 2),m+n≥6.The study method in this chapter is same as Chapter 2.Due to the special structure of regular octahedron,C4 decomposition can be performed first,and then insert the upper and lower vertices of C4 to generate octahedron.Based on this method,some recursive structures and small order hypergraph decomposition results are given.Finally,the necessary and sufficient conditions for the decomposition obtained are proved.