Certain Issues On Combinatorial Designs

Combinatorial design theory is an important branch of combinatorial mathematics.It contains a lot of classical problems as well as a lot of application problems.For classical problems,we have discussed graph decomposition and intersection number problems.For application problems,this thesis is mainly concerned on two issues of distributed storage systems:the reliability of distributed storage systems and the privacy of users in distributed storage systems.Graph decomposition is one of the core issues in combination design theory.The H-decomposition of a graph G is to divide the edge of G into a set of subgraphs which are isomorphic to H,{H1,...,Hk},and satisfied:∪1≤i≤kHi=G;(2)for any 1≤i,j≤k,we have E(Hi)n E(Hj)=(?).This thesis has studied the sufficient and necessary con-ditions for the triangle decomposition of multigraphs λKv-λKw-λKu.Intersection number is another important problem in combinatorial design theory.For the intersec-tion number problem,this thesis has mainly studied the 4-way intersection problem for kite systems.As for the reliability of distributed storage system,this thesis considers fraction-al repetition codes that applied to DSSs,which are closely related to the combination design theory.We construct a special class of fractional repetition codes by mutual-ly orthogonal Latin squares.These codes are vital for DSSs in which both the per-node storage and repetition degree can easily be adjusted simultaneously.In addition,these codes pertain to node access frequency balancing.For distributed storage data,in addition to its storage reliability,we also need to consider the privacy of users when downloading data.Privacy protection is an important problem in information commu-nication.The private information retrieval(PIR)problem in this thesis belongs to this kind of problem.For the PIR problem with m retrieved values and k databases against t colluding databases(t-private MPIR),we describe it from the viewpoint of information theory.And the relationship between t and m is derived.Furthermore,a scheme of t-private MPIR with lower complexity is given.This thesis is organized as follows.In Chapter 1,we give a brief introduction on the background of graph decompo-sition,the intersection number of kite system,distributed storage systems and privacy information retrieval,and the main result of this thesis.In Chapter 2,we study the triangle decomposition of multigraph λKv-λKw-λKu.When the multiplicity λ is odd,the necessary and sufficient conditions of triangle de-compositions of AKv-AKw-AKu are given.When u is even,we showed that for large enough v,the elementary necessary conditions for the existence of a triangle decompo-sition of λKv-λKw-λKu are also sufficient.In Chapter 3,we discuss the intersection number of kite systems.Let I(v)={0,1,...,bv}\{bv-1} where bv=v(v-1)/8.Let Jμ(v)={s:there exist μ kite systems of order v intersecting in s blocks}.This chapter mainly gives and proves the necessary and sufficient condition of Jμ(v)=I(v).In Chapter 4,we study an important class of codes in distributed storage systems:fraction repetition codes.We construct a special class of fraction repetition codes by mutually orthogonal Latin squares in combinatorial design theory.These codes are vital for DSSs in which both the per-node storage and repetition degree can easily be adjusted simultaneously.In addition,these codes pertain to node access frequency balancing.In Chapter 5,we study the problem of private information retrieval.For the PIR problem with m retrieved values and k databases against t colluding databases,we de-scribe it from the viewpoint of information theory.And the relationship between t and m is derived by entropy function.Furthermore,a scheme of t-private MPIR with lower complexity is given.Chapter 6 includes the main content of this thesis and some problems which need to be further studied.