Upper Chromatic Numbers Of Optimal2-(V,3,1) Packings

Let positive integers v≥k≥t. A t-(v, k, λ) packing is a pair (X, B), where X is a v-set of elements (points) and B is a collection of k-subsets of X (blocks), such that every t-subset of points occurs in at most A blocks in B. The packing number Dλ(v, k, t) is the maximum number of blocks in any t-(v, k, A) packing. A t-(v, k, A) packing (X, B) is optimal if|B|=Dλ(v, k, t). If A=1, often one write D(v, k, t) for D1(v, k, t).A mixed hypergraph is a triple H=(X, C, D), where X is a finite set of ver-tices, while C and D are two families of subsets of X. The elements of C and D are called C-edges and D-edges respectively. Specially, if C=D, then’H is called a bi-hypergraph; if D=φ, then H is called a C-hypergraph; if C=φ, then H is called a D-hypergraph, H is now also a hypergraph. So hypergraph is a special case of mixed hypergraph. A strict k-coloring of H is a vertex coloring where any C-edge has at least two vertices of the same color and any D-edge has at least two vertices colored differ-ently. In a mixed hypergraph, it makes sense to study both the maximum and minimum numbers of colors required for a strict coloring. The maximum (minimum) integer k for which there exists a strict k-coloring of a mixed hypergraph is called the upper (lower) chromatic number of H.Coloring problem of mixed hypergraphs was first introduced in1992. This theorem is a relatively new topic on international, and there are many problems waiting for us to investigate. This problem was later extended to designs, such as coloring problems of Steiner triple and quadruple systems.In this thesis the concepts of mixed hypergraph and upper chromatic number are applied to optimal2-(v,3,1) packings, by regarding the vertex set of optimal2-(v,3,1) packing as the vertex set of bi-hypergraph, and the blocks as C-edges and D-edges at the same time. Then we study the upper chromatic numbers of some optimal2-(v,3,1) packings with small orders, and obtain the bound of upper chromatic numbers for optimal2-(v,3,1) packings with bigger orders by two recursive constructions.