Some New Bounds For Cover-Free Families Through Biclique Cover

preprint2011arXivOpen access

Abstract

An (r,w;d)(r,w;d) cover-free family (CFF)(CFF) is a family of subsets of a finite set such that the intersection of any rr members of the family contains at least dd elements that are not in the union of any other ww members. The minimum number of elements for which there exists an (r,w;d)−CFF(r,w;d)-CFF with tt blocks is denoted by N((r,w;d),t)N((r,w;d),t). In this paper, we show that the value of N((r,w;d),t)N((r,w;d),t) is equal to the dd-biclique covering number of the bipartite graph It(r,w)I_t(r,w) whose vertices are all ww- and rr-subsets of a tt-element set, where a ww-subset is adjacent to an rr-subset if their intersection is empty. Next, we introduce some new bounds for N((r,w;d),t)N((r,w;d),t). For instance, we show that for r≥wr\geq w and r≥2r\geq 2 N((r,w;1),t)≥c(r+ww+1)+(r+w−1w+1)+3(r+w−4w−2)log⁡rlog⁡(t−w+1), N((r,w;1),t) \geq c{{r+w\choose w+1}+{r+w-1 \choose w+1}+ 3 {r+w-4 \choose w-2} \over \log r} \log (t-w+1), where cc is a constant satisfies the well-known bound N((r,1;1),t)≥cr2log⁡rlog⁡tN((r,1;1),t)\geq c\frac{r^2}{\log r}\log t. Also, we determine the exact value of N((r,w;d),t)N((r,w;d),t) for some values of dd. Finally, we show that N((1,1;d),4d−1)=4d−1N((1,1;d),4d-1)=4d-1 whenever there exists a Hadamard matrix of order 4d.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.