On the upper bound of the size of the \(r\)-cover-free families
type: Item
instance of: scholarly article
title: On the upper bound of the size of the \(r\)-cover-free families
zbMATH Open document ID: 0798.05071
DOI: 10.1016/0097-3165(94)90067-1
author: Miklós Ruszinkó
published in: Journal of Combinatorial Theory. Series A
publication date: 1994-10-20T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05D05
Mathematics Subject Classification ID: 94B25
zbMATH DE Number: 599877
zbMATH Keywords: upper bound
zbMATH Keywords: \(r\)-cover-free families
zbMATH Keywords: superimposed code
zbMATH Keywords: set compression algorithm
reviewed by: Péter L. Erdős
MaRDI profile type: Publication
full work available at URL: 0097-3165(94)90067-1
OpenAlex ID: W2004227827
cites work: Q3798601
cites work: Explicit construction of exponential sized families of k-independent sets
cites work: Q4063504
cites work: Q4745752
cites work: Families of finite sets in which no set is covered by the union of two others
cites work: Families of finite sets in which no set is covered by the union of \(r\) others
cites work: On Sperner families satisfying an additional condition
cites work: Q3829565
cites work: Near perfect coverings in graphs and hypergraphs
cites work: Q4099521
cites work: A Method for Detecting All Defective Members in a Population by Group Testing
cites work: Q3780312
cites work: On upper bounds for unrestricted binary-error-correcting codes
cites work: Improved asymptotic bounds for error-correcting codes
cites work: Q3285920
cites work: Nonrandom binary superimposed codes
cites work: On a packing and covering problem
cites work: Q3976643
description: scientific article; zbMATH DE number 599877