On Combinatorial Batch Codes And Related Combinatorial Structures

In 2004,based on the background of data storage,Ishai,Kushilevitz,Ostrovsky and Sahai first proposed batch codes which can be employed in a distributed storage system for satisfying the user's distinct queries simultaneously and balancing the load among servers.In 2009,as a purely combinatorial version of batch codes,combinatorial batch codes(CBC)were defined by Paterson,Stinson and Wei in which each of m servers stores a subset of items(the number of items is n),and any set of at most k items can be retrieved by reading at most one item from each server.A CBC is called uniform if each item is stored in exactly c servers,and the goal is to determine the maximum number of items(denoted by n(m,c,k))for which there exists a uniform CBC.To ensure that items can be retrieved even in presence of servers failures in storage systems,Silberstein defined erasure combinatorial batch codes(ECBC)which allow some of the servers to fail at the same time and any set of items can be retrieved from the surviving servers.To save the total storage,for given parameters n,k,m,a CBC with minimum total storage N(n,k,m)over all servers is called optimal.A key and difficult problem in the research on batch codes is to determine the extremal values of(erasure)combinatorial batch codes and uniform combinatorial batch codes for some parameters and give explicit constructions of codes attaining those extremal values.However,so far this problem has not been solved for many parameters.In this thesis,we determine some N(n,k,m)and n(m,c,k),and construct optimal CBCs and ECBCs by connecting(erasure)combina-torial batch codes with other combinatorial structures.This thesis mainly includes the following results.In Chapter 1,we first present a lower bound on N(n,k,k+1)by investigating the structure of CBC(n,N,k,k+ 1),and it is tight for some n and k.Then by this lower bound,we determine n(k+1,2,k)and give an upper bound on n(k+1,3,k)for k>19,that is,n(k+ 1,2,k)= k + 3 for 5<f<10,n(k +1,2,k)= k + 2 for k?10 and n(k +1,3,k)? k + 4 for k>19.We also give a relation between N(n,k,m)and N(n,k-1,m)by improving a result on monotonicity of N(n,k,m),from which we obtain N(m + 3,7,m)which is 24 for m = 8 and m +14 for m ? 9,and give a construction of optimal CBC(m + 3,m + 14,7,m)for m ? 9.In Chapter 2,we determine some N(n,5,m)and construct optimal CBC*(n,N,5,m)from bipartite graphs.Firstly,by studying the structure of CBC*(n,N,5,m)which has type[1,2],we proof that each optimal CBC*(n,N,5,m)with n?[m2/4]can be trans-formed into an optimal CBC*(n,N,5,m)of type[1,2]according to 5-Hall condition and several transformations,and we determine N(n,5,m)for 5?m<n?[m2/4]by com-puting the maximum integer number of singletons in a CBC*(n,5,m)of type[1,2].Sec-ondly,according to N([m2/4],5,m)and a result on monotonicity of N(n,5,m),we obtain a lower bound on N(n,5,m)when n>[m2/4?,and then we show that it is tight when n ?[m2/4]+(m/2 3]+([m/2]3)by giving an explicit construction of CBC*(n,N,5,m),so We have N(n,5,m)=3n-[m2+/4].Finally,We present a bound on N(n,5,m)for[m2/4]+ +([m/2]3)+([m/2]3)<n?(m3),which is tight for some n and m.In Chapter 3,we define a new class of regular graphs which are generalized strongly regular graphs by generalizing the definition of strongly regular graphs.We study this family of graphs and present some restrictions on the parameters of a class of generalized strongly regular graphs of grade 2.Then we derive generalized strongly regular graphs of arbitrary grade from a Cayley graph,and based on those of grade 2 and grade 3,we construct combinatorial batch codes by giving an incidence relation between some objects of the graphs.In Chapter 4,we give a new construction of erasure combinatorial batch codes based on nonadaptive group testing.We connect separable matrices and disjunct matrices the mathematical model of nonadaptive group testing)with the incidence matrices of erasure combinatorial batch codes,and proof that the separable(disjunct)matrix satisfying some conditions is the incidence matrix of an erasure combinatorial batch code.A lot of constructions of separable matrices and disjunct matrices based on distinct combinatorial structures have been given by many authors,from which we can obtain ECBCs with different parameters.In particular,if a separable(disjunct)matrix has constant column weight,then the derived erasure combinatorial batch code is optimal.