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 the normal view instead:
scientific article; zbMATH DE number 599877
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| 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
0.8343673348426819
0 references
0.8189668655395508
0 references
0.8063322305679321
0 references
0.7829282879829407
0 references
0.7726320624351501
0 references
