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
    0 references
    cover-free family
    0 references
    key distribution pattern
    0 references
    Sperner's theorem
    0 references
    superimposed binary code
    0 references
    0 references
    0 references
    0 references

    Identifiers