Intersection Inequalities for the Covering Problem

From MaRDI portal





Suppose that one considers the set of \(p^n\) vectors of length \(n\) which may be formed when each component may take one of \(p\) values. Then we define \(\sigma(n,p)\) as the minimal cardinality of a set of vectors which \textit{covers} all \(p^n\) vectors, using the fact that a vector is said to cover itself and the \(n\) vectors which differ from it in exactly one component. It is a well-known result that \((1 + n(p - 1))\sigma(n,p)\ge p^n\). The present paper strengthens this inequality to take into account the cardinalities of subsets of a covering set, and shows how the resulting system of inequalities may be employed to obtain improved numerical bounds on \(\sigma(n,p)\). In particular, it is shown that \(\sigma(8,2)=32\).











This page was built for publication: Intersection Inequalities for the Covering Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5581649)