Some new bounds for cover-free families (Q1976329)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Some new bounds for cover-free families |
scientific article |
Statements
Some new bounds for cover-free families (English)
0 references
9 May 2000
0 references
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\).
0 references
cover-free family
0 references
key distribution pattern
0 references
Sperner's theorem
0 references
superimposed binary code
0 references