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
1969
0 references
intersection inequalities
0 references
covering problem
0 references
0.8055456280708313
0 references
0.7852423787117004
0 references
0.7831740975379944
0 references
0.7799096703529358
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