Zsolt Tuza: Combinatorial Batch Codes

Let n,m,k be given positive integers. We consider multihypergraphs (i.e., multiple edges are allowed) with n vertices and m edges, with the property that the union of any i edges contains at least i vertices, for all i=1,2,...,k. The problem is to minimize the total size of edges (which is equal to the degree sum). For r fixed, an interesting related Turan-type problem is to determine the largest m admitting an r-uniform (multi)hypergraph of order n that satisfies the condition above with a given k.

joint work with Csilla Bujtas