Relaxations of Hall’s Condition: Optimal batch codes with multiple queries

Combinatorial batch codes model the storage of a database on a given number of servers such that any $k$ or fewer items can be retrieved by reading at most $t$ items from each server. %kkk A combinatorial batch code with parameters $n,k,m,t$ can be represented by a system $cF$ of $n$ (not necessarily distinct) sets over an $m$-element underlying set $X,$ such that for any $k$ or fewer members of $cF$ there exists a system of representatives in which each element of $X$ occurs with multiplicity at most $t.$ The main purpose is to determine the minimum $N(n,k,m,t)$ of total data storage $sum_{Fin cF}|F|$ over all combinatorial batch codes $cF$ with given parameters. Previous papers concentrated on the case $t=1.$ Here we obtain the first nontrivial results on combinatorial batch codes with $t>1.$ We determine $N(n,k,m,t)$ for all cases with $kle 3t,$ and also for all cases where $n ge t{ii{m}{lceil k/t ceil -2}}.$ Our results can be considered equivalently as minimum total size $sum_{Fin cF}|F|$ over all set systems $cF$ of given order $m$ and size $n,$ which satisfy a relaxed version of Hall's Condition; that is, $left|igcupcF' ight| ge |cF'|/t$ holds for every subsystem $cF'subseteq cF$ of size at most $k.$