A probabilistic variant of Sperner ’s theorem and of maximal r-cover free families

Abstract A family of sets is called r -cover free if no set in the family is contained in the union of r (or less) other sets in the family. A 1-cover free family is simply an antichain with respect to set inclusion. Thus, Sperner’s classical result determines the maximal cardinality of a 1-cover free family of subsets of an n -element set. Estimating the maximal cardinality of an r -cover free family of subsets of an n -element set for r > 1 was also studied. In this note we are interested in the following probabilistic variant of this problem. Let S 0 , S 1 , … , S r be independent and identically distributed random subsets of an n -element set. Which distribution minimizes the probability that S 0 ⊆ ⋃ i = 1 r S i ? A natural candidate is the uniform distribution on an r -cover-free family of maximal cardinality. We show that for r = 1 such distribution is indeed best possible. In a complete contrast, we also show that this is far from being true for every r > 1 and n large enough.