Some new bounds for cover-free families
type: Item
instance of: scholarly article
title: Some new bounds for cover-free families
zbMATH Open document ID: 0948.05055
published in: Journal of Combinatorial Theory. Series A
publication date: 2000-05-09T00:00:00Z
review text: A family \({\mathcal F}\) of subsets of \([n]= \{1,\dots, n\}\) is called \((w,r)\)-cover-free provided that for any \(w\) members \(B_1,\dots, B_w\) and any other \(r\) members \(A_1,\dots, A_r\) of \({\mathcal F}\), we have \[ \bigcap^w_{i= 1} B_i\nsubseteq \bigcup^r_{j=1} A_j. \] Let \(N((w,r),T)\) denote the minimum number \(n\) such that there exists a \((w,r)\)-cover-free family on \([n]\) of size \(T\). The following new lower bounds are proved, where \(c\) is some constant: \[ N((w,r), T)\geq 2c {{w+r\choose w}\over\log(w+ r)}\log T,\qquad\text{if }w,r\geq 1\quad\text{and }T\geq w+ r>2, \] \[ N((w,r), T)\geq 0.7c {{w+ r\choose w}(w+ r)\over \log{w+r\choose w}}\log T,\qquad \text{if } w,r\geq 1\quad\text{and }T> T_{w,r}, \] where \(T_{w,r}\) is some integer depending on \(w\) and \(r\).
reviewed by: Konrad Engel
Mathematics Subject Classification ID: 05D05
Mathematics Subject Classification ID: 05B40
zbMATH DE Number: 1443259
zbMATH Keywords: cover-free family
zbMATH Keywords: key distribution pattern
zbMATH Keywords: Sperner's theorem
zbMATH Keywords: superimposed binary code
author: D. R. Stinson
author: Ruizhong Wei
author: Li Zhu
MaRDI profile type: Publication
full work available at URL: jcta.1999.3036
OpenAlex ID: W2001779588
cites work: New combinatorial designs and their applications to group testing
cites work: Q4745752
cites work: On key storage in secure networks
cites work: Interval packing and covering in the Boolean lattice
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 \(r\)-cover-free families
cites work: Q3780312
cites work: Nonrandom binary superimposed codes
cites work: Key storage in secure networks
cites work: Bounds for key distribution patterns
cites work: On the upper bound of the size of the \(r\)-cover-free families
cites work: Secure frameproof codes, key distribution patterns, group testing algorithms and related structures
DOI: 10.1006/JCTA.1999.3036
description: scientific article; zbMATH DE number 1443259