On the upper bound of the size of the \(r\)-cover-free families (Q1328402)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On the upper bound of the size of the \(r\)-cover-free families |
scientific article; zbMATH DE number 599877
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the upper bound of the size of the \(r\)-cover-free families |
scientific article; zbMATH DE number 599877 |
Statements
On the upper bound of the size of the \(r\)-cover-free families (English)
0 references
20 October 1994
0 references
Let \(T(r,n)\) denote the maximum number of subsets of an \(n\)-set such that no subset is covered by the union of any other \(r\) subsets (such a system is called \(r\)-cover-free). It is shown that for \(n\) sufficiently large \[ {\log_ 2 T(r,n)\over n}\leq 8 {\log_ 2 r\over r^ 2}. \] This comes from a better understanding and proof of a result of A. G. Dyachkov and V. V. Rykov. The central element of this proof is a new set compression algorithm.
0 references
upper bound
0 references
\(r\)-cover-free families
0 references
superimposed code
0 references
set compression algorithm
0 references
