Intersection Inequalities for the Covering Problem
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\).
- On covering and coloring problems for rook domains
- An inequality in binary vector spaces
- Bounds on packings and coverings by spheres in q-ary and mixed Hamming spaces
- New results on codes with covering radius 1 and minimum distance 2
- A new lower bound for the football pool problem for six matches
- Tight bounds for Katona's shadow intersection theorem
- Independent domination in hypercubes
- On the minimum size of 4-uniform hypergraphs without property \(B\)
- On covering sets and error-correcting codes
- Covering intersecting bi-set families under matroid constraints
- Generalized minor inequalities for the set covering polyhedron related to circulant matrices
- Hyper-rook Domain Inequalities
- scientific article; zbMATH DE number 4173033 (Why is no real title available?)
- scientific article; zbMATH DE number 3880735 (Why is no real title available?)
- On the number of ideals of the Niederreiter-Rosenbloom-Tsfasman poset and lower bounds on covering codes
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)