COMBINATORIAL BATCH CODES AND TRANSVERSAL MATROIDS

Combinatorial batch codes were defined by Paterson, Stinson, and Wei as purely combinatorial versions of the batch codes introduced by Ishai, Kushilevitz, Ostrovsky, and Sahai. There are n items and m servers each of which stores a subset of the items. It is required that, for prescribed integers k and t, any k items can be retrieved by reading at most t items from each server. Only the case t = 1 is considered here. An optimal combinatorial batch code is one in which the total storage required is a minimum. We establish an important connection between combinatorial batch codes and transversal matroids, and exploit this connection to characterize optimal combinatorial batch codes if n = m + 1 and n = m + 2.