Some New Bounds For Cover-Free Families Through Biclique Cover

Mathematics – Combinatorics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Scientific paper

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\geq w$ and $r\geq 2$ $$ 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 $c$ is a constant satisfies the well-known bound $N((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)$ 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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Some New Bounds For Cover-Free Families Through Biclique Cover does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Some New Bounds For Cover-Free Families Through Biclique Cover, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Some New Bounds For Cover-Free Families Through Biclique Cover will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-165751

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.