Intersection Inequalities for the Covering Problem (Q5581649)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3299766
Language Label Description Also known as
default for all languages
No label defined
    English
    Intersection Inequalities for the Covering Problem
    scientific article; zbMATH DE number 3299766

      Statements

      Intersection Inequalities for the Covering Problem (English)
      0 references
      0 references
      0 references
      1969
      0 references
      intersection inequalities
      0 references
      covering problem
      0 references
      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\).
      0 references

      Identifiers