Some new bounds for cover-free families through biclique covers

AbstractAn (r,w;d) cover-free family (CFF) is a family of subsets of a finite set X such that the intersection of any r members of the family contains at least d elements that are not in the union of any other w members. The minimum size of a set X for which there exists an (r,w;d)−CFF with t blocks is denoted by N((r,w;d),t).In this paper, we show that the value of N((r,w;d),t) is equal to the d-biclique covering number of the bipartite graph It(r,w) whose vertices are all w- and r-subsets of a t-element set, where a w-subset is adjacent to an r-subset if their intersection is empty. Next, we provide some new bounds for N((r,w;d),t). In particular, we show that for r≥w and r≥2N((r,w;1),t)≥cr+ww+1+r+w−1w+1+3r+w−4w−2logrlog(t−w+1), where c is approximately 12. Also, we determine the exact value of N((r,w;d),t) for t≤r+w+rw and also for some values of d. Finally, we show that N((1,1;d),4d−1)=4d−1 if and only if there exists a Hadamard matrix of order 4d