Turán numbers and batch codes

Combinatorial batch codes provide a tool for distributed data storage, with possible application in reducing the computational overhead of private information retrieval protocol. Recently, Balachandran and Bhattacharya observed that the problem of constructing such uniform codes with some extremal properties can be formulated as a Turán-type question on hypergraphs. Here we establish general lower and upper bounds for this extremal problem, and also for its generalization where the forbidden family consists of those rr-uniform hypergraphs HH which satisfy the condition k≥|E(H)|>|V(H)|+qk≥|E(H)|>|V(H)|+q (for k>q+rk>q+r and q>−rq>−r fixed). We also prove that, in the given range of parameters, the considered Turán function is asymptotically equal to the one restricted to |E(H)|=k|E(H)|=k, studied by Brown, Erdős and T. Sós. Both families contain some rr-partite members–often called the ‘degenerate case’, characterized by the equality limn→∞ex(n,F)/nr=0–and therefore their exact order of growth is not known.