Some New Bounds For Cover-Free Families Through Biclique Cover

Abstract

An $(r,w;d)$ cover-free family $(CFF)$ is a family of subsets of a finite set 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 number of elements 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 $I_t(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 introduce some new bounds for $N((r,w;d),t)$. For instance, we show that for $r\ge w$ and $r\ge 2$ $$N((r,w;1),t)\ge c\frac{\left(\genfrac{}{}{0ex}{}{r+w}{w+1}\right)+\left(\genfrac{}{}{0ex}{}{r+w-1}{w+1}\right)+3\left(\genfrac{}{}{0ex}{}{r+w-4}{w-2}\right)}{\log r}\log (t-w+1),$$ where $c$ is a constant satisfies the well-known bound $N((r,1;1),t)\ge c\frac{r^2}{\log r}\log t$. Also, we determine the exact value of $N((r,w;d),t)$ for some values of $d$. Finally, we show that $N((1,1;d),4d-1)=4d-1$ whenever there exists a Hadamard matrix of order 4d.