On the upper bound of the size of the \(r\)-cover-free families (Q1328402): Difference between revisions

Let \(T(r,n)\) denote the maximum number of subsets of an \(n\)-set such that no subset is covered by the union of any other \(r\) subsets (such a system is called \(r\)-cover-free). It is shown that for \(n\) sufficiently large \[ {\log_ 2 T(r,n)\over n}\leq 8 {\log_ 2 r\over r^ 2}. \] This comes from a better understanding and proof of a result of A. G. Dyachkov and V. V. Rykov. The central element of this proof is a new set compression algorithm.