Almost Cover-Free Codes and Designs
An -subset of codewords of a binary code is said to be an {\em -bad} in if the code contains a subset of other codewords such that the conjunction of the codewords is covered by the disjunctive sum of the codewords. Otherwise, the -subset of codewords of is said to be an {\em -good} in~.mA binary code is said to be a cover-free -code if the code does not contain -bad subsets. In this paper, we introduce a natural {\em probabilistic} generalization of cover-free -codes, namely: a binary code is said to be an almost cover-free -code if {\em almost all} -subsets of its codewords are -good. We discuss the concept of almost cover-free -codes arising in combinatorial group testing problems connected with the nonadaptive search of defective supersets (complexes). We develop a random coding method based on the ensemble of binary constant weight codes to obtain lower bounds on the capacity of such codes.