Some New Bounds for Cover-Free Families

Let N ((w; r); T ) denote the minimum number of points in a (w; r)-cover-free family having T blocks. In this paper, we prove two new lower bounds on N . 1 Introduction Cover-free families were first introduced in 1964 by Kautz and Singleton [9] to investigate superimposed binary codes. These structures have been discussed in several equivalent formulations in subjects such as information theory, combinatorics and group testing by numerous researchers (see, for example, [1, 2, 4, 5, 6, 7, 8, 12]). In 1988, Mitchell and Piper [10] defined the concept of key distribution patterns, which are in fact a generalized type of cover-free family. Some papers giving constructions and bounds for these objects include [3, 4, 11, 14]. Here is the definition of a cover-free family. Definition 1.1 Let X be an n-set and let F be a set of subsets (blocks) of X. (X; F) is called a (w; r)-cover-free family (or (w; r)-CFF) provided that, for any w blocks B 1 ; \Delta \Delta \Delta ; Bw 2 F and any other ..