Constructing designs straightforwardly: Worst arising cases (Q2713359)

A \(t\)-\((v,k,\lambda)\) packing (covering) design \(D\) is a collection of \(k\)-element sets, called blocks, out of a \(v\)-set such that each \(t\)-subset of the \(v\)-set is contained in at most (at least) \(\lambda\) blocks. Generally, one is interested in maximizing (minimizing) the size of a packing (covering) design with given parameters, but other questions may be posed as well. In the current paper, the problems of finding the minimum size of a maximal packing and the maximum size of a minimal covering are considered. A packing is maximal if it is not possible to add further blocks without violating the packing criterion; a minimal covering is defined in an analogous way. The results obtained give worst-case bounds for the sizes of designs constructed, for example, by any greedy algorithm.