Lower bounds for cover-free families

MaRDI QIDQ2629487zbMATH OpenFDO

Authors Ali Z. Abdi, Nader H. Bshouty

Publication date 6 July 2016

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.03578, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p45

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

cover-free familylower bound

Mathematics Subject Classification ID

Combinatorial aspects of block designs (05B05) Combinatorial aspects of packing and covering (05B40)

Abstract: Let $calF$ be a set of blocks of a $t$-set $X$. $(X,calF)$ is called $(w,r)$-cover-free family ($(w,r)-$CFF) provided that, the intersection of any $w$ blocks in $calF$ is not contained in the union of any other $r$ blocks in $calF$. We give new asymptotic lower bounds for the number of minimum points $t$ in a $(w,r)$-CFF when $wler=|calF{|}^{e}psilon$ for some constant $epsilonge1/2$.

Review text

Summary: Let \(\mathcal F\) be a set of blocks of a \(t\)-set \(X\). A pair \((X,\mathcal F)\) is called an \((w,r)\)-cover-free family (\((w,r)\)-CFF) provided that, the intersection of any \(w\) blocks in \(\mathcal F\) is not contained in the union of any other \(r\) blocks in \(\mathcal F\).{ }We give new asymptotic lower bounds for the number of minimum points \(t\) in a \((w,r)\)-CFF when \(w\leq r=|\mathcal F|^\epsilon\) for some constant \(\epsilon\geq 1/2\).

Recommendations

• Some new bounds for cover-free families
• A generalization of (2,w;d)-cover free families.
• Some new bounds for cover-free families through biclique covers
• Asymptotic upper bound for the rate of \((w,r)\) cover-free codes
• Almost optimal cover-free families

Cites work

• Bounds on the rate of disjunctive codes
• scientific article; zbMATH DE number 3801449 (Why is no real title available?)
• Learning a Hidden Subgraph
• Nonrandom binary superimposed codes
• On r-cover-free families
• On a bound of cover-free families
• On the upper bound of the size of the \(r\)-cover-free families
• Some new bounds for cover-free families

Cited in

(10)

• Some new bounds for cover-free families through biclique covers
• Some new bounds for cover-free families
• Non-adaptive learning of a hidden hypergraph
• A generalization of (2,w;d)-cover free families.
• A note on cover-free families
• Almost optimal cover-free families
• A survey of cover-free families: constructions, applications, and generalizations
• Lower bounds on the minimal dispersion of point sets via cover-free families
• Lower bounds for graph reconstruction with maximal independent set queries
• Lower bounds for coverings of pairs by large blocks

This page was built for publication: Lower bounds for cover-free families

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2629487)