Some new bounds for cover-free families
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\).
scientific article; zbMATH DE number 1443259