recreational mathematics

Combinatorial covering designs

Author(s): Gordon; Mills; Rödl; Schönheim

A $(v, k, t)$ \textit{covering design}, or \textit{covering}, is a family of $k$-subsets, called \textit{blocks}, chosen from a $v$-set, such that each $t$-subset is contained in at least one of the blocks. The number of blocks is the covering’s \textit{size}, and the minimum size of such a covering is denoted by $C(v, k, t)$.

\begin{problem} Find a closed form, recurrence, or better bounds for $C(v,k,t)$. Find a procedure for constructing minimal coverings. \end{problem}

Keywords: recreational mathematics

Syndicate content